Problemă de selecție a activității Greedy Algo-1 - GeeksforGeeks

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

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.

---