U pohlepnom algoritmu, mi donosimo bilo koji izbor koji se u ovom trenutku čini najboljim u nadi da će to dovesti do globalnog optimalnog rješenja. U dinamičkom programiranju donosimo odluku u svakom koraku uzimajući u obzir trenutni problem i rješenje prethodno riješenog podproblema kako bismo izračunali optimalno rješenje.
Koliko izvodljivih rješenja postoji u pohlepnoj metodi?
Pohlepni algoritam pravi pohlepne izbore u svakom koraku kako bi osigurao da je ciljna funkcija optimizirana. Greedy algoritam ima samo jedan udarac za izračunavanje optimalnog rješenja tako da se nikada ne vrati i poništi odluku.
Šta je koncept pohlepne metode?
Definicija: Algoritam koji uvijek uzima najbolje trenutno ili lokalno rješenje dok pronalazi odgovor. Pohlepni algoritmi pronalaze sveukupno, ili globalno, optimalno rješenje za neke probleme optimizacije, ali mogu pronaći manje od optimalnih rješenja za neke slučajeve drugih problema.
Koje su prednosti pohlepnog pristupa?
Prednost korištenja pohlepnog algoritma je u tome što rješenja za manje instance problema mogu biti jednostavna i lako razumljiva. Nedostatak je što je sasvim moguće da najoptimalnija kratkoročna rješenja mogu dovesti do najgoreg mogućeg dugoročnog ishoda.
Kada trebamo koristiti pohlepni?
U nastavku su navedeni neki problemi koji koriste optimalno rješenje koristeći Greedy pristup
- Problem trgovačkog putnika.
- Kruskalov algoritam minimalnog razapinjućeg stabla.
- Dijkstra's minimalni spanning tree algoritam.
- Problem sa rancem.
- Problem sa zakazivanjem posla.
