Informatică Algoritmi
Algoritmi greedy exemple
Algoritmii greedy sunt strategii de rezolvare a problemelor care aleg la fiecare pas cea mai bună opțiune locală, sperând să obțină soluția optimă globală. Acești algoritmi sunt simpli și eficienți pentru probleme cu proprietatea de alegere greedy și substructură optimă. Un exemplu clasic este problema rucsacului fracționar, unde se alege mereu obiectul cu cel mai mare raport valoare/greutate.
Exemple de probleme greedy
- Problema rucsacului fracționar Se dă un rucsac cu capacitate W și n obiecte cu greutăți și valori. Se pot lua fracțiuni din obiecte. Algoritmul sortează obiectele descrescător după raportul valoare/greutate și umple rucsacul în această ordine.
- Problema acoperirii cu intervale Se dă o mulțime de intervale pe o dreaptă și se cere numărul minim de puncte care intersectează toate intervalele. Algoritmul alege mereu punctul din capătul drept al intervalului curent.
- Codificarea Huffman Pentru compresia datelor, se construiește un arbore binar optim care atribuie coduri mai scurte caracterelor cu frecvențe mai mari, folosind o coadă de priorități.
Pași pentru implementare
- 1 Identifică proprietatea greedy Verifică dacă alegerea optimă locală duce la soluție globală, de exemplu prin sortare după un criteriu.
- 2 Sortează datele de intrare Pentru multe probleme, sortarea este esențială, ca în problema rucsacului, unde se ordonează obiectele.
- 3 Iterează și alege Parcurge datele sortate și la fiecare pas aplică regula greedy, cum ar fi adăugarea obiectului în rucsac dacă încape.
Testează întotdeauna dacă problema are proprietatea greedy pentru a evita soluții greșite.