Sadržaj:
Definicija - Što znači pohlepni algoritam?
Pohlepni algoritam je algoritamska strategija koja donosi najbolji optimalan izbor u svakoj maloj fazi s ciljem da na kraju dovede do globalno optimalnog rješenja. To znači da algoritam odabire trenutno najbolje rješenje bez obzira na posljedice. Odabire najbolji neposredni rezultat, ali ne uzima u obzir veliku sliku, stoga se smatra pohlepnom.
Tehopedija objašnjava pohlepni algoritam
Pohlepni algoritam djeluje tako da odabere najbolji mogući odgovor u svakom koraku i pređe na sljedeći korak dok ne dođe do kraja, bez obzira na cjelokupno rješenje. Nada se samo da je put koji je krenuo globalno optimalan, ali kao što se iznova i iznova dokazalo, ova metoda često ne nudi globalno optimalno rješenje. U stvari, posve je moguće da najoptimalnija kratkoročna rješenja dovedu do najgoreg mogućeg globalnog ishoda.
Zamislite to kao uzimajući puno prečaca u proizvodnom poslu: kratkoročno se velike količine štede na troškovima proizvodnje, ali to na kraju dovodi do pada jer je kvaliteta ugrožena, što rezultira povratima proizvoda i niskom prodajom kako su kupci upoznati sa "Jeftini" proizvod. Ali to nije uvijek slučaj, postoji puno aplikacija u kojima pohlepni algoritam najbolje radi na pronalaženju ili približavanju globalno optimalnog rješenja, poput izrade Huffmanovog stabla ili stabla učenja odluka.
Na primjer: uzmite put s najvećim ukupnim zbrojem. Pohlepni algoritam uzeo bi plavi put, kao rezultat kratkog vida, umjesto narančaste staze, koja daje najveći zbroj.
komponente:
- Kandidatski skup podataka za koji treba rješenje
- Funkcija odabira koja odabira najboljeg koji doprinosi konačnom rješenju
- Funkcija izvedivosti koja pomaže funkciji odabira utvrđivanjem može li kandidat pridonijeti rješenju
- Objektivna funkcija koja djelomičnom rješenju dodjeljuje vrijednost
- Funkcija rješenja koja ukazuje na to da je pronađeno optimalno rješenje
