Algoritm lacom cu exemple: Metoda lacomă & Abordare

Cuprins:

Anonim

Ce este un algoritm Greedy?

În Greedy Algorithm, un set de resurse sunt împărțite recursiv pe baza disponibilității imediate maxime a resursei respective în orice etapă dată de execuție.

Pentru a rezolva o problemă bazată pe abordarea lacomă, există două etape

  1. Scanarea listei de articole
  2. Optimizare

Aceste etape sunt prezentate în paralel în acest tutorial algoritm Greedy, pe parcursul divizării matricei.

Pentru a înțelege abordarea lacomă, va trebui să aveți cunoștințe practice despre recursivitate și schimbarea contextului. Acest lucru vă ajută să înțelegeți cum să urmăriți codul. Puteți defini paradigma lacomă în funcție de propriile afirmații necesare și suficiente.

Două condiții definesc paradigma lacomă.

  • Fiecare soluție treptată trebuie să structureze o problemă către soluția sa cea mai bine acceptată.
  • Este suficient dacă structurarea problemei se poate opri într-un număr finit de pași lacomi.

Cu teorizarea continuată, haideți să descriem istoria asociată abordării de căutare Greedy.

În acest tutorial algoritm Greedy, veți învăța:

  • Istoria algoritmilor lacomi
  • Strategii și decizii lacome
  • Caracteristicile abordării lacome
  • De ce să folosim abordarea Greedy?
  • Cum se rezolvă problema de selectare a activității
  • Abordarea arhitecturii lacomului
  • Dezavantaje ale algoritmilor lacomi

Istoria algoritmilor lacomi

Iată un reper important al algoritmilor lacomi:

  • Algoritmii lacomi au fost conceptualizați pentru mulți algoritmi de mers grafic în anii 1950.
  • Esdger Djikstra a conceptualizat algoritmul pentru a genera copaci minimi. El a urmărit să scurteze intervalul de rute din capitala olandeză, Amsterdam.
  • În același deceniu, Prim și Kruskal au realizat strategii de optimizare care s-au bazat pe minimizarea costurilor traseelor ​​de-a lungul rutelor cântărite.
  • În anii '70, cercetătorii americani, Cormen, Rivest și Stein au propus o substructurare recursivă a soluțiilor lacome în introducerea lor clasică în cartea algoritmilor.
  • Paradigma de căutare Greedy a fost înregistrată ca un tip diferit de strategie de optimizare în înregistrările NIST în 2005.
  • Până în prezent, protocoalele care rulează web, cum ar fi open-shortest-path-first (OSPF) și multe alte protocoale de comutare a pachetelor de rețea utilizează strategia lacomă pentru a minimiza timpul petrecut pe o rețea.

Strategii și decizii lacome

Logica în forma sa cea mai ușoară a fost redusă la „lacomă” sau „nu lacomă”. Aceste afirmații au fost definite de abordarea adoptată pentru a avansa în fiecare etapă a algoritmului.

De exemplu, algoritmul lui Djikstra a folosit o strategie lacomă pas cu pas identificarea gazdelor de pe Internet prin calcularea unei funcții de cost. Valoarea returnată de funcția de cost a determinat dacă următoarea cale este „lacomă” sau „non-lacomă”.

Pe scurt, un algoritm încetează să mai fie lacom dacă în orice stadiu face un pas care nu este lacom local. Problemele lacome se opresc fără alte scopuri ale lăcomiei.

Caracteristicile abordării lacome

Caracteristicile importante ale unui algoritm al metodei Greedy sunt:

  • Există o listă ordonată de resurse, cu costuri sau atribuții de valoare. Acestea cuantifică constrângerile asupra unui sistem.
  • Veți lua cantitatea maximă de resurse în timpul aplicării unei constrângeri.
  • De exemplu, într-o problemă de planificare a activității, costurile resurselor sunt în ore, iar activitățile trebuie efectuate în ordine serială.

De ce să folosim abordarea Greedy?

Iată motivele utilizării abordării lacome:

  • Abordarea lacomă are câteva avantaje, ceea ce o poate face potrivită pentru optimizare.
  • Un motiv important este acela de a obține cea mai fezabilă soluție imediat. În problema de selecție a activității (explicată mai jos), dacă se pot face mai multe activități înainte de a termina activitatea curentă, aceste activități pot fi efectuate în același timp.
  • Un alt motiv este împărțirea recursivă a unei probleme pe baza unei condiții, fără a fi nevoie să combinați toate soluțiile.
  • În problema de selectare a activității, pasul „împărțirii recursive” se realizează prin scanarea unei liste de articole o singură dată și luând în considerare anumite activități.

Cum se rezolvă problema de selectare a activității

În exemplul de planificare a activității, există un timp de „început” și „terminare” pentru fiecare activitate. Fiecare activitate este indexată cu un număr pentru referință. Există două categorii de activitate.

  1. activitate considerată : este activitatea, care este referința din care este analizată capacitatea de a face mai mult de o activitate rămasă.
  2. activități rămase: activități la unul sau mai mulți indici înaintea activității luate în considerare.

Durata totală oferă costul efectuării activității. Adică (finalizare - pornire) ne oferă durata ca cost al unei activități.

Veți afla că măsura lacomă este numărul de activități rămase pe care le puteți efectua în timpul unei activități luate în considerare.

Abordarea arhitecturii lacomului

PASUL 1)

Scanați lista costurilor activității, începând cu indexul 0 ca Index considerat.

PASUL 2)

Când mai multe activități pot fi terminate până la momentul respectiv, activitatea luată în considerare se termină, începeți să căutați una sau mai multe activități rămase.

PASUL 3)

Dacă nu mai există activități rămase, activitatea curentă rămasă devine următoarea activitate luată în considerare. Repetați pasul 1 și pasul 2, cu noua activitate luată în considerare. Dacă nu mai sunt activități rămase, treceți la pasul 4.

PASUL 4)

Returnează uniunea indicilor considerați. Aceștia sunt indicii de activitate care vor fi utilizați pentru a maximiza debitul.

Arhitectura abordării lacome

Explicarea codului

#include#include#include#define MAX_ACTIVITIES 12

Explicația codului:

  1. Fișiere / clase incluse în antet
  2. Un număr maxim de activități furnizate de utilizator.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Explicația codului:

  1. Spațiul de nume pentru operațiuni de streaming.
  2. O definiție a clasei pentru TIME
  3. O oră de timp.
  4. Un constructor implicit TIME
  5. Variabila de ore.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Explicația codului:

  1. O definiție a clasei din activitate
  2. Marcaje de timp care definesc o durată
  3. Toate marcajele de timp sunt inițializate la 0 în constructorul implicit
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Explicația codului:

  1. Partea 1 a definiției clasei de planificator.
  2. Considerat Index este punctul de plecare pentru scanarea matricei.
  3. Indicele de inițializare este utilizat pentru a atribui marcaje temporale aleatorii.
  4. O serie de obiecte de activitate este alocată dinamic folosind noul operator.
  5. Pointerul programat definește locația de bază curentă pentru lăcomie.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Explicația codului:

  1. Constructorul planificatorului - partea 2 a definiției clasei planificatorului.
  2. Indexul considerat definește începutul curent al scanării curente.
  3. Mărimea lacomă actuală este nedefinită la început.
for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++){current_activities[init_index].start.hours =rand() % 12;current_activities[init_index].finish.hours =current_activities[init_index].start.hours +(rand() % 2);printf("\nSTART:%d END %d\n",current_activities[init_index].start.hours,current_activities[init_index].finish.hours);}… …

Explicația codului:

  1. O buclă for pentru inițializarea orelor de început și de sfârșit a fiecăreia dintre activitățile programate în prezent.
  2. Inițializarea timpului de începere.
  3. Inițializarea timpului de încheiere întotdeauna după sau exact la ora de început.
  4. O instrucțiune de depanare pentru a imprima duratele alocate.
public:Activity * activity_select(int);};

Explicația codului:

  1. Partea 4 - ultima parte a definiției clasei de planificare.
  2. Funcția de selectare a activității are ca bază un index de pornire și împarte misiunea lacomă în subprobleme lacome.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Folosind operatorul de rezoluție a scopului (: :), este furnizată definiția funcției.
  2. Indicele considerat este indicele numit după valoare. Greedy_extent este inițializat doar un index după Indexul considerat.
Activity * Scheduler :: activity_select(int considered_index){while( (greedy_extent < MAX_ACTIVITIES ) &&((this->current_activities[greedy_extent]).start.hours <(this->current_activities[considered_index]).finish.hours )){printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",(this->current_activities[greedy_extent]).start.hours,(this->current_activities[greedy_extent]).finish.hours,greedy_extent + 1);greedy_extent++;}… …

Explicația codului:

  1. Logica de bază - Extinderea lacomă este limitată la numărul de activități.
  2. Orele de început ale activității curente sunt verificate ca fiind programabile înainte ca activitatea considerată (dată de indexul considerat) să se termine.
  3. Atâta timp cât este posibil, este tipărită o declarație de depanare opțională.
  4. Treceți la următorul index din matricea de activitate
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Explicația codului:

  1. Verificări condiționate dacă toate activitățile au fost acoperite.
  2. Dacă nu, vă puteți reporni lacomul cu Indexul considerat ca punct curent. Acesta este un pas recursiv care împarte cu lăcomie afirmația problemei.
  3. Dacă da, se întoarce la apelant fără posibilități de extindere a lăcomiei.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Explicația codului:

  1. Funcția principală utilizată pentru a invoca programatorul.
  2. Este creat un nou programator.
  3. Funcția de selectare a activității, care returnează un indicator al activității de tip, revine la apelant după încheierea misiunii lacome.

Ieșire:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

Dezavantaje ale algoritmilor lacomi

Nu este potrivit pentru problemele Greedy în care este necesară o soluție pentru fiecare subproblemă, cum ar fi sortarea.

În astfel de probleme de practică a algoritmului Greedy, metoda Greedy poate fi greșită; în cel mai rău caz duce chiar la o soluție non-optimă.

Prin urmare, dezavantajul algoritmilor lacomi este acela de a nu ști ce se află înaintea stării lacome actuale.

Mai jos este o descriere a dezavantajului metodei Greedy:

În scanarea lacomă prezentată aici ca un copac (valoare mai mare lăcomie mai mare), o stare algoritmică la valoarea: 40, este probabil să ia 29 ca valoare următoare. În plus, misiunea sa se termină la 12. Aceasta înseamnă o valoare de 41.

Cu toate acestea, dacă algoritmul a luat o cale sub-optimă sau a adoptat o strategie de cucerire. apoi 25 ar fi urmate de 40, iar îmbunătățirea costurilor globale ar fi 65, care este evaluată cu 24 de puncte mai mult ca o decizie suboptimală.

Exemple de algoritmi lacomi

Majoritatea algoritmilor de rețea utilizează abordarea lacomă. Iată o listă cu câteva exemple de algoritmi Greedy:

  • Algoritmul copacului minim al lui Prim
  • Problema vânzătorului călător
  • Grafic - Hărți de colorat
  • Algoritmul copacului minim al lui Kruskal
  • Algoritmul arborelui minim al Dijkstra
  • Grafic - Copertă Vertex
  • Problema rucsacului
  • Problemă de programare a locurilor de muncă

Rezumat:

Pentru a rezuma, articolul a definit paradigma lacomă, a arătat cât de optimistă și recursivă lacomă vă pot ajuta să obțineți cea mai bună soluție până la un punct. Algoritmul Greedy este aplicat pe scară largă pentru rezolvarea problemelor în multe limbi, cum ar fi algoritmul Greedy Python, C, C #, PHP, Java, etc. abordare. În cele din urmă, au fost explicate demeritele utilizării abordării lacome.