De ce contează?
Ești la bufetul cu autoservire, ai o singură farfurie și vrei s-o umpli cât mai gustos. Nu analizezi tot meniul și toate combinațiile posibile — la fiecare pas iei felul care arată cel mai bine ACUM și mergi mai departe, fără să te uiți înapoi. Uneori iese o farfurie perfectă. Alteori îți dai seama prea târziu că, dacă ai fi sărit peste tort, ar fi încăput și friptura. Exact așa gândește metoda greedy: alege ce e mai bun pe moment și nu se mai răzgândește — uneori câștigă, alteori se blochează cu o alegere pe care n-o mai poate retrage.
Ce este
Metoda greedy (lacomă) este o strategie de rezolvare în care construiești soluția pas cu pas, iar la fiecare pas faci alegerea care pare cea mai bună în acel moment — alegerea local-optimă. Odată făcută, nu o mai reconsideri niciodată: greedy nu revine, nu testează alternative, nu dă înapoi.
Schema generală are mereu aceeași formă:
- ai un set de candidați și un criteriu „ce e cel mai bun acum”;
- cât timp soluția nu e completă, iei candidatul cel mai bun valid;
- îl adaugi la soluție și nu te mai întorci asupra lui.
Greedy e atractiv pentru că e simplu și rapid: de obicei sortezi candidații după criteriu, apoi îi parcurgi o singură dată. Problema e că nu orice problemă se lasă rezolvată așa.
Greedy = alegi mereu optimul local și nu revii niciodată asupra deciziei. Această strategie dă răspunsul corect doar atunci când optimul local duce garantat la optimul global — proprietate care se numește proprietatea greedy. Dacă proprietatea nu ține, greedy se mișcă repede... către un răspuns greșit.