Metoda Greedy (probleme de optimizare)

Pe scurt

Metoda Greedy este o tehnică de programare care alege la fiecare pas opțiunea local optimă, în speranța că aceasta va conduce la soluția global optimă. Algoritmul face o alegere care pare cea mai bună în momentul curent, fără a reconsidera deciziile anterioare, iar corectitudinea sa este garantată doar pentru problemele care respectă proprietatea de substructură optimală și alegerea greedy.

Ce este metoda Greedy

Metoda Greedy (lacomă) este o tehnică de programare utilizată pentru rezolvarea problemelor de optimizare. Ea constă în alegerea la fiecare pas a opțiunii locale optimale (cea mai bună din momentul respectiv) în speranța că aceasta va conduce la soluția global optimă.

Această abordare este eficientă deoarece, de multe ori, complexitatea sa este polinomială (de obicei O(n log n) sau O(n)), dar nu garantează întotdeauna optimul global.

Proprietăți necesare pentru corectitudine

Doar problemele care respectă următoarele două proprietăți sunt rezolvate corect prin metoda Greedy:

• Proprietatea de substructură optimală – soluția optimă a problemei conține soluțiile optime ale subproblemelor
• Alegerea greedy – decizia locală este consistentă cu optimul global

Pentru a aplica corect metoda, trebuie demonstrată corectitudinea algoritmului, de obicei prin inducție sau prin tehnica schimbului (exchange argument).

Concepte cheie

• Optim local vs. optim global
• Proprietatea de substructură optimală
• Alegerea greedy (criteriu de selecție)
• Tehnica schimbului (exchange argument) pentru demonstrarea corectitudinii

Aplicații clasice

Problema spectacolelor

Avem n spectacole, fiecare cu timp de început și sfârșit. Se dorește selectarea unui număr maxim de spectacole care nu se suprapun.

Algoritmul greedy:

• Sortează spectacolele după timpul de sfârșit (crescător)
• Alege primul spectacol (cel care se termină cel mai devreme)
• Elimină toate spectacolele care se suprapun cu acesta (încep înainte de sfârșitul lui)
• Repetă

Explicație: prin alegerea celui care se termină cel mai devreme, lăsăm cât mai mult timp pentru restul.

Exemplu: spectacolele (1,3), (2,5), (4,6), (5,7)

• După sortare după sfârșit: (1,3), (2,5), (4,6), (5,7)
• Alegem (1,3) – eliminăm (2,5) deoarece începe la 2 < 3
• Alegem (4,6) – eliminăm (5,7)
• Rezultat: 2 spectacole

Problema rucsacului fracționar

Avem un rucsac de capacitate C și n obiecte, fiecare cu greutatea g_i și valoarea v_i. Se poate lua orice fracțiune dintr-un obiect. Se cere valoarea maximă transportată.

Algoritmul greedy:

• Calculează raportul valoare/greutate pentru fiecare obiect
• Sortează descrescător după acest raport
• Parcurge obiectele și ia cât mai mult posibil (integral sau fracționar) până la umplerea rucsacului

Exemplu: C=10, obiecte: (v=60, g=10, raport=6), (v=100, g=20, raport=5), (v=120, g=30, raport=4)

• Sortate: primul (60,10), al doilea (100,20), al treilea (120,30)
• Luăm primul întreg (10 kg, 60 valoare), rămâne capacitate 0
• Valoare totală = 60

Alt exemplu: C=50

• Luăm primul (10), al doilea (20) și 20 din al treilea (80 valoare)
• Total: 60+100+80 = 240

Problema monedelor (sistem canonic)

Se dă o sumă S și monede cu valori 1, 5, 10, 50, 100. Găsiți numărul minim de monede.

Algoritmul greedy: alege cât mai multe monede de valoare mare care nu depășesc suma rămasă.

Exemplu: S=178

• 1 monedă de 100 (rest 78)
• 1 de 50 (rest 28)
• 2 de 10 (rest 8)
• 1 de 5 (rest 3)
• 3 de 1 (rest 0)
• Total monede: 1+1+2+1+3 = 8

Acest sistem este canonic, deci soluția este optimă.

Limitări importante

• Metoda Greedy nu funcționează pentru problema rucsacului 0/1 (cu obiecte indivizibile) decât în cazuri particulare; acolo se folosește programare dinamică
• Metoda trebuie aplicată doar când este garantată optimalitatea

Exemplu de eșec: pentru monede de 1, 3, 4, suma 6

• Greedy alege 4, apoi 1, apoi 1 (3 monede)
• Soluția optimă este 3+3 (2 monede)

Verifică-te!

1. Care sunt cele două proprietăți pe care trebuie să le respecte o problemă pentru a fi rezolvată corect prin metoda Greedy?

1. În problema spectacolelor, după ce criteriu se sortează spectacolele în algoritmul greedy?

1. De ce metoda Greedy nu funcționează pentru problema rucsacului 0/1, dar funcționează pentru varianta fracționară?