Metoda greedy

Alegerea local optimă, de ce funcționează uneori și eșuează alteori, și cum recunoști o problemă potrivită.

Ideea

Metoda greedy construiește soluția pas cu pas, alegând la fiecare pas ce pare cel mai bun în acel moment, fără să revină niciodată asupra alegerii.

Este exact opusul backtracking-ului. Acolo încercam totul și ne întorceam, aici alegem o dată și mergem înainte. De aceea greedy este mult mai rapid, dar tot de aceea nu funcționează întotdeauna.

Unde stă față de programă. Programa de bacalaureat din 2022 nu numește metoda greedy, deci nu ți se va cere „scrieți un algoritm greedy”. Ideea apare totuși în probleme obișnuite, unde sortezi după un criteriu și parcurgi o dată. La corectare, orice rezolvare corectă se punctează, indiferent de metodă. Lecția te ajută să gândești așa, nu acoperă un capitol de examen.

Un exemplu în care merge

Plata unei sume cu bancnote de 1, 5, 10, 50, 100, folosind cât mai puține bancnote.

La fiecare pas iau cea mai mare bancnotă care încape.

int val[] = {100, 50, 10, 5, 1};

for (int i = 0; i < 5; i++) {
    int cate = s / val[i];
    if (cate > 0)
        cout << cate << " x " << val[i] << "\n";
    s = s % val[i];
}

Pentru 287: două de 100, una de 50, trei de 10, una de 5, două de 1. Nouă bancnote, și nu se poate mai bine.

Un exemplu în care nu merge

Aceeași problemă, cu bancnote de 1, 3 și 4, pentru suma 6.

Greedy ia un 4, apoi rămâne 2, deci două de 1: trei bancnote.

Soluția optimă este 3 + 3: două bancnote.

Metoda a eșuat, deși algoritmul a făcut exact ce trebuia. Cu această mulțime de valori, alegerea local optimă nu duce la optimul global.

Asta e tot ce trebuie să reții despre greedy: corectitudinea depinde de problemă, nu de program. Un algoritm greedy trebuie justificat, nu doar scris.

Probleme clasice în care greedy funcționează

Selectarea activităților

Ai n activități cu ora de început și de sfârșit. Vrei să faci cât mai multe, fără suprapuneri.

Alegerea corectă: sortezi după ora de terminare și iei fiecare activitate care începe după ce s-a terminat ultima aleasă.

// v sortat crescător după sfârșit
int ultimul = 0, cate = 0;
for (int i = 1; i <= n; i++)
    if (v[i].inceput >= ultimul) {
        cate++;
        ultimul = v[i].sfarsit;
    }

Intuiția: terminând cât mai devreme, lași cât mai mult timp liber pentru restul.

Sortarea după durată sau după ora de început nu funcționează, dă rezultate greșite. Criteriul de sortare este algoritmul.

Suma maximă cu un număr limitat de obiecte

Sortezi descrescător și iei primele k. Aici greedy este evident corect.

Ordonarea pentru timp de așteptare minim

Dacă mai mulți clienți așteaptă la un ghișeu, servirea în ordinea crescătoare a duratelor minimizează timpul total de așteptare. Un client scurt servit primul îi întârzie puțin pe toți cei de după el. Unul lung servit primul îi întârzie pe toți cu mult.

Structura oricărei soluții greedy

Aproape toate au aceeași formă:

1. Sortează după un criteriu.
2. Parcurge o dată și ia ce se poate.

Toată dificultatea stă în alegerea criteriului de sortare. Odată ce l-ai găsit, codul e banal.

Cum îți dai seama dacă merge

Nu există o rețetă, dar există un test practic bun: caută un contraexemplu mic. Ia trei-patru valori și încearcă să construiești un caz în care alegerea lacomă pierde. Dacă găsești unul, metoda nu merge. Dacă după câteva încercări serioase nu găsești, probabil merge.

Semnale că greedy nu este metoda potrivită:

• Alegerea de acum schimbă ce e disponibil mai târziu, în feluri complicate.
• Problema cere „numărul de moduri", nu un optim.
• Enunțul are limite mici (n ≤ 20), semn că se așteaptă backtracking.

Invers, limite mari (n = 10⁵) cu cerință de optim sunt un semn bun pentru greedy, uneori cu sortare la început.

Greedy față de backtracking

Când nu ești sigur că greedy e corect și n este mic, alege backtracking-ul. E mai lent, dar corect.

De reținut

• Greedy alege ce pare bun acum și nu revine.
• Funcționează doar la anumite probleme, iar corectitudinea trebuie justificată.
• Structura este mereu: sortez după un criteriu, apoi parcurg o dată.
• Criteriul de sortare este algoritmul propriu-zis.
• Caută un contraexemplu mic înainte să te bazezi pe el.
• Limite mari + cerință de optim = probabil greedy. Limite mici = probabil backtracking.