dreapta|miniatura|280x280px|Determinarea numărului minim de monede cu care printr-un algoritm . 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ă 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ă.) Algoritmii formează o care urmează euristica rezolvării de probleme 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 produce, în general, o soluție optimă, dar cu toate acestea o euristică poate produce la nivel local soluții optime care aproximează o soluție optimă globală într-un timp rezonabil.

De exemplu, o strategie 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 rezolvă cu proprietăți de .

Detalii În general, algoritmii au cinci componente: O mulțime de candidați, din care se creează o soluție Funcția de selecție, care alege cel mai bun candidat pentru a fi adăugat la soluție O funcție de fezabilitate, care este folosită pentru a determina dacă un candidat poate fi utilizat pentru a contribui la o soluție O funcție obiectiv, care atribuie o valoare unei soluții sau unei soluții parțiale, și O funcție de soluție, care va indica atunci când s-a descoperit o soluție completă Algoritmii produc soluții bune la unele , dar nu la altele. Cele mai multe probleme la care funcționează vor avea două proprietăți: Proprietatea alegerii 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 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 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 , 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ă dacă o soluție optimă a problemei conține soluții optime pentru subprobleme”.Introducere în Algoritmi (Cormen, Leiserson, Rivest, și Stein) 2001, Capitolul 16 "Algoritmii Greedy".

Cazurile de eșec Pentru multe alte probleme, algoritmii 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.Comis-voiajor trebuie să nu fie lacomi: dominația analiza lacom de tip euristic pentru TSP (G. Gutin, A. Yeo și A. Zverovich, 2002)

Tipuri Algoritmii 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 . Algoritmii pot fi folosiți ca algoritmi de selecție pentru a prioritiza opțiuni într-o căutare, sau într-un algioritm . Există câteva variante de algoritm greedy: Algoritmi puri Algoritmi ortogonali Algoritmi relaxați

Aplicații Algoritmii 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 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 . 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 optimi.

Teoria , și teoria mai generală a , oferă clase întregi de astfel de algoritmi.

Algoritmii Greedy apar și în rutarea rețelelor. Folosind rutarea , 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 utilizată de către . Locația poate fi și o construcție complet artificială, ca în și în .

Exemple 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 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 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. este un exemplu de algoritm aplicat aproximării semnalelor. Un algoritm găsește soluția optimă pentru 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 este optim pentru orice număr de cercuri. Un algoritm este folosit pentru a construi un arbore Huffman în unde găsește o soluție optimă. În , algoritmii sunt frecvent utilizați, deși nu garantează găsirea soluției optime.

Note

Bibliografie (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

Greedy coin în Python exemplu de Noah Gift.

Categorie:Algoritmi