Sisällysluettelo:
Määritelmä - mitä ahne algoritmi tarkoittaa?
Ahne algoritmi on algoritminen strategia, joka tekee parhaan optimaalisen valinnan jokaisessa pienessä vaiheessa tavoitteena, että tämä lopulta johtaa globaalisti optimaaliseen ratkaisuun. Tämä tarkoittaa, että algoritmi valitsee parhaan ratkaisun tällä hetkellä ottamatta huomioon seurauksia. Se valitsee parhaan välittömän tulosteen, mutta ei ota huomioon kokonaisuutta, joten sitä pidetään ahneana.
Techopedia selittää ahnean algoritmin
Ahne algoritmi toimii valitsemalla parhaan mahdollisen vastauksen jokaisessa vaiheessa ja siirtymällä sitten seuraavaan vaiheeseen loppuun saakka, ottamatta huomioon kokonaisratkaisua. Se vain toivoo, että kulkema tie on maailmanlaajuisesti optimaalinen, mutta kuten on todettu toistuvasti, tämä menetelmä ei usein löydä globaalisti optimaalista ratkaisua. Itse asiassa on täysin mahdollista, että optimaaliset lyhytaikaiset ratkaisut johtavat pahimpaan mahdolliseen globaaliin lopputulokseen.
Ajattele sitä tekevän paljon pikavalintoja valmistusliiketoiminnassa: Lyhyellä aikavälillä suuria määriä säästyy valmistuskustannuksissa, mutta tämä johtaa lopulta laskuun, koska laatu vaarantuu, mikä johtaa tuotteen tuottoon ja alhaiseen myyntiin, kun asiakkaat tutustuvat “Halpa” tuote. Mutta näin ei aina ole, on paljon sovelluksia, joissa ahne algoritmi toimii parhaiten etsimään tai likimääräisesti maailmanlaajuisesti optimaalista ratkaisua, kuten Huffman-puun tai päätöksenteon oppimispuun rakentamisessa.
Esimerkiksi: Ota polku, jolla on suurin summa. Ahne algoritmi ottaisi lyhyen näkyvyyden seurauksena sinisen polun eikä oranssin polun, joka tuottaa suurimman summan.
komponentit:
- Ehdokas tietojoukko, joka tarvitsee ratkaisun
- Valintatoiminto, joka valitsee parhaan tekijän lopulliseen ratkaisuun
- Toteutettavuusfunktio, joka avustaa valintafunktiota määrittämällä voidaanko ehdokas osallistua ratkaisuun
- Objektiivinen toiminto, joka antaa arvon osaratkaisulle
- Ratkaisutoiminto, joka osoittaa, että optimaalinen ratkaisu on löydetty
