Dinamično programiranje

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.

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

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 Belmanova enačba. Vsak problem rešen s pomočjo metode dinamičnega programiranja ima svojo Belmanovo 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

Algoritmi

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