Metoda greedy

Metoda greedy construiește soluția prin alegeri locale considerate cele mai bune la momentul respectiv. Ea este corectă numai când se poate demonstra că aceste alegeri duc la o soluție optimă globală. De exemplu, la selectarea unui număr maxim de intervale care nu se suprapun, alegerea intervalului ce se termină cel mai devreme permite loc pentru cât mai multe intervale ulterioare.

Metoda greedy construiește soluția în pași succesivi; la fiecare pas alege, dintre candidații disponibili, pe cel considerat cel mai bun după un criteriu local și nu mai revine asupra alegerii. Ea este rapidă, dar este corectă numai pentru problemele la care se poate demonstra că alegerile locale duc la un optim global. Pentru a folosi metoda se identifică criteriul de alegere, ordinea de examinare a candidaților (adesea sortarea lor după acel criteriu) și condiția de acceptare a unui candidat. Dacă pentru o problemă criteriul nu este demonstrat, algoritmul poate da un rezultat care este valid, dar nu optim.

Exemplul 1 — selectarea intervalelor compatibile. Se cere numărul maxim de intervale care nu se suprapun, dintre intervalele $[1,2]$, $[3,4]$, $[2,5]$, $[4,6]$, $[5,7]$, $[6,8]$. Criteriul corect este să se aleagă mereu intervalul care se termină cel mai devreme. Intervalele se sortează crescător după capătul drept: $[1,2]$, $[3,4]$, $[2,5]$, $[4,6]$, $[5,7]$, $[6,8]$. Se examinează în ordine:

1. $[1,2]$ se alege, iar ultimul capăt devine 2.
2. $[3,4]$ începe la 3, după capătul 2, deci se alege; ultimul capăt este 4.
3. $[2,5]$ începe la 2, înaintea lui 4, deci se respinge.
4. $[4,6]$ începe la 4, adică chiar la capătul precedent; dacă atingerea la capăt este permisă, se alege, iar ultimul capăt este 6.
5. $[5,7]$ începe la 5, înaintea lui 6, deci se respinge.
6. $[6,8]$ începe la 6 și se alege.

Se aleg patru intervale: $[1,2]$, $[3,4]$, $[4,6]$ și $[6,8]$. Alegerea după intervalul cel mai scurt sau după începutul cel mai devreme nu garantează același optim.

#include <iostream>
using namespace std;
int main() {
    int st[] = {1, 3, 2, 4, 5, 6}, dr[] = {2, 4, 5, 6, 7, 8};
    int ultim = -1, nr = 0;
    for (int i = 0; i < 6; ++i)
        if (st[i] >= ultim) {
            ++nr;
            ultim = dr[i];
        }
    cout << nr;
    return 0;
}

Intervalele sunt deja ordonate după capătul drept, iar programul afișează 4.

Exemplul 2 — restul în monede. Pentru monedele 1, 5, 10 și 50 și suma 87, greedy ia mereu cea mai mare monedă care încape: 50, apoi 10, 10, 10, apoi 5, apoi 1 și 1. Sunt 7 monede și acesta este optimul pentru acest sistem de monede.

Exemplul 3 — când greedy nu merge. Pentru monedele 1, 3 și 4 și suma 6, greedy ia 4, apoi 1 și 1, adică 3 monede. Optimul este însă 3 + 3, doar 2 monede. Alegerea locală cea mai bună (moneda cea mai mare) nu duce la optimul global. Pentru astfel de sisteme de monede se folosește programarea dinamică. Concluzia este că o soluție greedy cere o demonstrație pentru problema respectivă sau un contraexemplu care arată că nu merge.

Contraexemplu pentru criteriul „cel mai scurt interval”: din $[1,5]$, $[4,6]$ și $[5,9]$ cel mai scurt este $[4,6]$, iar alegerea lui le respinge pe celelalte două, deci rezultă un singur interval. Criteriul capătului drept ia $[1,5]$ și apoi $[5,9]$, adică două intervale.

Greșeli frecvente

• Greșit: metoda greedy dă mereu soluția optimă.
  Corect: dă optimul numai când alegerea locală este demonstrat corectă pentru problemă.
• Greșit: pentru selectarea intervalelor se alege intervalul cel mai scurt.
  Corect: criteriul corect este capătul drept cel mai mic.
• Greșit: la monede, cea mai mare monedă care încape duce la numărul minim de monede pentru orice sistem.
  Corect: pentru monedele 1, 3, 4 și suma 6 nu merge.

Înainte și după