Programowanie dynamiczne: Różnice pomiędzy wersjami

Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów. W odróżnieniu od techniki [[dziel i zwyciężaj]] podproblemy w programowaniu dynamicznym nie są na ogół rozłączne, ale musi je cechować [[własność optymalnej podstruktury]]. Zagadnienia odpowiednie dla programowania dynamicznego cechuje również to, że zastosowanie do nich [[brute force|metody siłowej]] (ang. ''brute force'') prowadzi do ponadwielomianowej liczby rozwiązań podproblemów, podczas gdy sama liczba różnych podproblemów jest wielomianowa.

Zazwyczaj jednym z parametrów definiujących podproblemy jest liczba elementów znajdujących się w rozpatrywanym problemie, drugim jest pewna wartość liczbowa, zmieniająca się w zakresie od 0 do największej stałej występującej w problemie. Możliwe są jednak bardziej skomplikowane dobory parametrów, a także większa ich liczba. Ponieważ jednak uzyskiwany algorytm zazwyczaj wymaga pamięci (i czasu) proporcjonalnego do iloczynu maksymalnych wartości wszystkich parametrów, stosowanie większej ilości parametrów niż 3-4 rzadko bywa praktyczne.

Klucz do zaprojektowania algorytmu tą techniką leży w znalezieniu [[rekursja|równania rekurencyjnego]] opisującego optymalną wartość [[optymalizacja (matematyka)|funkcji celu]] dla danego problemu jako funkcji optymalnych wartości funkcji celu dla podproblemów o mniejszych rozmiarach. Programowanie dynamiczne znajduje optymalną wartość funkcji celu dla całego zagadnienia rozwiązując podproblemy od najmniejszego do największego i zapisując optymalne wartości w tablicy. Pozwala to zastąpić wywołania rekurencyjne odwołaniami do odpowiednich komórek wspomnianej tablicy i gwarantuje, że każdy podproblem jest rozwiązywany tylko raz. Rozwiązanie ostatniego z rozpatrywanych podproblemów jest na ogół wartością rozwiązania zadanego zagadnienia.

* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001. ''Introduction to Algorithms'', 2nd ed. MIT Press & McGraw-Hill. ISBN 0-262-03293-7. Zwłaszcza rozdział 15: 323–69323–69. (klasyczny wykład podręcznikowy na poziomie podstawowym)

* Juraj Hromkovič. ''Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics.'' 2nd ed. Springer Verlag 2004. ISBN 3-540-44134-4. Rozdział 3.2: 152–7152–7 (zwięzła prezentacja teoretyczna)

[[es:Programación dinámica (informática)]]