Diskretno 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?

Diskretno dinamično programiranje je ena od metod za načrtovanje algoritmov, pri kateri iščemo optimalno pot. Zadnje čase je metoda postala tako popularna, da pogosto spuščamo besedico diskretno. V splošnem namreč dinamično programiranje delimo na deterministično in stohastično, po drugi strani pa na zvezno in diskretno. Pri zveznem dinamičnem programiranju, gre za proces z zveznim časovnim parametrom, pri diskretnem pa je časovni parameter diskreten.

Natančno povedano, je potrebno v članku dinamično programiranje razumeti, da gre za deterministično, diskretno dinamično programiranje.

Rešujemo problem optimalne poti po razslojenem omrežju. Vozlišča imamo razporejena v n slojev:

V(1), V(2), ..., V(n). 

Naj p(i) označuje število vozlišč i-tega sloja:

p(i) = |V(i)|

V prvem sloju in v zadnjem sloju imamo po eno samo vozlišče

V(1) = {s}, 
V(n) = {t}. 

Usmerjene povezave potekajo le od sloja i do sloja i+1.

Povezava med j-tim vozliščem i-tega sloja in k-tim vozliščem (i+1)-vega sloja ima ceno, 
ki jo označimo s C(i,j,k). 

Povezave lahko nosijo tudi negativne cene. Iščemo najkrajšo pot od s do t.

Naj F(i,j) označuje ceno najkrajše poti od j-tega vozlišča v sloju i do vozlišča t. 

Iščemo torej F(1,1). Za reševanje uporabimo Bellmanove enačbe

F(n,1) = 0
F(i,j) = min{F(i+1,k) + C(i,j,k)| k = 1,2,...,p(i)}    

Bellmanov princip optimalnosti zagotavlja, da ima sistem Bellmanovih enačb enolično rešitev, ki daje tudi rešitev naše naloge. (V resnici dobimo cene optimalnih poti od poljubnega vozlišča do vozlišča t.)

Dinamično programiranje je torej metoda s katero poskušamo problem, ki ga rešujemo prevesti na opisani problem optimalne poti po razslojenem omrežju.

Zgled

Glej tudi

Osebna orodja