Programowanie dynamiczne

Programowanie dynamiczne (PD; ang. dynamic programming, DP) — to metoda rozwiązywania złożonych zadań optymalizacyjnych, oparta na podziale wyjściowego problemu na ciąg prostszych podproblemów. Metoda stosowana jest do wieloetapowych procesów decyzyjnych, w których optymalne rozwiązanie całego zadania może być zbudowane z optymalnych rozwiązań jego podproblemów.

Termin został wprowadzony przez amerykańskiego matematyka Richarda Bellmana w latach 50. XX wieku. W tym kontekście słowo „programowanie" używane jest w znaczeniu „planowanie" lub „opracowywanie optymalnego planu działań", a nie pisanie kodu komputerowego.

Kluczowe właściwości i twierdzenia

Możliwość zastosowania programowania dynamicznego do danego zadania określana jest przez obecność dwóch fundamentalnych właściwości.

Zasada optymalności Bellmana

Centralnym pojęciem metody jest zasada optymalności Bellmana (ang. Bellman's principle of optimality). Głosi ona: niezależnie od stanu początkowego i decyzji początkowej, kolejne decyzje muszą tworzyć optymalną strategię względem stanu uzyskanego w wyniku pierwszej decyzji.

Innymi słowy, każda część optymalnej trajektorii jest sama w sobie optymalna. Właściwość ta pozwala podzielić ogólne zadanie na ciąg prostszych podproblemów i rozwiązywać je rekurencyjnie.

Nakładające się podproblemy

Zadanie posiada właściwość nakładających się podproblemów (ang. overlapping subproblems), jeśli przy jego rekurencyjnym rozwiązywaniu te same podproblemy pojawiają się wielokrotnie. PD pozwala uniknąć powtórnych obliczeń poprzez zapamiętywanie rozwiązań już napotkanych podproblemów (technika ta nazywana jest memoizacją lub tabulacją), co znacznie zwiększa efektywność w porównaniu z naiwnym rekurencyjnym przeszukiwaniem.

Równanie Bellmana

Z zasady optymalności wynika podstawowa relacja rekurencyjna metody — równanie Bellmana. Wiąże ono „wartość" (optymalny zysk lub koszt) bieżącego stanu z wartościami stanów następnych. W ogólnej postaci dla deterministycznego procesu wieloetapowego z addytywną funkcją celu ma ono postać:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

gdzie:

• $k$ — numer kroku (od $m$ do 1);
• $x$ — stan systemu na kroku $k-1$;
• $y$ — sterowana decyzja podejmowana na kroku $k$;
• ${\phi }_k(x,y)$ — zysk (lub koszt) na k-tym kroku;
• $f_k(x,y)$ — funkcja wyznaczająca nowy stan systemu;
• $V_k(s)$ — optymalna wartość funkcji celu dla podproblemu rozpoczynającego się na kroku $k$ w stanie $s$.

Równanie rozwiązywane jest sekwencyjnie, zazwyczaj „od końca", przechodząc od ostatniego kroku do pierwszego.

Przykłady zastosowania

• Zadanie o najkrótszej ścieżce w grafie: Zadanie to posiada właściwość optymalnej podstruktury, ponieważ każdy fragment najkrótszej ścieżki jest sam w sobie najkrótszy. Algorytmy Bellmana-Forda i Floyda-Warshalla są klasycznymi przykładami zastosowania PD do rozwiązania tego zadania.
• Zadanie plecakowe: Zadanie optymalnego wypełnienia plecaka o ograniczonej pojemności przedmiotami o różnych wartościach i wagach. PD pozwala rozwiązać to zadanie, rozpatrując przedmioty kolejno i obliczając na każdym kroku maksymalną wartość dla wszystkich możliwych wartości pozostałej pojemności.
• Zadanie alokacji zasobów: Podział ograniczonego zasobu (np. inwestycji) między kilka projektów w celu maksymalizacji łącznego efektu.

Ograniczenia

Głównym ograniczeniem metody jest przekleństwo wymiarowości (ang. curse of dimensionality) — termin wprowadzony przez Bellmana dla określenia wykładniczego wzrostu liczby stanów, a w konsekwencji złożoności obliczeniowej, wraz ze wzrostem liczby zmiennych opisujących stan systemu. Ogranicza to praktyczne zastosowanie dokładnego PD dla zadań o bardzo dużej wymiarowości.

Pojęcia powiązane

• Badania operacyjne
• Teoria optymalnego sterowania
• Markowski proces decyzyjny (stochastyczne uogólnienie)
• Równanie Hamiltona — Jacobiego — Bellmana (analog dla czasu ciągłego)

Przypisy

</references>