De ce contează?
Un truc de magie pare corect până când cineva îți arată unde e păcăleala. La fel cu Greedy: o strategie lacomă pare evident bună — până dai peste un caz care o dărâmă. Înainte să te bazezi pe ea, fă-i tu însuți „proba": caută păcăleala sau convinge-te că nu există.
De ce e nevoie de justificare
Greedy e seducător: simplu, rapid, „evident". Dar „evident" nu înseamnă „corect". Pe multe probleme, alegerea locală optimă ratează optimul global. Înainte să implementezi o strategie Greedy, fă-i una dintre cele două probe: caută un contraexemplu sau argumentează că merge.
Proba rapidă: caută un contraexemplu
Un singur caz în care Greedy ratează optimul îi dărâmă corectitudinea. E cel mai ieftin test: încearcă cazuri mici, „rele", înainte să scrii cod.
Exemplu: monede , rest 6. Greedy (cea mai mare monedă) dă 4+1+1 = 3 monede; optimul e 3+3 = 2. Contraexemplul găsit → strategia Greedy „cea mai mare monedă" e greșită pe acest sistem.
Asimetrie importantă: ca să infirmi un Greedy ai nevoie de un singur contraexemplu. Ca să-l confirmi, ai nevoie de un argument care acoperă toate cazurile. De aceea cauți întâi contraexemplul — e mult mai rapid.
Proba că merge: argumentul de schimb
Dacă nu găsești contraexemplu, justifici intuitiv. Cel mai folosit e argumentul de schimb:
Iei o soluție optimă oarecare. Arăți că prima ei alegere poate fi înlocuită cu alegerea Greedy fără să înrăutățească rezultatul. Repetând, soluția optimă se transformă în cea Greedy — deci Greedy e la fel de bun.
La selecția activităților: orice soluție optimă o poate înlocui pe prima ei activitate cu cea care se termină cel mai devreme (alegerea Greedy), fără să piardă activități. Deci Greedy e optim.
Proba „rămâne în frunte"
O variantă: arăți că, la fiecare pas, soluția Greedy e cel puțin la fel de bună ca orice altă soluție parțială (e mereu „în frunte"). Dacă rămâne în frunte tot timpul, e optimă la final.
Nu-ți trebuie o demonstrație formală riguroasă la concurs — îți trebuie un argument intuitiv solid care te convinge că alegerea locală nu strică optimul. Dacă nu reușești să-l schițezi, e un semnal că Greedy s-ar putea să fie greșit.
Când Greedy nu e suficient
Dacă alegerile se influențează reciproc (o alegere bună acum poate închide o opțiune mai bună mai târziu, și nu poți argumenta schimbul), Greedy cedează. Acolo intervine programarea dinamică, care explorează combinațiile fără să se angajeze prematur.
De reținut (recapitulare)
| Pas | Ce faci |
|---|---|
| 1 | Formulezi strategia lacomă (ce alegi la fiecare pas) |
| 2 | Cauți un contraexemplu mic |
| 3 | Dacă rezistă, schițezi un argument (schimb / rămâne în frunte) |
| 4 | Dacă nici argumentul nu merge, treci la altă metodă (DP) |
Capcane reale la justificarea unui Greedy:
- Implementezi fără să verifici: „pare corect" nu e o demonstrație. Mulți pierd puncte pe un Greedy plauzibil dar greșit.
- Generalizezi din câteva exemple: că merge pe 3 cazuri mici nu garantează corectitudinea. Cauți activ cazul „rău".
- Confunzi optimul local cu cel global: alegerea cea mai bună de moment nu e mereu parte din soluția optimă.
- Renunți prea repede la contraexemplu: uneori el e mic și evident — încearcă valori „nepotrivite" (monede necanonice, intervale care se înghit).
De reținut
- Un singur contraexemplu infirmă un Greedy; caut-l înainte de a implementa.
- Dacă rezistă, justifică prin argumentul de schimb sau „rămâne în frunte".
- Dacă nu poți argumenta, alegerile probabil se influențează → treci la programare dinamică.