Pohlepni algoritam

Pohlepni algoritam je algoritam koji koristi metaheuristiku za rešavanje problema, takvu da u svakom ponavljanju postupka bira lokalno najbolje rešenje, u nadi da će tako konačno iznaći globalni optimum.

Na primer, primena strategije pohlepnog algoritma na Problem trgovačkog putnika daje sledeći algoritam: U svakom koraku poseti neposećeni grad koji je najbliži trenutnom gradu.

Skup kandidata, iz koga se nalazi rešenje
Funkcija izbora, koja bira najboljeg kandidata za dodavanje u rešenje
Funkcija izvodljivosti, koja proverava da li se kandidat može iskoristiti da doprinese rešenju
Objektivna funkcija, koja dodeljuje vrednost rešenju, ili parcijalnom rešenju, i
Funkcija rešenja, koja pokazuje kada smo došli do kompletnog rešenja

Pohlepni algoritmi daju dobra rešenja za neke matematičke probleme, ali za neke druge nisu pogodni. Većina problema za koje ova strategija daje dobre rezultate ima dva svojstva:

Svojstvo pohlepnog izbora: Možemo da napravimo koji god izbor u datom trenutku a da izgleda najbolji, i zatim da rešimo podprobleme koji se kasnije javljaju. Izbor koji smo načinili može da zavisi od prethodnih izbora, ali ne i od narednih izbora ili svih rešenja potproblema. Iterativno pravimo jedan pohlepni izbor za drugim, i svodimo svaki dati problem na manji problem. Drugim rečima, pohlepni algoritam nikada ne preispituje svoje izbore. To je glavna razlika u odnosu na dinamičko programiranje, koje je temeljnije, i garantuje pronalaženje rešenja. U svakom koraku, dinamičko programiranje daje zaključke bazirane na svim zaključcima u prethodnom koraku, i može da preispita altorigamski put do rešenja prethodnog koraka.

Optimalna struktura: Problem ima optimalnu strukturu ako optimalno rešenje problema sadrži optimalna rešenja potproblema.

Kada strategija pohlepnih algoritama nije dobra: Za mnoge druge probleme, pohlepni algoritmi mogu biti pogrešan izbor strategije. Recimo, u partiji šaha, pohlepni algoritam će uvek odigrati onaj potez koji izgleda najbolje u datom trenutku, ne obazirući se na njegove posledice. Na primer, ukoliko najveću vrednost za igrača u datoj situaciji ima potez u kome on uzima protivničkog lovca, on će to i učiniti, sve i ako taj potez otvara protivniku mogućnost da matira igrača.

Primene[uredi | uredi izvor]

Za većinu problema, pohlepni algoritmi uglavnom (ali ne i uvek) neće uspeti da nađu globalno optimalno rešenje, jer oni obično ne obrađuju temeljno sve mogućnosti. Ovi algoritmi vrlo rano donose određene odluke, koje ih mogu sprečiti da kasnije nađu najbolje rešenje. Na primer, svi poznati pohlepni algoritmi za problem bojenja grafa i sve ostale NP-kompletne probleme, ne nalaze uvek optimalna rešenja. Pa ipak, oni su korisni, jer su u stanju da brzo daju dobru aproksimaciju optimalnog rešenja.

Ako se može dokazati da pohlepni algoritam nalazi globalni optimum za datu klasu problema, on se obično i koristi, jer je brži od ostalih optimizacionih metoda, kao što je dinamičko programiranje. Primeri takvih pohlepnih algoritama su Kruskalov algoritam i Primov algoritam za nalaženje minimalnog obuhvatnog stabla, Dijkstrin algoritam za nalaženje najkraćih puteva u grafu iz jednog početka, algoritam za nalaženje optimalnog Hafmanovog stabla, kao i algoritam za rešenje problema izbora aktivnosti.

Literatura[uredi | uredi izvor]

Introduction to Algorithms (Cormen, Leiserson, and Rivest) 1990, Chapter 17 "Greedy Algorithms" pp. 329.
Introduction to Algorithms (Cormen, Leiserson, and Rivest) 2001, Chapter 16 "Greedy Algorithms" .
G. Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.
J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121-127.
G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288-298.

Spoljašnje veze[uredi | uredi izvor]