Tässä opetusohjelmassa opit, mikä on dynaaminen ohjelmointi. Löydät myös vertailun dynaamisen ohjelmoinnin ja ahneiden algoritmien välillä ongelmien ratkaisemiseksi.
Dynaaminen ohjelmointi on tietokoneohjelmoinnin tekniikka, joka auttaa ratkaisemaan tehokkaasti luokan ongelmat, joilla on päällekkäisiä aliongelmia ja optimaalinen alarakenteen ominaisuus.
Tällaisiin ongelmiin kuuluu samojen osahäiriöiden arvon toistuva laskeminen optimaalisen ratkaisun löytämiseksi.
Dynaaminen ohjelmointiesimerkki
Otetaan tapaus tuottaa fibonacci-sekvenssi.
Jos sekvenssi on F (1) F (2) F (3)… F (50), se noudattaa sääntöä F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Huomaa kuinka päällekkäisiä alaongelmia on, meidän on laskettava F (48) laskeakseen sekä F (50) että F (49). Tämä on juuri sellainen algoritmi, jossa dynaaminen ohjelmointi loistaa.
Kuinka dynaaminen ohjelmointi toimii
Dynaaminen ohjelmointi toimii tallentamalla osaongelmien tulos niin, että kun niiden ratkaisuja tarvitaan, ne ovat käsillä eikä meidän tarvitse laskea niitä uudelleen.
Tätä tekniikkaa aliongelmien arvon tallentamiseksi kutsutaan muistiinpanoksi. Tallentamalla taulukon arvot säästämme aikaa jo kohtaamiemme alaongelmien laskemiseen.
var m = kartta (0 → 0, 1 → 1) funktio fib (n), jos avain n ei ole kartalla mm (n) = fib (n - 1) + fib (n - 2) palauttaa m (n)
Dynaaminen ohjelmointi muistiinpanolla on ylhäältä alaspäin suuntautuva lähestymistapa dynaamiseen ohjelmointiin. Kääntämällä algoritmin toiminnan suunnan eli aloittamalla perustapauksesta ja siirtymällä kohti ratkaisua voimme toteuttaa myös dynaamisen ohjelmoinnin alhaalta ylöspäin.
funktio fib (n) jos n = 0 paluu 0 muu var prevFib = 0, currFib = 1 toisto n - 1 kertaa var newFib = prevFib + currFib prevFib = currFib currFib = newFib return currentFib
Rekursio vs. dynaaminen ohjelmointi
Dynaamista ohjelmointia käytetään enimmäkseen rekursiivisiin algoritmeihin. Tämä ei ole sattumaa, suurin osa optimointiongelmista vaatii rekursiota ja optimointiin käytetään dynaamista ohjelmointia.
Mutta kaikki rekursiota käyttävät ongelmat eivät voi käyttää dynaamista ohjelmointia. Ellei päällekkäisiä aliongelmia ole, kuten fibonacci-sekvenssiongelmassa, rekursio voi saavuttaa ratkaisun vain jakamalla ja valloittamalla -menetelmällä.
Siksi rekursiivinen algoritmi, kuten Yhdistä lajittelu, ei voi käyttää dynaamista ohjelmointia, koska alaongelmat eivät ole millään tavalla päällekkäisiä.
Ahneita algoritmeja vs. dynaaminen ohjelmointi
Ahneet algoritmit muistuttavat dynaamista ohjelmointia siinä mielessä, että ne ovat molemmat optimoinnin työkaluja.
Ahneet algoritmit etsivät kuitenkin paikallisesti optimaalisia ratkaisuja tai toisin sanoen ahne valinta, toivoen löytävänsä globaalin optimaalin. Siksi ahneilla algoritmeilla voidaan tehdä arvaus, joka näyttää optimaaliselta tuolloin, mutta tulee kalliiksi linjassa eikä takaa maailmanlaajuista optimaalista.
Dynaaminen ohjelmointi puolestaan löytää optimaalisen ratkaisun ongelmiin ja tekee sitten tietoisen valinnan yhdistää näiden ongelmien tulokset optimaalisen ratkaisun löytämiseksi.
