Folosim cookie-uri pentru a vă asigura că aveți cea mai bună experiență de navigare pe site-ul nostru. Prin utilizarea site-ului nostru, recunoașteți că ați citit și înțeles Politica noastră privind cookie-urile și politica de confidențialitate

selecție

Greedy este o paradigmă algoritmică care construiește o soluție bucată cu bucată, alegând întotdeauna următoarea piesă care oferă cel mai evident și imediat beneficiu. Algoritmii lacomi sunt utilizați pentru probleme de optimizare. O problemă de optimizare poate fi rezolvată folosind Greedy dacă problema are următoarea proprietate: La fiecare pas, putem face o alegere care arată cel mai bine în acest moment și obținem soluția optimă a problemei complete.
Dacă un algoritm Greedy poate rezolva o problemă, atunci devine, în general, cea mai bună metodă pentru a rezolva această problemă, deoarece algoritmii Greedy sunt, în general, mai eficienți decât alte tehnici precum Programarea dinamică. Dar algoritmii Greedy nu pot fi întotdeauna aplicați. De exemplu, problema Fractional Knapsack (Vezi acest lucru) poate fi rezolvată folosind Greedy, dar 0-1 Backpack nu poate fi rezolvată folosind Greedy.

Următoarele sunt câteva algoritmi standard care sunt algoritmi Greedy.
1) Arborele minim de întindere (MST) al lui Kruskal: În algoritmul lui Kruskal, creăm un MST prin alegerea marginilor una câte una. Greedy Choice este de a alege cea mai mică margine de greutate care nu provoacă un ciclu în MST construit până acum.
2) Arborele minim de întindere al lui Prim: De asemenea, în algoritmul lui Prim, creăm un MST prin alegerea marginilor una câte una. Menținem două seturi: un set de vârfuri deja incluse în MST și setul de vârfuri care nu sunt încă incluse. Greedy Choice este de a alege cea mai mică margine de greutate care leagă cele două seturi.

3) Cea mai scurtă cale a lui Dijkstra: Algoritmul Dijkstra este foarte similar cu algoritmul lui Prim. Cel mai scurt arbore de cale este construit, margine cu margine. Menținem două seturi: un set de vârfuri deja incluse în arbore și setul de vârfuri care nu sunt încă incluse. Greedy Choice este de a alege marginea care leagă cele două seturi și se află pe cea mai mică cale de greutate de la sursă la set, care conține vârfuri neincluse încă.
4) Codificare Huffman: Codificarea Huffman este o tehnică de compresie fără pierderi. Atribuie coduri de biți de lungime variabilă diferitelor caractere. Greedy Choice este de a atribui cel mai mic cod de lungime de biți celui mai frecvent caracter.

Algoritmii lacomi sunt uneori folosiți și pentru a obține o aproximare a problemelor de optimizare Hard. De exemplu, Traveling Salesman Problem este o problemă NP-Hard. O alegere lacomă pentru această problemă este de a alege cel mai apropiat oraș nevizitat din orașul actual la fiecare pas. Aceste soluții nu produc întotdeauna cea mai bună soluție optimă, dar pot fi folosite pentru a obține o soluție aproximativ optimă.

Să considerăm problema de selectare a activității ca primul nostru exemplu de algoritmi Greedy. Urmează declarația problemei.
Vi se oferă n activități cu timpul lor de început și de sosire. Selectați numărul maxim de activități care pot fi efectuate de o singură persoană, presupunând că o persoană poate lucra doar la o singură activitate la un moment dat.
Exemplu:

Opțiunea lacomă este să alegeți întotdeauna următoarea activitate, al cărei timp de finalizare este cel mai mic dintre activitățile rămase, iar timpul de început este mai mare sau egal cu timpul de finalizare al activității selectate anterior. Putem sorta activitățile în funcție de timpul lor de finalizare, astfel încât să considerăm întotdeauna următoarea activitate ca activitate de timp minim de finalizare.

1) Sortează activitățile în funcție de timpul lor de finalizare
2) Selectați prima activitate din matricea sortată și imprimați-o.
3) Faceți următoarele pentru activitățile rămase în matricea sortată.
…… .a) Dacă ora de începere a acestei activități este mai mare sau egală cu timpul de finalizare a activității selectate anterior, selectați această activitate și imprimați-o.

În următoarea implementare C, se presupune că activitățile sunt deja sortate în funcție de timpul lor de finalizare.