Algoritm lacom - Greedy algorithm

Algoritmii lacomi determină numărul minim de monede de dat în timp ce se fac schimbări. Aceștia sunt pașii pe care cei mai mulți oameni i-ar face pentru a emula un algoritm lacom pentru a reprezenta 36 de cenți folosind doar monede cu valori {1, 5, 10, 20}. Moneda cu cea mai mare valoare, mai mică decât modificarea rămasă datorată, este optimul local. (În general, problema schimbării necesită o programare dinamică pentru a găsi o soluție optimă; cu toate acestea, majoritatea sistemelor valutare, inclusiv euro și dolarul american, sunt cazuri speciale în care strategia lacomă găsește o soluție optimă.)

Un algoritm lacom este orice algoritm care urmează euristica rezolvării problemelor de a face alegerea optimă la nivel local în fiecare etapă. În multe probleme, o strategie lacomă nu produce o soluție optimă, dar o euristică lacomă poate produce soluții optime la nivel local care aproximează o soluție optimă la nivel global într-un timp rezonabil.

De exemplu, o strategie lacomă pentru problema vânzătorului călător (care are o mare complexitate de calcul) este următoarea euristică: „La fiecare pas al călătoriei, vizitați cel mai apropiat oraș nevizitat”. Această euristică nu intenționează să găsească cea mai bună soluție, dar se termină într-un număr rezonabil de pași; găsirea unei soluții optime la o problemă atât de complexă necesită de obicei pași nerezonabili. În optimizarea matematică, algoritmii lacomi rezolvă în mod optim problemele combinatorii având proprietățile matroizilor și dau aproximări cu factor constant problemelor de optimizare cu structura submodulară.

Specificații

În general, algoritmii lacomi au cinci componente:

1. Un set de candidați, din care se creează o soluție
2. O funcție 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 utilizată pentru a determina dacă un candidat poate fi folosit 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 când am descoperit o soluție completă

Algoritmii lacomi produc soluții bune pentru unele probleme matematice , dar nu și pentru altele. Cele mai multe probleme pentru care funcționează vor avea două proprietăți:

Proprietate lacomă

Putem face orice alegere care pare cea mai bună în acest moment și apoi rezolvăm subproblemele care apar mai târziu. Alegerea făcută de un algoritm lacom poate depinde de alegerile făcute până acum, dar nu de alegerile viitoare sau de toate soluțiile la subproblemă. Iterativ face o alegere lacomă după alta, reducând fiecare problemă dată într-una mai mică. Cu alte cuvinte, un algoritm lacom nu își reconsideră niciodată alegerile. Aceasta este principala diferență față de programarea dinamică , care este exhaustivă și garantează că va găsi soluția. După fiecare etapă, programarea dinamică ia decizii pe baza tuturor deciziilor luate în etapa anterioară și poate reconsidera calea algoritmică a etapei anterioare către soluție.

Substructură optimă

"O problemă prezintă o substructură optimă dacă o soluție optimă a problemei conține soluții optime la subprobleme."

Cazuri de eșec

Exemple despre modul în care un algoritm lacom poate să nu reușească să obțină soluția optimă.

Începând de la A, un algoritm lacom care încearcă să găsească maximul urmând cea mai mare pantă va găsi maximul local la "m", ignorând maximul global la "M".

Pentru a ajunge la cea mai mare sumă, la fiecare pas, algoritmul lacom va alege ceea ce pare a fi alegerea imediată optimă, deci va alege 12 în loc de 3 la al doilea pas și nu va ajunge la cea mai bună soluție, care conține 99.

Algoritmii lacomi nu reușesc să producă soluția optimă pentru multe alte probleme și pot produce chiar și cea mai proastă soluție unică . Un exemplu este problema vânzătorului călător menționat mai sus: pentru fiecare număr de orașe, există o atribuire a distanțelor între orașe pentru care euristica cea mai apropiată-vecină produce cel mai rău tur posibil unic. Pentru alte exemple posibile, a se vedea efectul orizont .

Tipuri

Algoritmii lacomi pot fi caracterizați ca fiind „miopi” și, de asemenea, ca „nerecuperabili”. Ele sunt ideale numai pentru problemele care au o „substructură optimă”. În ciuda acestui fapt, pentru multe probleme simple, algoritmii cei mai potriviți sunt lacomi. Cu toate acestea, este important să rețineți că algoritmul lacom poate fi folosit ca algoritm de selecție pentru a prioritiza opțiunile dintr-o căutare sau algoritmul ramificat și legat. Există câteva variații ale algoritmului lacom:

• Algoritmi lăcomi puri
• Algoritmi lăcomi ortogonali
• Algoritmi lacomi relaxați

Teorie

Algoritmii lacomi au o lungă istorie de studiu în optimizarea combinatorie și informatică teoretică . Se știe că euristicile lacome produc rezultate suboptimale pentru multe probleme și, prin urmare, întrebările naturale sunt:

• Pentru ce probleme funcționează optim algoritmii lacomi?
• Pentru ce probleme algoritmii lacomi garantează o soluție aproximativ optimă?
• Pentru ce probleme este garantat algoritmul lacom să nu producă o soluție optimă?

Există un corp larg de literatură care răspunde la aceste întrebări pentru clase generale de probleme, cum ar fi matroidele , precum și pentru probleme specifice, cum ar fi acoperirea setată .

Matroizi

Un matroid este o structură matematică care generalizează noțiunea de independență liniară de la spații vectoriale la seturi arbitrare. Dacă o problemă de optimizare are structura unui matroid, atunci algoritmul lacom adecvat îl va rezolva în mod optim.

Funcții submodulare

O funcție definită pe subseturi ale unui set se numește submodulară dacă pentru fiecare avem asta . ${\ displaystyle f}$${\ displaystyle \ Omega}$${\ displaystyle S, T \ subseteq \ Omega}$${\ displaystyle f (S) + f (T) \ geq f (S \ cup T) + f (S \ cap T)}$

Să presupunem că cineva dorește să găsească un set care să maximizeze . Algoritmul lacom, care construiește un set prin adăugarea incrementală a elementului care crește cel mai mult la fiecare pas, produce ca ieșire un set care este cel puțin . Adică, lacomul funcționează într-un factor constant la fel de bun ca soluția optimă. ${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle (1-1 / e) \ max _ {X \ subseteq \ Omega} f (X)}$${\ displaystyle (1-1 / e) \ aproximativ 0,63}$

Garanții similare pot fi dovedite atunci când constrângeri suplimentare, cum ar fi constrângeri de cardinalitate, sunt impuse asupra rezultatului, deși sunt deseori ușoare variații ale algoritmului lacom. A se vedea pentru o prezentare generală.

Alte probleme cu garanții

Alte probleme pentru care algoritmul lacom oferă o garanție puternică, dar nu o soluție optimă, includ

• Setează capacul
• Problema copacului Steiner
• Echilibrarea sarcinii
• Set independent

Multe dintre aceste probleme se potrivesc cu limite inferioare; adică algoritmul lacom nu are o performanță mai bună decât garanția în cel mai rău caz.

Aplicații

Algoritmii lacomi de obicei (dar nu întotdeauna) nu reușesc să găsească soluția optimă la nivel global, deoarece de obicei nu funcționează exhaustiv asupra tuturor datelor. Aceștia își pot angaja prea devreme anumite alegeri, împiedicându-i să găsească ulterior cea mai bună soluție generală. De exemplu, toți algoritmii de colorat lacomi cunoscuți pentru problema colorării graficului și toate celelalte probleme NP-complete nu găsesc în mod consecvent soluții optime. Cu toate acestea, ele sunt utile, deoarece se gândesc rapid și oferă adesea aproximări bune la optim.

Dacă se poate dovedi că un algoritm lacom produce randamentul optim global pentru o anumită clasă de probleme, acesta devine de obicei metoda de alegere, deoarece este mai rapid decât alte metode de optimizare, cum ar fi programarea dinamică . Exemple de astfel de algoritmi lacome sunt algoritmul lui Kruskal si algoritmul lui Prim pentru identificarea arborilor minime se întinde și algoritmul pentru identificarea optime arbori Huffman .

Algoritmii lacomi apar și în rutare de rețea . Folosind rutare lacomă, un mesaj este redirecționat către nodul vecin care este „cel mai aproape” de destinație. Noțiunea de locație a unui nod (și, prin urmare, „apropierea”) poate fi determinată de locația sa fizică, ca și în rutare geografică utilizată de rețelele ad hoc . Locația poate fi, de asemenea, o construcție complet artificială, ca în cazul rutării lumii mici și a tabelului hash distribuit .

Exemple

• Problema de selectare a activității este caracteristică acestei clase de probleme, unde scopul este de a alege numărul maxim de activități care nu se ciocnesc între ele.
• În jocul pe computer Macintosh Crystal Quest , obiectivul este de a colecta cristale, într-un mod similar cu problema vânzătorului călător . Jocul are un mod demo, unde jocul folosește un algoritm lacom pentru a merge la fiecare cristal. Inteligența artificială nu ține cont de obstacole, astfel încât modul demo se termină de multe ori rapid.
• Exercitarea de potrivire este un exemplu de un algoritm greedy aplicat pe aproximare a semnalului.
• Un algoritm lacom găsește soluția optimă la problema lui Malfatti de a găsi trei cercuri disjuncte într-un triunghi dat care maximizează aria totală a cercurilor; se presupune că același algoritm lacom este optim pentru orice număr de cercuri.
• Un algoritm lacom este folosit pentru a construi un copac Huffman în timpul codificării Huffman unde găsește o soluție optimă.
• În învățarea arborelui decizional , algoritmii lacomi sunt utilizați în mod obișnuit, totuși nu li se garantează că vor găsi soluția optimă.
  • Un astfel de algoritm popular este algoritmul ID3 pentru construcția arborelui decizional.
• Algoritmul lui Dijkstra și algoritmul de căutare A * înrudit sunt algoritmi lăcomi optimi verificabili pentru căutarea graficului și găsirea celei mai scurte căi .
  • O căutare * este optimă condițional, necesitând o „ euristică admisibilă ” care nu va supraestima costurile parcursului.
• Algoritmul lui Kruskal si algoritmul lui Prim sunt algoritmi lacomi pentru construirea arborilor minime se întinde de la un anumit grafic conectat . Ei găsesc întotdeauna o soluție optimă, care poate să nu fie unică în general.

Vezi si

Referințe

Surse

linkuri externe

• „Algoritm lacom” , Enciclopedia Matematicii , EMS Press , 2001 [1994]
• Cadou, Noe. "Exemplu de monedă lacomă Python" .