Dinamično programiranje

Iskanje najkraše poti. Odebeljena črta predstavlja najkrajšo pot med dvema vozliščema

Dinamično programiranje je prva metoda, ki sistematično pregleduje vse možne poti v reševanju problema in zato tudi pride do optimalne rešitve.

V splošnih primerih ne moremo dobiti na tekočem koraku delčke rešitve, vidimo le množico potencionalnih rešitev do konca in potem jih rekonstruiramo. Končna rešitev je sestavljena iz komponent rešitve oziroma iz delnih rešitev. Ko na tekočem koraku ugotovimo, da delna rešitev oziroma komponenta neke rešitve ne vodi h cilju, to delno delno rešitev zavržemo.

Dinamično programiranje temelji na pravilu optimalnosti, saj vsako podzaporedje optimalnega zaporedja je tudi optimalno.

Osnova za dinamično programiranje je rekurzivna enačba, ki se imenuje Bellmanova enačba. Vsak problem rešen s pomočjo metode dinamičnega programiranja ima svojo Bellmanovo enačbo.

Ker potencialne rešitve na tekočem koraku določamo na osnovi potencialnih rešitev iz prejšnjega koraka, je pri dinamičnem programiranju prisotna rekurzivna relacija. Poznamo dva pristopa za reševanje:

• pristop naprej
• pristop nazaj

Prednost dinamičnega programiranja je predvsem ta, da kadar želimo delati z več objekti, zanje ni potrebno rezervirati fiksnih količin spomina (glej tabela) ampak ga lahko dodeljujemo dinamično po potrebi. Podatke lahko s kazalci uredimo, na primer, v vrsto (podatkovni tip) oseb, ki stojijo pred blagajno. Vsak objekt (Oseba) v tej vrsti bo vseboval atribute o sebi ter kazalec na naslednjo osebo. Zadnji objekt bo vseboval kazalec na prazen prostor (null). Kadar dodamo novo osebo v vrsto, dinamično rezerviramo v pomnilniku prostor za novo osebo (ustvarimo nov objekt), ter zadnji osebi spremenimo prazen kazalec na novoustvarjeno osebo. (glej tudi podatkovne strukture seznam, sklad)

Tak način dodeljevanja pomnilnika je zelo pomemben pri algoritmih, ki zahtevajo veliko število operacij nad veliko količino podatkov. Prav tako lahko pri zahtevnejših podatkovnih strukturah kazalci kažejo na več sosednjih objektov in s tem tvorijo drevo (glej binarna odločitvena drevesa (ang. Binary Decision Tree, BDT)). Za optimizacijo iskalnega časa je potrebno podatke že ob vstavljanju umestiti na ustrezno mesto ter včasih tudi spremeniti strukturo drevesa (Bayerjevo drevo, rdeče-črna drevesa, rotacije). Pri tem dinamično spreminjamo kazalce med objekti.

Algoritmi

• dolžine najkrajših poti
• optimalna dvojiška drevesa
• 0/1 nahrbtnik
• problem trgovskega potnika