De ce contează?
Imaginează-ți că faci un trofeu din piese LEGO și ai o singură cutie de piese. Un prieten îți spune că soluția lui e cea mai înaltă posibilă. Tu nu i-ai văzut construcția, dar ai o regulă: „pun mereu cea mai înaltă piesă care încape acum". Cum îl convingi că turnul tău nu e mai scund decât al lui? Nu construind toate turnurile din lume — ci arătând că ORICE piesă din turnul lui o poți schimba cu alegerea ta fără să cobori înălțimea. Asta e exact felul în care dovedești că un algoritm greedy e corect.
Ideea-cheie
Greedy ia, la fiecare pas, alegerea care arată cel mai bine acum, fără să se mai întoarcă. E rapid și simplu. Dar tocmai pentru că nu privește în viitor, nu ai voie să te încrezi în el doar pentru că „pare logic" sau „a mers pe exemplele mele". Trebuie să dovedești că alegerea lacomă nu te costă mai târziu.
Această lecție nu îți dă un algoritm nou. Îți dă răspunsul la întrebarea: am voie să mă încred în greedy aici? Sunt două unelte de demonstrație și un test de respingere:
- Argumentul de schimb (exchange argument): presupui că există o soluție optimă diferită de a ta, apoi arăți că poți schimba o alegere a ei cu alegerea greedy fără să o înrăutățești. Repeți schimbul până când optimul devine identic cu greedy — deci greedy era și el optim.
- Greedy stays ahead („greedy rămâne în față"): arăți că după fiecare pas, soluția greedy e cel puțin la fel de bună ca orice altă soluție. Dacă nu rămâne niciodată în urmă, la final nu poate fi mai slabă.
- Contraexemplul: dacă vrei să arăți că greedy nu merge, e de ajuns UN singur caz în care dă un răspuns mai prost decât optimul.
Greedy e corect doar dacă poți DOVEDI că e corect — nu pentru că pare evident. Cele două unelte de demonstrație sunt argumentul de schimb și „greedy stays ahead". Dacă nu reușești niciuna, oprește-te și caută un contraexemplu: poate greedy chiar nu merge, și atunci ai nevoie de altă tehnică (de obicei programare dinamică).