Informatyka MIMUW

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.