Dinamično programiranje

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

V podčlanku /SonjaValenčič najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.

Dinamično programiranje je način reševanja problemov, ki sestojijo iz podproblemov, ki se prekrivajo ali katerih rešitev vključuje iskanje optimalne sestave. 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 rešitev celotnega problema dobimo tako, da poiščemo najboljšo kombinacijo rešitev podproblemov. Tak problem rešujemo z metodo deli in vladaj:

  • če je problem zadosti majhen, ga neposredno rešimo,
  • problem razdelimo na manjše podprobleme,
  • z enakim postopkom poiščemo optimalne rešitve podproblemov,
  • 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.

Primeri

Glej tudi

Viri

Osebna orodja