Przejdź do treści

Programowanie dynamiczne

Lekcję o programowaniu dynamicznym zacznijmy od bardzo prostego (a także znanego i popularnego) przykładu: spróbujmy obliczyć n-tą liczbę Fibonacciego.

Liczby Fibonacciego są mocno rozpowszechnione, nawet w kulturze popularnej, ale przypomnijmy: liczby Fibonacciego to elementy ciągu, którego pierwszymi wyrazami są 0 i 1, a każdy następny wyraz jest sumą dwóch poprzednich: 1, 2, 3, 5, 8, 13,... Formalnie, można je zdefiniować tak:

\[\begin{align*} F_0 &= 0\\ F_1 &= 1\\ F_n &= F_{n-1} + F_{n-2} \end{align*}\]

Chcemy obliczyć zadany wyraz tego ciągu, na przykład \(F_{25}\) lub \(F_{1000}\). Na pierwszy rzut oka mogłoby się wydawać (i niestety, pogląd ten pokutuje w szkołach oraz wśród wysokich wyników wyszukiwania w internecie), że idealnym sposobem rozwiązania tego problemu jest rekursja, tak jak w poniższym kodzie:

int fibonacci(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

Warunki działania rekursji są w zasadzie spełnione: sprowadzamy problem (liczenie \(F_n\)) do mniejszych (liczenie \(F_{n-1}\) oraz \(F_{n-2}\)), mamy gwarancję, że prędzej czy później dojdziemy do najmniejszych przypadków (\(F_0\) i \(F_1\)), które są obsłużone. Istotnie, procedura ta wyprodukuje prawidłowe wyniki, pod warunkiem, że liczba n będzie odpowiednio mała. Dla n = 30 program będzie działał już zauważalnie długo, a dla n = 50 nie skończy działania w dającej się przewidzieć przyszłości.

Skąd biorą się problemy? Oczywistym jest, że fibonacci(30) wywoła fibonacci(29) oraz fibonacci(28). Ale z kolei fibonacci(29) uruchomi tę samą funkcję dla 28 (już po raz drugi!) i 27, a oba wywołania fibonacci(28) potrzebują fibonacci(27) (po raz drugi i trzeci). Łatwo się przekonać, że ostatecznie dojdzie do ogromnej liczby wykonań fibonacci(1) i fibonacci(0). Widać zatem, że bardzo wiele wartości jest liczona – niepotrzebnie – bardzo wiele razy. Liczby Fibonacciego są więc raczej klasycznym przykładem sytuacji, w której nie należy stosować rekursji.

Spróbujmy innego podejścia: zamiast zaczynać od fibonacci(n) i zastanawiać się, czego potrzebujemy, spróbujmy rozpocząć od dołu, obliczając fibonacci(2), fibonacci(3), ..., aż do fibonacci(n).

int fibonacci(int n)
{
    int F[n+1];
    F[0] = 0;
    F[1] = 1;
    for(int i = 2; i <= n; i++)
        F[i] = F[i-1] + F[i-2];
    return F[n];
}

Ten program nie jest specjalnie trudniejszy, a dodatkowo bardzo łatwo oszacować jego złożoność – skoro na każdy wyraz wykonywana jest jedna operacja, złożoność jest O(n). Zadziała więc i dla dużych n (jeśli, oczywiście, ominiemy problem związany z tym, że liczby Fibonacciego są bardzo duże, na przykład szukając tylko ich reszty z dzielenia przez jakąś ustaloną liczbę).

Takie podejście do problemu – od jego najprostszych składowych do najbardziej złożonych – zwane jest z angielska bottom-up, podczas gdy podejście "od całości do części" nazywane jest top-down. Dzisiejszy wykład poświęcony jest właśnie zamianie podejścia top-down (rekursja) na bottom-up, które w tym kontekście nazywa się programowaniem dynamicznym.

Prosty algorytm dynamiczny

Zacznijmy od prostego zadania:

Na \(n\) stosach ustawionych w rzędzie leży pewna liczba monet: na pierwszym stosie \(a_1\), na drugim \(a_1\) , ..., na \(n\)-tym \(a_n\). Wolno nam zabrać niektóre z tych stosów, ale nie wolno ruszyć dwóch sąsiednich. Jaka jest największa liczba monet, które można uzyskać?

Niestety, parę nasuwających się prostych strategii (na przykład "zabierać po kolei największe stosy, dopóki to możliwe", albo "zabrać tylko stosy o parzystych, albo tylko o nieparzystych numerach") okazuje się nieprawidłowe – omówimy bliżej takie podejścia za tydzień. Aby rozwiązać zadanie, oznaczmy sobie przez \(f(k)\) liczbę monet, które dałoby się zebrać, gdybyśmy do dyspozycji mieli tylko k początkowych stosów (czyli tylko stosy \(a_1, a_2, \ldots, a\_k\)). Przyjmijmy dodatkowo \(f(0) = 0\), widać też od razu, że \(f(1) = a_1\). Mamy więc do rozwiązania n problemów – obliczenie \(f(1), f(2),\ldots,\) oraz \(f(n)\). Zaczynamy od sformułowania warunku rekurencyjnego na \(f(k)\) – zakładamy, że mamy już obliczone \(f(1), f(2), \ldots, f(k-1)\) i dokonujemy prostej obserwacji:

  • Jeśli mamy do dyspozycji stosiki \(a_1, ..., a_k\), a zdecydujemy się nie brać ostatniego, to pozostaje nam do dyspozycji k-1 stosów, na których możemy postąpić dowolnie – a wiemy, że wartość \(f(k-1)\) jest najlepszym rozwiązaniem na tym ograniczonym problemie.
  • Jesli zdecydujemy się zabrać stosik \(a_k\), to nie wolno nam wziąć \(a_{k-1}\), za to na pozostałych stosach mamy pełną swobodę – najlepszy wynik, jaki na nich osiągniemy, obliczyliśmy już jako \(f(k-2)\).

Mamy więc dwie możliwości postępowania, i możemy wybrać jedną z nich – oczywiście wybieramy lepszą. Tak więc ostatecznie:

\[ f(k) = max\{f(k-1), a_k + f(k-2)\} \]

Pozostaje kwestia, jak użyć tego wzoru rekurencyjnego. Podobnie jak w wypadku liczb Fibonacciego, po prostu obliczamy kolejno \(f(2), f(3),\ldots, f(n)\), każdą wartość wyliczając z poprzednich na podstawie naszego wzoru:

// w tablicy A znajdują się kolejne wartości: a_1 to A[1], a_2 to A[2] itd.

// w tablicy F będziemy zapisywać wyniki


F[0] = 0;
F[1] = A[1];

for(int i = 2; i <= n; i++)
    F[i] = max(F[i-1], A[i] + F[i-2]);

Złożoność jest tu (oczywiście) O(n). Algorytm ten jest jednym z przedstawicieli bardzo szerokiej klasy algorytmów dynamicznych: ciężko podać (i nie jest to zresztą potrzebne) dokładną i precyzyjną definicję takowego, ale nieformalnie przyjmuje się, że są to algorytmy, które w celu rozwiązania problemu wyróżniają pewną liczbę mniejszych zadań – podobnych do pierwotnego – takich, że każde następne da się wyliczyć z poprzedniego. Odpowiedzi wyliczane są kolejno, od najprostszych zadań do najbardziej złożonych.

Najdłuższy wspólny podciąg

Jednym z najbardziej klasycznych – i najbardziej użytecznych – przykładów zastosowania programowania jest problem najdłuższego wspólnego podciągu dwóch słów (czyli łańcuchów znaków). Sfomułowanie problemu jest następujące:

Dane są dwa ciągi znaków: A[1..m] i B[1..n]. Znaleźć najdłuższe słowo C[1..k], które można otrzymać zarówno z A, jak i z B przez wykreślenie pewnych liter.

Na przykład, jeśli słowem A jest barka, a słowem B – brak, można otrzymac słowo ba k przez opuszczenie dwóch liter w A, a także przez opuszczenie jednej litery B. W tym wypadku będziemy (na razie) szukać jedynie długości podciągu, czyli liczby k w podanej definicji.

Tak jak poprzednio, będziemy starali się sformułować mniejsze problemy (podzadania), a potem rozwiązywać je w odpowiedniej kolejności. Pozadania muszą być tak dobrane, aby rozwiązanie każdego wynikało z mniejszych, podobnie jak w rekursji. W tym konkretnym wypadku skutecznym okazuje się zdefiniowanie:

P[i][j] – długość najdłuższego wspólnego podciągu początkowych fragmentów słów: A[1..i] oraz B[1..j].

Dla podanego przykładu słów barka i brak będziemy mieli na przykład P[2][2] = 1, jako że słowem A[1..2] jest ba, słowem B[1..2] jest br, a ich najdłuższy wspólny podciąg to po prostu b. Z kolei P[4][3] to 2 ( A[1..4] = bark, B[1..3] = bra, ich najdłuższym podciągiem jest ba albo br, oba długości 2). Dla wygody będziemy przyjmować P[i][0] = 0 dla każdego i, a także P[0][j] = 0 dla każdego j.

Nie jest trudno wyrazić P[i][j] rekurencyjnie, w zależności od mniejszych podzadań. Zauważmy, że najdłuższy wspólny podciąg A[1..i] oraz B[1..j] musi wpadać w jedną z trzech kategorii:

  • nie używać ostatniej dostępnej literki A[i] słowa A[1...i] – wtedy jest tak naprawdę podciągiem A[1..i-1]. Na przykład, jeśli podciąg słowa barka nie używa ostatniej litery (a), to jest też podciągiem słowa bark. W takim wypadku widać, że P[i][j] = P[i-1][j].

  • nie używać literki B[j], ostatniej w B[1..j] – wtedy P[i][j] = P[i][j-1]

  • używać zarówno A[i], jak i B[j]. Ale wtedy A[i] musi być ostatnią literą podciągu, a także B[j] musi być ostatnią literą podciągu. To się może zdarzyć tylko, jeśli A[i] = B[j]. Wtedy obliczamy podciąg A[1..i-1] i B[1..j-1], po czym dopisujemy do niego tę literę, otrzymując P[i][j] = P[i-1][j-1] + 1.

Mamy więc następujący – nieco bardziej skomplikowany niż wcześniej – wzór rekurencyjny:

\(P[i][j] = \max \begin{cases} P[i-1][j], \\ P[i][j-1], \\ P[i-1][j-1] + 1, \mbox{o ile } A[i] = B[j] \end{cases}\)

Znamy więc podzadania i potrafimy je obliczać rekurencyjnie. Pozostaje pytanie, w jakiej kolejności rozważać wartości P[i][j]. Zauważmy, że P[i][j] potrzebuje wyłącznie wartości P[i-1][j], P[i][j-1] oraz P[i-1][j-1]. Musimy więc dopilnować, aby wartości te były już w tym momencie znane. Dobrą kolejnością obliczeń jest na przykład:

P[0][0], P[0][1], ..., P[0][n], P[1][0], P[1][1], ..., P[1][n], P[2][0], ..., P[m][n].

Implementację algorytmu – okazuje się być wyjątkowo krótki – pozostawiamy Czytelnikowi w ramach jednego z zadań dołączonych do tej lekcji.

Do zadań tej lekcji dołączamy zaległe zadanie z lekcji 4, jednocześnie przepraszając za opóźnienie wynikłe z przyczyn technicznych. To zadanie wlicza się do puli zadań obowiązkowych do zaliczenia kursu.

Zadania

Piramida

Randka w ciemno

Najdłuższy wspólny podciąg