Kazalo:
Opredelitev - Kaj pomeni pohlepni algoritem?
Pohlepni algoritem je algoritmična strategija, ki omogoča najboljšo optimalno izbiro na vsaki majhni stopnji s ciljem, da na koncu pripelje do globalno optimalne rešitve. To pomeni, da algoritem trenutno izbere najboljšo rešitev, ne glede na posledice. Izbira najboljši takojšnji rezultat, vendar ne upošteva velike slike, zato velja za pohlepno.
Tehopedija razlaga pohlepni algoritem
Pohlepni algoritem deluje tako, da v vsakem koraku izbere najboljši možni odgovor in nato nadaljuje na naslednji korak, dokler ne pride do konca, ne glede na celotno rešitev. Upamo le, da je pot, ki jo vodi, globalno optimalna, vendar kot vedno znova dokazano, ta metoda ne predstavlja pogosto globalno optimalne rešitve. Pravzaprav je povsem mogoče, da najbolj optimalne kratkoročne rešitve vodijo do najslabšega možnega globalnega izida.
Zamislite si to kot uživanje veliko bližnjic v proizvodnem podjetju: kratkoročno se velike količine prihranijo pri proizvodnih stroških, vendar to sčasoma privede do padca, saj je kakovost ogrožena, kar ima za posledico donosnost izdelkov in nizko prodajo, ko se kupci seznanijo z “Poceni” izdelek. Vendar to ni vedno tako, obstaja ogromno aplikacij, kjer pohlepni algoritem najbolje deluje pri iskanju ali približevanju globalno optimalne rešitve, na primer pri gradnji Huffmanovega drevesa ali drevesa za odločanje o učenju.
Na primer: vzemite pot z največjo skupno vsoto. Pohlepni algoritem bi zaradi kratkovidnosti namesto oranžne poti sprejel modro pot, ki da največjo vsoto.
Sestavni deli:
- Kandidatni niz podatkov, ki potrebuje rešitev
- Izbirna funkcija, ki izbere najboljšega, ki prispeva k končni rešitvi
- Funkcionalna funkcija, ki pomaga izbirni funkciji tako, da ugotovi, ali lahko kandidat prispeva k rešitvi
- Objektivna funkcija, ki delni rešitvi dodeli vrednost
- Funkcija rešitve, ki kaže, da je bila odkrita optimalna rešitev
