Informatică Algoritmi
Ce este un algoritm greedy?
Un algoritm greedy este o tehnică de proiectare a algoritmilor care la fiecare pas alege cea mai bună opțiune disponibilă local, fără a lua în considerare consecințele globale. Această abordare simplifică rezolvarea problemelor prin decizii imediate, dar nu garantează întotdeauna soluția optimă. Se aplică în probleme de optimizare unde alegerea locală duce la rezultatul global cel mai bun.
Caracteristici principale
- Alegere locală La fiecare pas, algoritmul selectează varianta cu cel mai mare beneficiu imediat, fără a analiza toate posibilitățile viitoare.
- Nerecursivitate Deciziile sunt irevocabile; odată luate, nu se revine asupra lor, ceea ce reduce complexitatea timpului de execuție.
- Optim local vs. global Soluția poate fi optimă doar pentru unele probleme, cum ar fi problema rucsacului fracționar, dar eșuează în altele, ca problema comis-voiajorului.
Exemple de aplicații
- Problema rucsacului fracționar Se alege obiectul cu cel mai mare raport valoare/greutate la fiecare pas, asigurând profitul maxim.
- Codificarea Huffman Se construiește un arbore binar prin combinarea celor mai mici frecvențe, optimizând compresia datelor.
- Problema acoperirii cu intervale Se selectează intervalele care se termină cel mai devreme pentru a acoperi o mulțime de puncte cu număr minim de intervale.
Folosește algoritmi greedy pentru probleme simple unde alegerea locală e suficientă; verifică întotdeauna dacă soluția e optimă global.