Programowanie dynamiczne: Różnice pomiędzy wersjami

'''Programowanie dynamiczne''' jest techniką lub strategią projektowania [[algorytm|algorytmów]]ów, stosowaną przeważnie do rozwiązywania zagadnień [[optymalizacja|optymalizacyjnych]]. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą [[algorytm zachłanny|algorytmów zachłannych]]. Wynalazcą techniki jest amerykański matematyk [[Richard Ernest Bellman|Richard Bellman]], uhonorowany za to odkrycie medalem [[Institute of Electrical and Electronics Engineers|IEEE]] ([[język angielski|ang.]] ''medal of honour'') w [[1979]] roku.

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 [[Atak 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 [[rekursjaRekurencja|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.

Niejednokrotnie stosowanie techniki programowania dynamicznego daje w rezultacie [[algorytm pseudowielomianowy]]. Programowanie dynamiczne jest jedną z bardziej skutecznych technik rozwiązywania [[Problem NP -trudny|problemów NP-trudnych]]. Niejednokrotnie może być z sukcesem stosowana do względnie dużych przypadków problemów wejściowych, o ile stałe występujące w problemie są stosunkowo nieduże. Na przykład, w przypadku dyskretnego [[problem plecakowy|zagadnienia plecakowego]] jako parametry dynamiczne w metodzie programowania dynamicznego należy przyjąć rozmiar kolejno rozpatrywanych podzbiorów elementów oraz rozmiar plecaka, zmieniający się od 0 do wartości B danej w problemie.

* znajdowanie rozwiązania [[Problem nawiasowania ciągu macierzy|problemu optymalnego nawiasowania macierzy]]