Algoritm greedy

Algoritmii greedy formează o paradigmă algoritmică^⁠(d) care urmează euristica rezolvării de probleme^⁠(d) care face la nivel local alegerea optimă pentru fiecare etapă în speranța de a găsi un optim global. În multe probleme, o strategie greedy produce, în general, o soluție optimă, dar cu toate acestea o euristică greedy poate produce la nivel local soluții optime care aproximează o soluție optimă globală într-un timp rezonabil.

Determinarea numărului minim de monede cu care se dă un rest^⁠(d) printr-un algoritm greedy. Aceștia sunt pașii pe care și un om i-ar efectua pentru a emula un algoritm greedy pentru a compune suma de 36 de cenți, folosind numai monede cu valorile {1, 5, 10, 20}. Moneda de cea mai mare valoare, mai puțin decât restul datorat, este optimă. (În general, problema restului de bani necesită programare dinamică^⁠(d) pentru a găsi o soluție optimă; cu toate acestea, majoritatea sistemelor de mijloace de plată în numerar, inclusiv moneda Euro și dolarul american, sunt cazuri speciale în care strategia greedy găsește o soluție optimă.)

De exemplu, o strategie greedy pentru problema comis-voiajorului (care este de mare complexitate computațională) este următoarea euristică: „la fiecare etapă, se vizitează un oraș nevizitat aflat cel mai apropiat de actualul oraș”. Această euristică nu găsește neapărat o soluție mai bună, dar se termină într-un număr rezonabil de pași; găsirea unei soluții optime necesită de obicei nejustificat de mulți pași. În optimizarea matematică, algoritmii greedy rezolvă probleme combinatorice^⁠(d) cu proprietăți de matroide^⁠(d).

Detalii

În general, algoritmii greedy au cinci componente:

1. O mulțime de candidați, din care se creează o soluție
2. Funcția de selecție, care alege cel mai bun candidat pentru a fi adăugat la soluție
3. O funcție de fezabilitate, care este folosită pentru a determina dacă un candidat poate fi utilizat pentru a contribui la o soluție
4. O funcție obiectiv, care atribuie o valoare unei soluții sau unei soluții parțiale, și
5. O funcție de soluție, care va indica atunci când s-a descoperit o soluție completă

Algoritmii greedy produc soluții bune la unele probleme de matematică^⁠(d), dar nu la altele. Cele mai multe probleme la care funcționează vor avea două proprietăți:

Proprietatea alegerii greedy

Putem face orice alegere pare mai bună pe moment și apoi se pot rezolva subproblemele care apar mai târziu. Alegerea făcută de către un algoritm greedy poate depinde de alegerile făcute până atunci, dar nu de viitoarele alegeri sau de toate soluțiile subproblemelor. El face iterativ o alegere greedy după alta, reducând fiecare problemă dată într-una mai mică. Cu alte cuvinte, un algoritm greedy nu își reconsideră alegerile. Aceasta este principala diferență față de programarea dinamică^⁠(d), care este exhaustivă găsește garantat soluția.

După fiecare etapă, programarea dinamică ia decizii pe baza tuturor deciziilor luate în etapa anterioară, și poate reconsidera calea găsită în etapa algoritmică anterioară.

Substructură optimă

„O problemă prezintă substructură optimă^⁠(d) dacă o soluție optimă a problemei conține soluții optime pentru subprobleme”.

Cazurile de eșec

Exemple de cum un algoritm greedy poate eșua în găsirea soluției optime

Începând din A, un algoritm greedy va găsi maximul local din m, fără a fi conștient de maximul global din M

Cu obiectivul de a ajunge la suma cea mai mare, la fiecare pas, algoritmul greedy va alege ceea ce pare a fi soluția, așa că va alege 12 în loc de 3 la pasul al doilea, și nu va ajunge niciodată la soluția optimă, care conține 99.

Pentru multe alte probleme, algoritmii greedy nu reușesc să producă soluția optimă, și poate chiar produce cea mai proastă soluție. Un exemplu este problema comis-voiajorului de mai sus: pentru orice număr de orașe, există o atribuire de distanțe între orașe pentru care euristica celui mai apropiat vecin cel mai rău ciclu posibil.

Tipuri

Algoritmii greedy pot fi caracterizați ca având „viziune scurtă”, și „nerecuperabili”. Aceștia sunt ideali doar pentru probleme care au „substructură optima”. În ciuda acestui fapt, pentru multe probleme simple (de exemplu, problema restului de bani), cei mai potriviți algoritmi sunt algoritmii greedy. Algoritmii greedy pot fi folosiți ca algoritmi de selecție pentru a prioritiza opțiuni într-o căutare, sau într-un algioritm branch-and-bound. Există câteva variante de algoritm greedy:

• Algoritmi greedy puri
• Algoritmi greedy ortogonali
• Algoritmi greedy relaxați

Aplicații

Algoritmii greedy dau greș în găsirea soluției optime globale mai ales pentru că nu operează exhaustiv pe toate datele. Ei își pot lua angajamente pentru anumite alegeri prea devreme, ceea ce îi împiedică să găsească cele mai bune soluții globale mai târziu. De exemplu, toți algoritmii greedy de colorare pentru problema colorării grafurilor și pentru toate celelalte probleme NP-complete nu găsesc în mod consistent soluții optime. Cu toate acestea, ele sunt utile, deoarece acestea fac rapid alegeri și de multe ori dau aproximări bune ale soluției optime.

Dacă se poate demonstra că un algoritm greedy dă randament global optim pentru o anumită clasă de probleme, de obicei, acesta devine metoda aleasă, pentru că este mai rapid decât alte metode de optimizare ca programarea dinamică^⁠(d). Exemple de astfel de algoritmi greedy sunt algoritmul lui Kruskal și algoritmul lui Prim pentru găsirea arborilor minimi de acoperire, și algoritmul pentru găsirea arborilor Huffman^⁠(d) optimi.

Teoria matroidelor^⁠(d), și teoria mai generală a greedoidelor^⁠(d), oferă clase întregi de astfel de algoritmi.

Algoritmii Greedy apar și în rutarea rețelelor. Folosind rutarea greedy, un mesaj este transmis nodului vecin care este „cel mai apropiat” de destinație. Noțiunea de locație a unui nod (și, prin urmare, de „apropiere”) poate fi determinată de localizarea fizică, ca în rutarea geografică^⁠(d) utilizată de către rețelele ad-hoc^⁠(d). Locația poate fi și o construcție complet artificială, ca în rutarea într-o lume mică^⁠(d) și în tabelele de dispersie distribuite^⁠(d).

Exemple

• Problema de selecție a activității^⁠(d) este caracteristică pentru această clasă de probleme, unde obiectivul este de a alege numărul maxim de activități care nu intră în conflict unele cu altele.
• În jocul Crystal Quest^⁠(d) de pe computerele Macintosh, obiectivul este de a colecta cristale, într-un mod similar cu problema comis-voiajorului. Jocul are un modul demo, unde programul folosește un algoritm greedy pentru a merge la fiecare cristal. Inteligența artificială nu ține cont de obstacole, astfel încât modul demo de multe ori se termină repede.
• Urmărirea cu potrivire^⁠(d) este un exemplu de algoritm greedy aplicat aproximării semnalelor.
• Un algoritm greedy găsește soluția optimă pentru problema lui Malfatti^⁠(d) de găsire a trei cercuri disjuncte într-un anumit triunghi care să maximizeze suprafața totală a cercurilor; se presupune că același algoritm greedy este optim pentru orice număr de cercuri.
• Un algoritm greedy este folosit pentru a construi un arbore Huffman în codificarea Huffman^⁠(d) unde găsește o soluție optimă.
• În învățarea cu arbori de decizie^⁠(d), algoritmii greedy sunt frecvent utilizați, deși nu garantează găsirea soluției optime.

Bibliografie

• Introduction to Algorithms^⁠(d) (Cormen, Leiserson, Rivest) 1990, Capitolul 17 "Greedy Algorithms" p. 329.
• Introduction to Algorithms (Cormen, Leiserson, Rivest, și Stein) 2001, Capitolul 16 "Greedy Algorithms".
• G. Gutin, A. Yeo și A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.
• J. Bang-Jensen, G. Gutin și A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121-127.
• G. Bendall și F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288-298.

Legături externe

• Hazewinkel, Michiel, ed. (2001), „Greedy algorithm”, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104 
• Greedy coin în Python exemplu de Noah Gift.