Programowanie dynamiczne

2006 dziewczynek siedzi przy okrągłym stole. Jedna z nich ma 2006 kart…

Algorytmem pseudolosującym p. Duraja zostałem wybrany spośród 5 osób, które zostały po dzwonku w klasie do napisania czegoś o programowaniu dynamicznym. Postaram się napisać przejrzyście, zrozumiale i bez żadnych nasuwających się błędnych skojarzeń..

Ogólnie

Co to jest programowanie dynamiczne? (w dalszej części artykułu czasami oznaczane skrótowo jako PD)
Jest to metoda rozwiązywania problemów (najczęściej optymalizacyjnych(to znaczy takich, gdzie trzeba znaleźć najnajlepszą/najmniejszą/największą/itp wartość (czyli najoptymalniejszą))), w której to problem dzieli się na mniejsze podproblemy, a następnie korzystając z rozwiązanych podproblemów rozwiązujemy problem główny.

Jednak nie zawsze najoptymalniejsze rozwiązania podproblemów pomogą rozwiązać problem główny.
Przykład (z Cormena, najprostszy):

Mamy powyższy graf (mimo, że nie ma tam strzałek, przyjmujemy, że jest skierowany). Chcemy znaleźć najdłuższą ścieżkę prostą z wierzchołka 1 do 4. Na oko widać, że jest to 1-2-4 lub 1-3-4. Jeśli podzielimy ten problem na dwa mniejsze: najdłuższa ścieżka prosta z 1 do 2 oraz najdłuższa ścieżka prosta z 2 do 4 to co się dzieje? Najdłuższa ścieżka prosta z 1 do 2 to 1-3-4-2 a z 2 do 4 to 2-1-3-4. Łącząc te dwa podproblemy nie otrzymujemy rozwiązania naszego pierwotnego problemu. Najdłuższa ścieżka, jaką w ten sposób znaleźliśmy nie jest prosta.

Nasuwa się pytanie: jakie problemy możemy rozwiązywać programowaniem dynamicznym?
Problemy, które można rozwiązywać używając powyższej metody muszą mieć własność optymalnej podstruktury.
…
Co to jest własność optymalnej podstruktury?
Jest to własność problemu, która mówi, że dany problem można rozwiązać mając już rozwiązane jego podproblemy.

Jak rozpoznać czy dany problem ma własność optymalnej podstruktury?
Przeprowadzić dowód, że ma, bądź wymyślić kontrprzykład ;)

Programowanie dynamiczne jest w pewien sposób związane z algorytmami zachłannymi. Obu metod się używa, aby uzyskać jakiś najlepszy wynik. Algorytmy zachłanne są zwykle łatwiejsze do wymyślenia/zaklepania, ale nie zawsze można ich użyć do rozwiązania danego problemu. Jak się nie da, wtedy korzystamy z PD.

Cechy charakterystyczne programów dynamicznych:
- jak to określił p. Duraj: "kody do nich zwykle są krótkie i zawierają zazwyczaj jedną długą linijkę"
- ta jedna długa linijka to wzór rekurencyjny wykorzystujący gotowe rozwiązania podproblemów

3 ogólne metody zaklepania algorytmu dynamicznego

Przykład: Ciąg Fibonacciego (z lekcji, najprostszy)
I sposób (najgorszy):

fib(n) {
    if(n<2) return n;
    return fib(n-1) + fib(n-2);
}

Dlaczego jest najgorszy?
Jedną wartość fib(n) będziemy liczyć więcej niż jeden raz. Zdecydowanie więcej niż jeden raz. A po co skoro ona się nie zmienia?

Jaka jest złożoność?
Dla każdego wywołania będziemy sie wywoływać tak długo, aż zejdziemy do n = 1 lub n = 0. Czyli fib(1) wywołamy w sumie fib(n)-krotnie. Plus jeszcze czas "dojścia" do n=1.
Możemy to sobie rozrysować takie drzewo binarne. Korzeniem jest fib(n). Korzeń ma dwóch synów: fib(n-1) i fib(n-2). fib(n-1) również ma dwóch synów: fib(n-2) i fib(n-3). I każdego syna tak rozpisując powstanie nam niepełne drzewo binarne, gdzie liśćmi będą fib(1) i fib(0). Rysując odpowiednio ładnie to drzewo będzie miało większość węzłów po jednej stronie. Ilość węzłów w pełnym drzewie binarnym to 2^{^n}. Ilość węzłów w tym drzewie binarnym to około 1.6ⁿ. Czyli złożoność algorytmu wychodzi nam właśnie O(1.6ⁿ). Złożoność wykładnicza jest zła biorąc pod uwagę, że dany problem można rozwiązać szybciej..

II sposób: spamiętywanie
Pierwszy sposób można zdecydowanie polepszyć dodając jednego małego upgrade'a.

int F[1...n];
F[0] = 0;
F[1] = 1;
F[2...n] = -1;

fib(n) {
    if(F[n] != -1)
        return F[n];
    F[n] = fib(n-1) + fib(n-2);
    return F[n];
}

Dlaczego jest to lepsze?
Teraz zamiast wyliczać za każdym razem wartość dla aktualnego n, zapamiętujemy(stąd nazwa - spamiętywanie) ją w tablicy. Kiedy przyjdzie nam ponownie odwołać się do danej liczby Fibonacciego odczytujemy ją z tablicy.

Jaka jest złożoność?
F[n] = fib(n-1) + fib(n-2); dla każdego n wykona się dokładnie raz. Odczytywanie również dla każdego n wykona się dokładnie raz. Co nam daje:
2*n -> O(n). Liniówka. Co jest zdecydowanie lepsze niż złożoność wykładnicza.

III sposób: metoda wstępująca
Metoda wstępująca niewiele się różni od spamiętywania. Również trzymamy rozwiązania podproblemów w tablicy i później z nich korzystamy. Tylko teraz zamiast Wywoływać się rekurencyjnie dla podproblemu i sprawdzać czy już został rozwiązany i jeśli nie to rozwiązać to podproblemy rozwiązujemy iteracyjnie od najmniejszych do coraz większych. W ten sposób rozwiązując jakiś problem mamy pewność, że wszystkie podproblemy mniejsze od niego mamy już rozwiązane.

Jak to wygląda na ciągu Fibonacciego:

int F[1...n];
F[0] = 0;
F[1] = 1;
for i = 2 to n
    F[i] = F[i-1] + F[i-2];

Obrazowo można powiedzieć, że jest to wypełnianie tablicy od lewej do prawej (dla problemów jednowymiarowych) lub z góry do dołu i od lewej do prawej (dla problemów dwuwymiarowych).

Zalety w stosunku do spamiętywania:
- nie musimy się wywoływać rekurencyjnie dla podproblemów, wiemy, że ich rozwiązania już mamy
- w niektórych przypadkach da się zupgrade'ować złożoność pamięciową

Co znaczy, że da się polepszyć złożoność pamięciową?
W naszym przykładzie (ciąg Fibonacciego) złożoność pamięciowa wynosi O(n). Ale zauważmy, że dla aktualnej liczby F[i] wykorzystujemy tylko dwie poprzednie wartości. Z reszty nie korzystamy. To znaczy, że zamiast tablicować wszystkie liczby, wystarczy, że zapamiętamy dwie ostatnie (pod warunkiem, że chodzi nam tylko o F[n], a mniejsze nam nie są potrzebne w zadaniu).

int przedostatnia = 0;
int ostatnia = 1;
int aktualna;
for i=2 to n
    aktualna = przedostatnia + ostatnia;
    przedostatnia = ostatnia;
    ostatnia = aktualna;

W ten sposób mamy złożoność pamięciową O(1).
Ta optymalizacja przydaje się czasami, w niektórych zadaniach. Zdarzają się takie zadania, że np: złożoność czasowa ma być O(n²), ale pamięciowa O(n).
Wtedy zamiast trzymać całą tablicę NxN, trzymamy ostatni wiersz tej tablicy, a aktualny wypełniamy na jego podstawie (tylko pod warunkiem, że wzór rekurencyjny na to pozwala).

Rozwinięcie

Wstęp za nami, teraz kilka przykładów zastosowania w najpopularniejszych problemach.

Najdłuższy wspólny podciąg (NWP):
Mamy dwa ciągi(literowe, liczbowe, itp)
A: 1 3 3 7 5 6 8 (długość n=7)
B: 1 3 5 2 2 8 0 (długość m=7) [n nie musi być równe m]
Ich najdłuższy wspólny podciąg ma długość 4 (jest to podciąg 1 3 5 8).
A teraz jak to obliczyć(konkretnie długość, nie sam podciąg).
Niech "i" będzie wskazywało na pewną pozycję z pierwszego ciągu (indeksujemy od 1).
Tak samo "j" tylko dla drugiego podciągu.

Mamy tablicę rozmiaru nxm. W komórce [i][j] będzie wartość najdłuższego wspólnego podciągu, tak jakbyśmy ucięli pierwszy ciąg do pierwszych i znaków, a drugi do pierwszych j znaków. Dla i=0 lub j=0 dane ciągi są ciągami pustymi. W szczególności w komórce [n][m] będzie wartość NWP dla naszych początkowych ciągów.
Jak obliczyć komórkę [i][j]?
Zauważmy, że jeśli i-ty znak z pierwszego ciągu jest taki sam jak j-ty znak z drugiego, to NWP [i][j] jest równy najdłuższemu wspólnemu podciągowi ciągów o ten jeden znak krótszych + 1. Czyli [i][j] = [i-1][j-1] + 1;
Ale jeśli aktualne dwa przetwarzane znaki są różne, to NWP może być równy NWP ciągów [i][j-1] lub [i-1][j], a konkretnie większa wartość z tych dwóch. Czyli [i][j] = max([i-1][j],[i][j-1]).

Czyli otrzymaliśmy ogólny wzór rekurencyjny:

NWP[i][j] = max(NWP[i-1][j],NWP[i][j-1]) dla A[i] != B[j]
        NWP[i-1][j-1] + 1 dla A[i] == B[j]

Pozostaje nam jeszcze ustalenie wartości dla wiersza i = 0 i kolumny j = 0. Ale to pozostawiam jako ćwiczenie :)
Jest to przy okazji przykład, w którym można zastosować ulepszenie złożoności pamięciowej, tutaj korzystamy tylko z aktualnego i poprzedniego wiersza, więc po co zapamiętywać wszystko (no chyba, że mamy sporo dostępnej pamięci).

[więcej przykładów kiedyś..]

Zakończenie

Na zakończenie pokażę (mniej więcej) jak wykorzystać PD do przepchnięcia zadań I i J na Athinie.

Zadanie I
Mamy ukraść filary z mostu tak, żeby ich suma wartości była jak największa. Przy czym nie możemy zabrać trzech kolejnych.

Jeśli most ma jeden filar, to go zabieramy.
Jeśli most ma dwa filary, to je zabieramy.
Jeśli most ma trzy i więcej filarów…

Dla każdej kolejnej trójki filarów musimy zdecydować, którego z nich najbardziej nam się opłaca nie wziąć, biorąc pod uwagę:
- jeśli nie weźmiemy pierwszego, to bierzemy to co byśmy wzięli do niego + filar drugi i trzeci z rozważanych
- jeśli nie weźmiemy drugiego, to bierzemy to co byśmy wzięli do pierwszego włącznie + filar trzeci
- jeśli nie weźmiemy trzeciego, to bierzemy to co byśmy wzięli do niego po prostu
i bierzemy maxa z tych wartości. Całość da się zaklepać w 4 liniach ;)

Zadanie J
Mamy pizzę. Pizza jest okrągła. Jest podzielona na nierówne części. Biorąc na zmianę z drugą osobą chcemy wziąć jak największą wartość kawałków.

Jak by to rozwiązać jeśli pizza byłaby podłużna (czyli miała dokładnie dwa końce, z których to możemy zacząć zabieranie kawałków)?
Oznaczmy wartości kolejnych kawałków poprzez $v_{1}, v_{2}, ..., v_{n}$
A poprzez $s_{i}$ sumę $v_{1} + v_{2} + ... + v_{i}$

Zdefiniujmy podproblem:
Ile jesteśmy w stanie najwięcej zabrać na pizzy, która składa się wyłącznie z kawałków $v_{i}, v_{i+1}, ..., v_{j}$
Oznaczmy tą wartość poprzez W[i][j].
Czyli naszym szukanym rozwiązaniem jest liczba znajdująca się w W[1][n] (cała pizza).

Zauważmy, że to co zabierze druga osoba na podkawałku od $i$ do $j$ jest równe sumie kawałków na tym obszarze minus to co my weźmiemy.

Będziemy rozpatrywać spójne podkawałki pizzy od najmniejszych do największych pod względem ilości kawałków.
Dla pizzy, która zawiera tylko jeden kawałek po prostu to zabieramy => W[i][i] = $v_{i}$
Następnie dla kawałków o długości $k = 2, 3, ..., n$ robimy co następuje:
$W[i][i+k-1] = max:$
zabieramy "lewy" kawałek i to co nam zostawi drugi gracz na obszarze W[i-1][i+k-1]
zabieramy "prawy" kawałek i to co nam zostawi drugi gracz na obszarze W[i][i+k-2]

Mamy rozwiązanie dla pizzy, która gdzieś się kończy, a gdzieś zaczyna. Lecz nasza pizza jest okrągła. Co można z tym zrobić? Możemy tą pizze gdzieś rozerwać, tak by była płaska, następnie wziać drugą identyczną pizze i położyć obok pierwszej. Powstanie nam $v_{1}, v_{2}, ..., v_{n}, v_{1}, v_{2}, ..., v_{n}$
Następnie odpalając powyższy sposób na tej pizzie i rozważając wszystkie kawałki długości $n$ możemy znaleźć najlepsze rozwiązanie.