Close menu
Close menu

Tunnistaudu

Kirjaudu

Etkö ole vielä jäsen?

Liity jäseneksi

5.3 Ahneet algoritmit

Ahneella algoritmilla tarkoitetaan algoritmien suunnittelumenetelmää, missä ongelma pyritään ratkaisemaan tekemällä ”ahneesti” parhaimmalta vaikuttavia valintoja. Valinta tehdään yleensä käyttämällä jotain yksinkertaista sääntöä tai ohjetta. Esimerkkinä voidaan tarkastella vaihtokolikoiden antamista, kun käytössä on tavanomaiset Suomessa käytössä olevat kolikot.
Slide14.PNG

Jos jokin rahasumma R pitää muodostaa pienimmällä mahdollisellä määrällä kolikoita, toimii seuraava ahne algoritmi oikein:

  • Valitaan aina isoin mahdollinen vaihtokolikko K, joka vielä sisältyy rahasummaan R.
  • Vähennetään rahasummasta R kolikon K arvo, ja jatketaan jäljellä olevalle rahasummalle vaihtorahojen antamista samalla tavalla.

Slide18.PNG

Ahneen algoritmi toimiminen esimerkkitilanteessa perustuu siihen, että kolikoiden arvot on valittu sopivasti. Mikäli kolikoiden arvot on valittu jotenkin muuten, ei ahne algoritmi välttämättä anna oikeaa ratkaisua.

Tutustu ohjelmaesimerkkiin vaihtorahojen laskemisesta (WeScheme).

Tehtäsarja 1: Ahne algoritmi
5.4 Dynaaminen ohjelmointi