Ahneusalgoritmit ovat eräänlainen algoritminen strategia, joka tekee optimaalisen valinnan jokaisessa vaiheessa toive löytää globaali optimaalinen. Niitä käytetään laajalti ratkaista optimointi ongelmia, joissa paikalliset päätökset johtavat maailmanlaajuisesti optimaalinen ratkaisu. Tämä artikkeli tutkii käsitettä ahneus algoritmeja, tarjoaa käytännön esimerkkejä, ja osoittaa, miten suorittaa liittyviä laskelmia.

Mitä ovat Ahneus-algoritmit?

Ahne algoritmi rakentaa ratkaisu pala palalta, aina valitsemalla seuraavan palan, joka tarjoaa välittömimmän hyödyn. Tämä lähestymistapa on yksinkertainen ja tehokas, mutta ei aina takaa parasta yleistä ratkaisua kaikkiin ongelmiin. Se on tehokkain, kun ongelma esittelee ahneutta-valintaa omaisuutta ja optimaalista alarakennetta.

Käytännön esimerkkejä

Ahneusalgoritmien avulla ratkaistuja yhteisiä ongelmia ovat muun muassa kolikonvaihto-ongelma, aktiviteettivalinta ja murto-osainen reppuongelma. Nämä esimerkit osoittavat, miten paikallisen optimaalisten valintojen tekeminen voi johtaa maailmanlaajuisesti optimaaliseen ratkaisuun tietyissä skenaarioissa.

Laskelmat ja toteutus

Harkitse kolikonvaihto-ongelmaa, jossa tavoitteena on tehdä muutos tietylle summalle käyttäen vähiten kolikoita. Oletetaan, että kolikon nimellisarvo on 1, 5, 10 ja 25 senttiä, ja tavoitemäärä on 63 senttiä. Ahneus lähestymistapa edellyttää valita suurin kolikko vähemmän tai yhtä paljon kuin jäljellä oleva määrä kussakin vaiheessa.

Vaiheittainen laskenta:

  • Valitse 25 senttiä (muut: 63 - 25 = 38)
  • Valitse 25 senttiä (muut: 38 - 25 = 13)
  • Valitse 10 senttiä (jäännös: 13 - 10 = 3)
  • Valitse 1 sentti (muu: 3 - 1 = 2)
  • Valitse 1 sentti (muu: 2 - 1 = 1)
  • Valitse 1 sentti (muu: 1 - 1 = 0)

Käytetyt kolikot yhteensä: 6.