Dinamično programiranje: Razlika med redakcijama

Izbrisana vsebina Dodana vsebina

Znotrajvrstično

Redakcija: 01:11, 18. junij 2005

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

Algoritmi

Redakcija: 11:57, 16. junij 2005 uredi Lacen (pogovor \| prispevki) 1.793 urejanj Brez povzetka urejanja		Redakcija: 01:11, 18. junij 2005 uredi razveljavi Romanm (pogovor \| prispevki) Birokrati, Preverjevalci uporabnikov, Administratorji 45.232 urejanj m Bellmanova enačba Novejše urejanje →
Vrstica 6:		Vrstica 6:
	Dinamično programiranje temelji na pravilu '''optimalnosti''', saj vsako [[podzaporedje]] optimalnega [[zaporedje\|zaporedja]] je tudi optimalno.		Dinamično programiranje temelji na pravilu '''optimalnosti''', saj vsako [[podzaporedje]] optimalnega [[zaporedje\|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.		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.