Close menu
Close menu

Tunnistaudu

Kirjaudu

Etkö ole vielä jäsen?

Liity jäseneksi

5.4 Dynaaminen ohjelmointi

Dynaamisella ohjelmoinnilla tarkoitetaan algoritmien suunnitelumenetelmää, jolle on ominaista alkuperäisen ongelman jako helpommin ratkaistaviin osaongelmiin, osaongelmien ratkaisujen tallentaminen ja alkuperäisen ongelman ratkaiseminen osaongelmien ratkaisujen avulla.
Slide20.PNG
Jotta lähestymistapaa voidaan soveltaa, tulee ongelman olla jaettavissa yksinkertaisempiin osaongelmiin. Tarkastellaan esimerkkinä Fibonaccin lukujonon alkioiden laskemista.
Slide21.PNG
Rekursiivisen määritelmän perusteella on suoraviivaista muodostaa algoritmi lukujonon alkioiden laskemiseksi.
Slide22.PNG
Algoritmin suoritus menee hitaaksi kun perusalgoritmille annetun argumentin arvo on yli 30. Tarkkaa suoritusaikaa voidaan tutkia funktiolla time, jolle annetaan argumenttina funktio, jonka suoritusaika halutaan laskea. Syynä perusalgoritmin hidastumiseen on se, että algoritmi ei osaa suoraan hyödyntää jo aiemmin laskettuja lukuja.
Slide20.PNG
Perusalgoritmia voidaan nopeuttaa siten, että tallennetaan jo valmiiksi lasketut Fibonaccin luvut listaan. Apufunktio fib2-apu ylläpitää listaa, johon lukujonon alkiot tallennetaan listan alkuun samalla kun ne lasketaan. Harjoitustehtävissä pääset testaamaan, kuinka paljon nopeampi fib2-funktio on Fibonaccin lukujonon alkioiden laskennassa.
Slide21.PNG
Listan lisäksi toinen yleinen tietorakenne on taulukko. Taulukon alkioihin viitataan kahdella indeksillä, rivin numerolla ja sarakkeen numerolla. Rivien ja sarakkeiden numerointi lähtee liikkeelle yleensä nollasta. Taulukon voidaan ajatella olevan lista, jonka osat muodostavat taulukon rivit.Slide26.PNG
Taulukko-tietorakenteen yhtenä hyötynä on sen vastaavuus tavanomaisten taulukoiden / ruudukoiden kanssa. Esimerkiksi sudoku-ristikko tai shakkilauta on helppo mallintaa taulukkona. Tässä esitetty taulukoiden listatoteutus ei ole kuitenkaan laskennallisesti tehokasta.

Tarkastellaan seuraavana esimerkkinä kolikoiden keräämistä ruudukosta. Robotti lähtee liikkeelle ruudukon vasemmasta yläkulmasta, eli ruudusta (0,0). Robotti voi kulkea ruudukossa vain alaspäin tai oikealle. Jokaisessa ruudussa on kolikoita. Robotin pitää kerätä mahdollisimman paljon kolikoita kulkiessaan vasemmasta yläkulmasta oikeaan alakulmaan.
Slide27.PNG
Algoritmi parhaan reitin löytämiseksi kolikkorobotille perustuu seuraavaan havaintoon:

  • Jos tiedetään montako kolikkoa on mahdollista kerätä ruudusta (0,0) ruutuun (i-1,j) ja ruutuun (i, j-1) kulkevilla reiteillä, voidaan laskea montako kolikkoa on mahdollista kerätä kuljettaessa ruudusta (0,0) ruutuun (i,j).

Edellä esitetty havainto perustuu siihen, että optimaalisella reitillä ruudusta (0,0) ruutuun (i,j) myös osareittien on oltava optimaaliset. Tämän perusteella voidaan muodostaa rekursiivinen kaava kolikoiden lukumäärän laskemiseksi.
Slide28.PNG
Seuraavissa taulukoissa on esitetty kolikoiden määrä ruudukossa ja niiden kolikoiden lukumäärä, jotka voidaan kerätä parhaalla reitillä ruudusta (0,0) ruutuun (i,j). Käytetään taulukosta, johon on laskettu optimaalisella reitillä kerättävien kolikoiden lukumäärä, merkintää S ja merkintää S(i,j) viittaamaan niiden kolikoiden lukumäärään, jotka on mahdollista kerätä reitillä ruudusta (0,0) ruutuun (i,j).
Slide29.PNG

Algoritmi parhaan reitin laskemiseksi voidaan toteuttaa seuraavasti. Taulukossa (listassa) K on annettu kolikoiden määrät eri ruuduissa. Taulukon alkion (i,j) haku on toteutettu vastaavasti kuin kohdassa Listasta taulukoksi.
Slide30.PNG
Laskettaessa arvoa S(i,j) tulee seuraavat vaihtoehdot:

  • Jos i=0 ja j=0, niin ollaan taulukon vasemmassa yläkulmassa ja tällöin kerättävien kolikoiden lukumäärä on S(0,0) = K(0,0).
  • Jos i=0 ja 1
  • Jos 1
  • Jos i=4 ja j=4, niin ollaan taulukon oikeassa alakulmassa ja laskenta päättyy.
  • Muussa tapauksessa ollaan taulukon keskellä ja S(i,j) = Max ( S(i-1,j), S(i, j-1)) + K.

Funktio laske saa argumentteina indeksit i ja j, taulukon S (alussa tyhjä) ja taulukon K.
Funktion toteutuksessa on vielä huomioitu tilanne, missä j=4 (ollaan taulukon oikeassa reunassa), tällöin laske-funktiota kutsutaan seuraavan kerran arvolla j=0.
Slide31.PNG

Tehtäväsarja 1. Dynaaminen ohjelmointi
Tehtäväsarja 2: Kolikoiden kerääminen
5.5 Vektorit ja puolitushaku