Programowanie dynamiczne

Rozwiązaniem danego problemu często jest kombinacja rozwiązań podproblemów, na które można problem rozłożyć. Natomiast nie od razu wiemy, jaka dekompozycja jest optymalna; początkowo mamy niedeterministyczny wybór wielu różnych dekompozycji. W sytuacji, gdy nie wiemy, jaka dekompozycja jest optymalna, nie możemy uruchomić rekursji, ponieważ na każdym etapie mielibyśmy wiele wyborów i w sumie złożoność mogłaby być wykładnicza.

W takich sytuacjach stosujemy metodę zwaną programowaniem dynamicznym. Metoda ta, z grubsza biorąc, wygląda następująco: Jeśli problem możemy rozbić na podproblemy i liczba wszystkich potencjalnych podproblemów jest wielomianowa, to zamiast korzystać z rekursji możemy obliczyć wartości wszystkich podproblemów stosując odpowiednią kolejność: od "mniejszych" podproblemów do "większych". Rozmiary problemów muszą być odpowiednio zdefiniowane, nie powinno być zależności cyklicznej.

Wartości obliczone dla podproblemów zapamiętujemy w tablicy. Mając obliczone wartości podproblemów, na które można rozbić dany problem, wartość problemu obliczamy korzystając z wartości zapamiętanych w tablicy.

Najistotniejsze jest tutaj określenie zbioru potencjalnych podproblemów. Z reguły zbiór ten jest znacznie większy niż zbiór podproblemów będących częściami jednego optymalnego rozwiązania.

Spróbujmy skonstruować wielomianowy algorytm dla problemu minimalnego sklejania sąsiadów korzystając z programowania dynamicznego. Jeśli mamy dany ciąg \( p_1,p_2, \ldots p_n \), to w tym przypadku podproblem można utożsamić z pewnym przedziałem \( [i..j] \). Niech \( wynik[i,j] \) będzie wartością problemu minimalnego sklejania sąsiadów dla ciągu \( (p_i,p_{i+1}, \ldots p_j) \);

oznaczmy ponadto

\( \sigma_{i,j}\ =\ \sum_{k=i}^j\ p_k \)

Algorytm Optymalne-Sklejanie-Sąsiadow

for  i:=1 to n do wynik[i,i]:=0;  
for  j:=2 to n do 
  for  i:=j-1 downto 1 do 
    wynik[i,j] := min(i <= k  < j) (wynik[i,k]+wynik[k+1,j]+sigma[i,j]) 
return  wynik[1,n];

W algorytmie zasadniczą instrukcję

\( wynik[i,j] := \min_{i \le k < j}\ (wynik[i,k]+wynik[k+1,j]+\sigma_{i,j}) \)

można wykonywać w dowolnym przyzwoitym porządku ze względu na (i,j) (na przykład po przekątnych, zaczynając od głównej przekątnej). Przyzwoitość polega na tym, że jest już ostatecznie policzone to, z czego w danym momencie korzystamy.

Algorytm ma złożoność czasową \( O(n^3) \) i jest to "typowa" złożoność algorytmów tego typu. Duża złożoność wynika stąd, że liczymy wartości dla mnóstwa podproblemów, które mogą być zupełnie nieistotne z punktu widzenia optymalnego rozwiązania.

Dygresja

Problem sklejania sąsiadów można rozwiązać inaczej, modyfikując w sposób nietrywialny algorytm Optymalne-Sklejanie-Par. W algorytmie tym instrukcję

zastąp dwa najmniejsze elementy \( a,b \) przez \( a+b \)

zamieńmy na:

zastąp dwa sąsiednie elementy \( a,b \) o minimalnej sumie przez \( a+b \)
przesuń \( a+b \) przed najbliższy na prawo (w ciągu) element \( c \) większy od \( a+b \)
(na koniec ciągu, jeśli takiego \( c \) nie ma)

Otrzymany algorytm (wersja algorytmu Garsia-Wachsa) liczy koszt minimalnego sklejania sąsiadów. Jest to przykład pozornie prostego algorytmu, dla którego odpowiedź na pytanie, "dlaczego to działa" jest niezwykle skomplikowana i wykracza poza zakres tego kursu. Pozostawiamy jako ćwiczenie implementację tego algorytmu w czasie \( O(n \log n) \), przy założeniu, że jest on poprawny. Jeśli liczby \( p_i \) są liczbami naturalnymi z przedziału \( [1..n] \), to istnieje nawet (bardzo trudna) implementacja w czasie liniowym.