Metoda Greedy (probleme de optimizare)

Pe scurt

Metoda Greedy este o tehnică de proiectare a algoritmilor care construiește soluția pas cu pas, alegând la fiecare pas cea mai bună opțiune locală, în speranța obținerii soluției globale optime. Pentru a fi aplicabilă, problema trebuie să respecte proprietatea de substructură optimală și proprietatea alegerii lacome. Algoritmii greedy sunt eficienți datorită complexităților temporale reduse (de obicei O(n log n) sau O(n)), dar nu garantează întotdeauna optimul global.

Definiția și principiile metodei Greedy

Metoda Greedy (sau „algoritmul lacom”) este o tehnică de proiectare a algoritmilor folosită pentru rezolvarea problemelor de optimizare. Ea presupune construirea soluției pas cu pas, alegând la fiecare pas cea mai bună alegere locală („lacomă”) în speranța că aceasta va duce la o soluție globală optimă.

Condiții de aplicabilitate:

• Proprietatea de substructură optimală – soluția optimă a problemei conține soluții optime ale subproblemelor
• Proprietatea alegerii lacome – alegerea locală optimă duce la soluția globală optimă

Atenție: Metoda Greedy nu garantează întotdeauna optimul global, de aceea trebuie demonstrat sau verificat pentru fiecare problemă.

Domenii de aplicare în informatică

Metoda Greedy este utilizată frecvent la următoarele tipuri de probleme

• Suma maximă
• Planificare optimală
• Selectarea activităților
• Problema rucsacului (varianta continuă sau fracționară)
• Probleme pe grafuri:

- Drumuri minime – algoritmul Dijkstra

Aplicații în contextul examenului de Bacalaureat

În cadrul examenului de Bacalaureat la Informatică, elevii trebuie

• Să recunoască dacă o problemă poate fi rezolvată greedy
• Să identifice criteriul de alegere locală
• Să implementeze algoritmul în pseudocod sau într-un limbaj de programare (C++/Pascal)

În practică, multe probleme de Bac se rezolvă greedy prin sortare prealabilă și apoi parcurgere secvențială cu alegerea elementelor care maximizează sau minimizează un anumit criteriu.

Concepte cheie

• Alegerea locală optimă
• Proprietatea de substructură optimală
• Sortarea datelor ca pas pregătitor
• Problema rucsacului fracționar
• Selectarea activităților
• Plata cu monede (sisteme canonice)
• Algoritmii lui Kruskal, Prim, Dijkstra ca exemple greedy
• Complexitate O(n log n) datorită sortării

Exemple clasice

Exemplul 1: Suma maximă de monede (problema plății unei sume cu număr minim de monede)

Presupunem că avem monede de valori 1, 5, 10, 25 (sistem canonic). Pentru a plăti suma S, alegem la fiecare pas cea mai mare monedă care nu depășește suma rămasă.

Exemplu practic: Pentru S=67

• Alegem 25, rămâne 42
• Alegem 25, rămâne 17
• Alegem 10, rămâne 7
• Alegem 5, rămâne 2
• Alegem 1, rămâne 1
• Alegem 1
• Total: 6 monede

Algoritmul este greedy: la fiecare pas, alegem moneda de valoare maximă posibilă. În sistemele monetare canonice (euro, dolar), această metodă dă numărul minim de monede. Se implementează prin sortarea descrescătoare a monedelor și parcurgerea lor.

Exemplul 2: Problema rucsacului fracționar (Fractional Knapsack)

Avem n obiecte, fiecare cu greutate g[i] și valoare v[i]. Capacitatea rucsacului este C. Se cere valoarea maximă care poate fi transportată, putând lua fracțiuni din obiecte.

Algoritmul:

• Sortează obiectele după raportul valoare/greutate descrescător
• Ia cât mai mult posibil din fiecare obiect până la umplerea rucsacului

Exemplu practic: Obiecte: (v=60, g=10) raport=6; (v=100, g=20) raport=5; (v=120, g=30) raport=4; C=50

• Sortate: (60,10), (100,20), (120,30)
• Se ia primul (10), rămâne 40
• Al doilea (20), rămâne 20
• Din al treilea se ia 20/30 = 2/3, valoare 80
• Total valoare = 60+100+80=240

Algoritmul este optimal pentru varianta fracționară.

Exemplul 3: Selectarea activităților (Activity Selection)

Avem n activități, fiecare cu start s[i] și sfârșit f[i]. Se cere numărul maxim de activități care pot fi desfășurate fără suprapunere (o persoană poate participa la o singură activitate la un moment dat).

Algoritmul:

• Sortează activitățile după timpul de sfârșit crescător
• Alege prima activitate (cea care se termină cel mai devreme)
• Selectează următoarea activitate al cărei timp de start este ≥ timpul de sfârșit al ultimei alese

Exemplu practic: Activități: (1,2), (2,3), (3,4), (0,5), (5,7)

• Sortate după sfârșit: (1,2), (2,3), (3,4), (0,5), (5,7)
• Se alege (1,2), apoi (2,3) (start=2≥2), apoi (3,4) (start=3≥3), apoi (5,7) (start=5≥4)
• Total: 4 activități

Metoda este optimală.

Exemplul 4: Problema calului pe tabla de șah

De pe o tablă de șah (n x n), un cal pleacă dintr-o poziție și trebuie să viziteze toate căsuțele o singură dată. Varianta greedy alege la fiecare pas mutarea cu cele mai puține opțiuni viitoare (regula lui Warnsdorff).

Verifică-te!

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

1. În problema selectării activităților, după ce criteriu se sortează activitățile înainte de aplicarea algoritmului greedy?

1. De ce algoritmii greedy au, de obicei, complexitatea O(n log n) și nu O(n²) sau mai mare?