Dinamično programiranje/SonjaValenčič

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

V računalništvu je dinamično programiranje način reševanja problemov, ki jih lahko razbijemo na podprobleme, ki so istega tipa kot glavni problem, vendar na manjšem obsegu podatkov. Z dinamičnim programiranjem pogosto rešimo problem v polinomskem času, čeprav bi naivna rešitev zahtevala eksponentni čas. Dinamično programiranje je leta 1953 izumil ameriški matematik Richard Bellman.

Znani sta dve tipični zvrsti problemov, ki ju rešujemo z dinamičnim programiranjem.

Vsebina

Problem s prekrivajočimi podproblemi

Da se podproblemi prekrivajo pomeni, da isti podproblem uporabimo za reševanje več različnih večjih problemov. Na primer, če hočemo izračunati 5-ti člen Fibonaccijevega zaporedja, dvakrat uporabimo vrednost tretjega člena, ker F5 = F4 + F3 in F4 = F3 + F2. Če bi F3 dvakrat računali, bi izgubljali čas z reševanjem problema, ki smo ga enkrat prej že rešili. Da se temu izognemo, shranimo rešitve že rešenih problemov. Temu pravimo memoizacija (ne memorizacija).

Problem optimalne sestave

Optimalna sestava pomeni, da optimalno rešitev celotnega problema dobimo s pomočjo optimalnih rešitev podproblemov. Tak problem rešimo po korakih:

  1. če je problem zadosti majhen, ga neposredno rešimo
  2. problem razdelimo na manjše podprobleme
  3. z enakim postopkom poiščemo optimalne rešitve podproblemov
  4. iz optimalnih rešitev podproblemov sestavimo optimalno rešitev celotnega problema

Postopek reševanja

Dinamično programiranje pozna dva pristopa:

Od zgoraj navzdol
Problem razdelimo na podprobleme , te podprobleme rešimo in si zapomnimo njihove rešitve, ker jih bomo morda še potrebovali. Pri tem načinu sta združeni rekurzija in memoizacija.
Od spodaj navzgor
Vse podprobleme, katerih rešitve bomo potrebovali, rešimo vnaprej in si rešitve zapomnimo. Iz teh rešitev sestavljamo rešitve večjih problemov. Ta pristop porabi malo manj prostora v pomnilniku (funkcija se manjkrat pokliče), ampak včasih je težko v naprej določiti vse podprobleme, katerih rešitve bomo potrebovali.

Slabosti

Če se pod...pod..podproblemi ne ponavljajo, ali če jih je eksponentno mnogo, z dinamičnim programiranjem ne moremo priti do rešitve s polinomsko časovno odvisnostjo. Tudi če je pod...pod...podproblemov polinomsko mnogo, jih je lahko vseeno preveč, da bi vse njihove rešitve shranili v pomnilniku. Če smo prepričani, da nekaterih rešitev ne bomo več potrebovali (npr. če je podproblem velikosti k odvisen samo od problemov velikosti k-1 in k-2, ne pa od tistih velikosti k-3 in manj), jih lahko sproti pozabljamo in tako prihranimo prostor.

Primer

Fibonaccijevo zaporedje je definirano rekurzivno, zato je za izračun n-tega člena najbolj primerna rekurzivna metoda.

  1.  
  2. //metoda vrne n-ti člen Fibonaccijevega zaporedja
  3. public static int fibo(int n) {
  4. if(n == 0 || n == 1) return 1; //ustavitveni pogoj: prva dva člena imata vrednost 1
  5. //metodo kličemo rekurzivno dokler je n >= 2
  6. return fibo(n-1) + fibo(n-2);
  7. }

Vendar tako napisana metoda že za dokaj majhne n opravi precej nepotrebnega računanja. Če hočemo na primer izračunati peti člen zaporedja, se prvi člen računa kar štirikrat (metoda fibo se za n = 1 kliče štirikrat). Na spodnjem grafu se vidi, da tudi nekatere druge člene računamo večkrat.

Ker nekatere člene računamo večkrat, je časovna zahtevnost te metode eksponentna. Temu se lahko izognemo: ko metodo prvič pokličemo za neko število n, rezultat shranimo v npr. tabelo in ko spet potrebujemo rezultat metode pri tem istem n, ga vzamemo iz tabele. Ker nižjih členov ni potrebno računati večkrat, je časovna zahtevnost sedaj O(n). To je pristop od zgoraj navzdol: najprej smo problem razbili na podprobleme in potem podprobleme rešili in shranili rešitve. Kot že rečeno, shranjevanju vrednosti, ki smo jih že izračunali, pravimo memoizacija.

  1. // tabela, v kateri bomo hranili vrednosti že izračunanih členov
  2. // na i-tem mestu bo vrednost i-tega člena
  3. public static int[] fibonacci = new int[1000]; //zadostuje za izračun do 1000-ega člena zaporedja
  4.  
  5. public static int fibo(int n) {
  6. if(n<=1) return 1;
  7. else {
  8. if(fibonacci[n] == 0 ){//n-tega člena do sedaj še nismo izračunali
  9. fibonacci[n] = fibo(n-1) + fibo(n-2); //rezultat vstavimo v tabelo, da ga bomo lahko
  10. //kasneje spet uporabili
  11. }
  12. return fibonacci[n];
  13. }
  14. }

Tudi to metodo lahko še izboljšamo. Prostorsko zahtevnost lahko zmanjšamo z linearne na konstantno. Da nam ni potrebno definirati tabele, uporabimo pristop od spodaj navzgor: Člene računamo od drugega (ničti in prvi sta dana) do n-tega in ob vsaki ponovitvi zanke si zapomnimo samo vrednosti prejšnjih dveh členov.

  1.  
  2. public static int fibo2(int n){
  3. int fibo_0 = 1;
  4. int fibo_1 = 1;
  5. for(int i = n-1; i > 0; i--){
  6. int fiboNovi = fibo_0 + fibo_1;
  7. fibo_0 = fibo_1;
  8. fibo_1 = fiboNovi;
  9. }
  10. return fibo_1;
  11. }

Glej tudi

Viri

Osebna orodja