Ahneessa algoritmissa tekemme minkä tahansa valinnan, joka näyttää tällä hetkellä parha alta siinä toivossa, että se johtaa globaaliin optimaaliseen ratkaisuun. Dynaamisessa ohjelmoinnissa teemme päätöksen jokaisessa vaiheessa ottaen huomioon nykyisen ongelman ja ratkaisun aiemmin ratkaistuun osaongelmaan optimaalisen ratkaisun laskemiseksi.
Kuinka monta toteuttamiskelpoista ratkaisua ahneella menetelmällä on?
Ahne algoritmi tekee ahneita valintoja jokaisessa vaiheessa varmistaakseen, että tavoitefunktio on optimoitu. Greedy-algoritmilla on vain yksi laukaus optimaalisen ratkaisun laskemiseksi, jotta se ei koskaan palaa takaisin ja käännä päätöstä.
Mikä on ahneen menetelmän käsite?
Määritelmä: Algoritmi, joka löytää aina parhaan välittömän tai paikallisen ratkaisun etsiessään vastausta. Ahneet algoritmit löytävät yleisen tai maailmanlaajuisesti optimaalisen ratkaisun joihinkin optimointiongelmiin, mutta voivat löytää vähemmän kuin optimaalisia ratkaisuja joihinkin muihin ongelmiin.
Mitä etuja ahneesta lähestymistavasta on?
Ahneen algoritmin käytön etuna on, että pienempien ongelmatapahtumien ratkaisut voivat olla yksinkertaisia ja helppoja ymmärtää. Haittapuolena on, että on täysin mahdollista, että optimaaliset lyhyen aikavälin ratkaisut voivat johtaa pahimpaan mahdolliseen pitkän aikavälin tulokseen.
Milloin meidän tulee käyttää ahnetta?
Alla mainittuja ongelmia, jotka käyttävät optimaalista ratkaisua Greedy-lähestymistapaa käyttäen
- Matkustava myyjäongelma.
- Kruskalin minimaalisen virittävän puun algoritmi.
- Dijkstran minimaalisen virittävän puun algoritmi.
- Reppuongelma.
- Työn ajoitusongelma.
