Gramzivi algoritmi (Greedy)

Gramzivi algoritmi (eng. greedy algorithms) predstavljaju algoritamsku tehniku koja gradi rešenje tako što u svakom koraku bira najbolju lokalnu odluku u nadi da će to dovesti do globalno optimalnog rešenja.

Ideja je jednostavna: nikada se ne vraćamo unazad niti preispitujemo prethodne odluke.

Kada se koriste gramzivi algoritmi?

Ova tehnika daje dobre rezultate ako je problem takav da:

se može podeliti na nezavisne korake
svaki korak utiče samo lokalno, a ne globalno
lokalni optimum vodi ka globalnom optimumu
postoji matematički dokaz optimalnosti (često preko indukcije ili dokaza kontradikcijom)

Primeri gde je greedy uspešan: aktivnosti i intervali, Huffmanovo kodiranje, Dijkstra, Kruskal, Prim.

Primeri gde greedy obično ne radi dobro: problem ranca (knapsack), putujući trgovac (TSP).

Osnovna ideja algoritma

Greedy pristup može se zapisati na visokom nivou kao:


while (postoji moguća odluka):
    izaberi najbolju lokalnu odluku
    napravi taj korak
    ažuriraj stanje

Primer 1: Odabir aktivnosti (Activity Selection)

Imamo skup aktivnosti sa svojim vremenima početka i završetka. Želimo da odaberemo najveći broj aktivnosti koje se ne preklapaju.

Greedy rešenje: uvek biramo aktivnost koja se najranije završava.


vector> aktivnosti = {{1,4},{3,5},{0,6},{5,7},{3,9},{5,9},{6,10},{8,11}};
sort(aktivnosti.begin(), aktivnosti.end(), 
     [](auto &a, auto &b){ return a.second < b.second; });

int poslednji_kraj = -1;
int broj = 0;

for (auto &a : aktivnosti){
    if (a.first >= poslednji_kraj){
        broj++;
        poslednji_kraj = a.second;
    }
}
// rezultat: maksimalan broj nepreklapajućih aktivnosti

Ključna ideja: ako izaberemo aktivnost koja se završava najranije, ostaje nam najviše vremena za ostale.

Primer 2: Huffmanovo kodiranje

Huffmanov algoritam generiše optimalno binarno kodiranje karaktera. Strategija: u svakom koraku se biraju dva najmanje frekventna čvora i kombinuju u novi čvor.

Greedy odluka → najmanje frekvencije spajamo prve.


while (ima više od jednog čvora u listi):
    uzmi dva minimalna čvora
    spoji ih u jedan (zbir frekvencija)
    vrati novi čvor nazad u listu

Rezultat je optimalno prefiksno kodno stablo (bez preklapanja kodova).

Primer 3: Najkraći putevi — Dijkstrin algoritam

Kod neusmerenih grafova sa nenegativnim težinama, Dijkstra koristi greedy da bi u svakom koraku izabrao čvor sa najmanjom trenutnom udaljenošću.

Lokalna odluka: izaberi "najbliži" čvor koji još nije obrađen.
To vodi globalnom optimumu jer negativnih grana nema.

Prednosti i mane

Prednosti	Mane
Brz, jednostavan za implementaciju	Nema garancije optimalnosti uvek
Često najbolji izbor za real-time sisteme	Potrebno matematički dokazati ispravnost
Niski zahtevi memorije	Radi samo uz određene uslove problema

Zadaci za vežbu

Probaj sledeće:

Napisati program za razmenu kovanica minimalnim brojem apoena (ako su apoeni standardni: 1, 2, 5, 10...)
Implementirati Kruskalov algoritam za minimalno razapinjuće stablo (MST)
Napisati greedy rešenje za raspored poslova sa profitom (Interval Scheduling with Profit) i razmotriti zašto ne radi uvek

Zaključak

Greedy algoritmi su elegantni, efikasni i primenljivi u velikom broju praktičnih problema. Međutim, uvek je neophodna pažljiva analiza — ako lokalni optimum ne garantuje globalni optimum, algoritam neće dati tačno rešenje.

□ Preporučeno sledeće: Dinamičko programiranje — kada greedy ne radi