Programowanie dynamiczne

Nie mylić z dynamicznym językiem programowania lub dynamicznym problemem .

Rysunek 1. Znajdowanie najkrótszej ścieżki w grafie przy użyciu optymalnej podstruktury; linia prosta wskazuje pojedynczą krawędź; linia falista wskazuje najkrótszą ścieżkę między dwoma wierzchołkami, które łączy (wśród innych ścieżek, nie pokazanych, dzielących te same dwa wierzchołki); pogrubiona linia to ogólnie najkrótsza droga od początku do celu.

Programowanie dynamiczne jest zarówno matematyczną metodą optymalizacji, jak i metodą programowania komputerowego. Metoda została opracowana przez Richarda Bellmana w latach pięćdziesiątych XX wieku i znalazła zastosowanie w wielu dziedzinach, od inżynierii lotniczej po ekonomię .

rekurencyjne rozbijanie go na prostsze podproblemy . Podczas gdy niektórych problemów decyzyjnych nie można rozebrać w ten sposób, decyzje obejmujące kilka punktów w czasie często rozpadają się rekurencyjnie. Podobnie w informatyce, jeśli problem można optymalnie rozwiązać, dzieląc go na podproblemy, a następnie rekurencyjnie znajdując optymalne rozwiązania tych podproblemów, to mówi się, że ma on optymalną podstrukturę .

Jeśli podproblemy mogą być rekurencyjnie zagnieżdżane w większych problemach, tak że można zastosować metody programowania dynamicznego, to istnieje zależność między wartością większego problemu a wartościami podproblemów. W literaturze optymalizacyjnej związek ten nazywany jest równaniem Bellmana .

Przegląd

Optymalizacja matematyczna

Jeśli chodzi o optymalizację matematyczną, programowanie dynamiczne zwykle odnosi się do uproszczenia decyzji poprzez rozbicie jej na sekwencję kroków decyzyjnych w czasie. Odbywa się to poprzez zdefiniowanie ciągu funkcji wartości V ₁ , V ₂ , ..., V _n przyjmując y jako argument reprezentujący stan układu w chwilach i od 1 do n . Definicja Vn ₍ y ) jest wartością otrzymaną w stanie y w ostatnim czasie n . Wartości V _i we wcześniejszych czasach i = n −1, n − 2, ..., 2, 1 można znaleźć, działając wstecz, stosując rekurencyjną zależność zwaną równaniem Bellmana . Dla i = 2, ..., n , V _{i −1} w dowolnym stanie y oblicza się z V _i przez maksymalizację prostej funkcji (zwykle sumy) zysku z decyzji w czasie i − 1 i funkcji V _i w nowym stanie systemu, jeśli taka decyzja zostanie podjęta. Ponieważ V _i zostało już obliczone dla potrzebnych stanów, powyższa operacja daje V _{i −1} dla tych stanów. Ostatecznie V ₁ w stanie początkowym układu jest wartością rozwiązania optymalnego. Optymalne wartości zmiennych decyzyjnych można odzyskać, jeden po drugim, śledząc wstecz już wykonane obliczenia.

Teoria sterowania

W teorii sterowania $że$ problemem jest znalezienie dopuszczalnej kontroli , która powoduje system ${\ Displaystyle {\ kropka {\ mathbf {x}}} (t) = \ mathbf {g} \ lewo (\ mathbf {x} (t), \ mathbf {u} (t), t \ prawo )}$ podążać po dopuszczalnej trajektorii w ciągłym przedziale czasu $równoważnik t_ {1} }$$Displaystyle t_$ minimalizuje funkcję kosztu

${\ Displaystyle J = b \ lewo (\ mathbf {x} (t_ {1}),t_{1}\right)+\int _{t_{0}}^{t_{1}}f\left(\mathbf {x} (t),\mathbf {u} (t) ,t\prawo)\mathrm {d} t}$

Rozwiązaniem $_ )} , co$$^ {\ ast}}$ optymalną trajektorię i funkcję kosztu utrzymania $x ∗$ . Ten ostatni jest zgodny z podstawowym równaniem programowania dynamicznego:

${\ Displaystyle -J_ {t} ^{\ast }=\min _{\mathbf {u} }\left\{f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)+J_{x }^{\ast {\mathsf {T}}}\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)\right\}}$

równanie różniczkowe cząstkowe znane jako równanie Hamiltona-Jacobiego-Bellmana , w którym ${\ displaystyle J_ {x} ^ {\ ast } = {\ frac {\ częściowe J ^ {\ ast}} {\ częściowe \ mathbf {x} }} = \ lewo [{\ frac {\ częściowe J ^ {\ ast} }{\częściowe x_{1}}}~~~~{\frac {\częściowe J^{\ast}}{\częściowe x_{2}}}~~~~\dots ~~~~{\frac { \ częściowy J ^ {\ ast}} {\ częściowy x_ {n}}} \ prawo] ^ {\ mathsf {T}}} i J t ∗ = ∂$ J $} ^ {\ ast }={\frac {\częściowe J^{\ast}}{\częściowe t}}}$ . Można stwierdzić, że minimalizowanie $\$$\ Displaystyle$ , x $mathbf {x}}$ i nieznanej funkcji ${\ Displaystyle J_ {x} ^ {\ ast}},$ a następnie podstawia wynik do równania Hamiltona – Jacobiego – Bellmana, aby rozwiązać równanie różniczkowe cząstkowe z warunkiem brzegowym ${\ Displaystyle J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)}$ . W praktyce wymaga to na ogół technik numerycznych dla pewnego dyskretnego przybliżenia dokładnej relacji optymalizacji.

Alternatywnie, proces ciągły można przybliżyć za pomocą układu dyskretnego, co prowadzi do następującej relacji rekurencyjnej, analogicznej do równania Hamiltona – Jacobiego – Bellmana:

${\ Displaystyle J_ {k} ^ {\ ast} \ lewo (\ mathbf {x} _ {nk} \ prawej) = \ min _ {\ mathbf {u} _ {nk}} \ lewo \ {{\ kapelusz {f}}\left(\mathbf {x} _{nk},\mathbf {u} _{nk}\right)+J_{k-1}^{\ast}\left({\hat {\mathbf {g} }}\left(\mathbf {x} _{nk},\mathbf {u} _{nk}\right)\right)\right\}}$

na $fa$ etapie równo rozmieszczonych dyskretnych przedziałów czasowych i gdzie $\ Displaystyle {\ kapelusz {f}}}$$i$ ^ ${g}}}}$$Displaystyle {\ kapelusz {\$$\ displaystyle \ mathbf {g}}$ oznaczają dyskretne przybliżenia do i $sol sol$ . To równanie funkcjonalne jest znane jako równanie Bellmana , które można rozwiązać dla dokładnego rozwiązania dyskretnego przybliżenia równania optymalizacji.

Przykład z ekonomii: problem optymalnego oszczędzania Ramseya

Zobacz też: model Ramseya – Cass – Koopmansa

W ekonomii celem jest generalnie maksymalizacja (a nie minimalizowanie) jakiejś dynamicznej funkcji dobrobytu społecznego . W problemie Ramseya funkcja ta wiąże wielkość konsumpcji z poziomami użyteczności . Luźno mówiąc, planista staje przed wyborem między konsumpcją współczesną a konsumpcją przyszłą (poprzez inwestycje w kapitał wykorzystywany w produkcji), znany jako wybór międzyokresowy . Przyszłe zużycie jest dyskontowane według stałej stawki ${\ Displaystyle \ beta \ w (0,1)}$ . Dyskretne przybliżenie równania przejścia kapitału jest podane przez

${\ Displaystyle k_ {t + 1} = {\ kapelusz {g}} \ lewo (k_ {t}, c_ { t}\right)=f(k_{t})-c_{t}}$

gdzie $funkcja$$konsumpcja$ , $.$ kapitał, to produkcji spełniająca warunki Inady Zakłada się kapitał początkowy ${\ displaystyle k_ {0}> 0} .$

Niech do $\ displaystyle c_ {t}}$ będzie konsumpcją w okresie t i załóżmy, że konsumpcja daje użyteczność ${\ Displaystyle u (c_ {t}) = \ ln (c_ { t})}$ tak długo, jak konsument żyje. Załóżmy, że konsument jest niecierpliwy, więc dyskontuje przyszłą użyteczność o współczynnik b w każdym okresie, gdzie ${\ displaystyle 0 <b <1}$ . Niech ${\ displaystyle k_ {t}}$ będzie kapitałem w okresie t . Załóżmy, $+$ kwotą ${\ displaystyle k_ { t + 1} = Ak_ {t} ^ {a} -c_ {t}}$ załóżmy, że kapitał i konsumpcja tego okresu określają kapitał następnego okresu jako , gdzie A jest stałą dodatnią i ${\ Displaystyle 0 <a <1}$ . Załóżmy, że kapitał nie może być ujemny. Wtedy problem decyzyjny konsumenta można zapisać w następujący sposób:

${\ Displaystyle \ max \ suma _ {t = 0} ^ {T} b ^ {t} \ ln (c_ {t})} z$ zastrzeżeniem ${\ Displaystyle k_ {t + 1} = Ak_ {t} ^ {a} -c_ {t} \ geq 0}$ dla wszystkich ${\ styl wyświetlania t=0,1,2,\ldkropki ,T}$

Zapisany w ten sposób problem wygląda na skomplikowany, ponieważ wymaga rozwiązania dla wszystkich zmiennych wyboru ${\ Displaystyle c_ {0}, c_ {1}, c_ {2}, \ ldots ,c_{T}}$ . (Kapitał nie jest zmienną wyboru - kapitał początkowy konsumenta jest przyjmowany jako dany $)$

Podejście programowania dynamicznego do rozwiązania tego problemu polega na podzieleniu go na sekwencję mniejszych decyzji. $Displaystyle t$ definiujemy sekwencję funkcji wartości dla $V_{t}(k)$ which represent the value of having any amount of capital k at each time t. There is (by assumption) no utility from having capital after death, $V_{T+1}(k)=0$.

Wartość dowolnej ilości kapitału w jakimkolwiek wcześniejszym czasie można obliczyć metodą indukcji wstecznej za pomocą równania Bellmana . W tym problemie dla każdego równanie Bellmana to ${\ Displaystyle t = 0,1,2, \ ldots, T}$

${\ Displaystyle V_ {t} (k_ {t}) \, = \ \ max \ lewo (\ ln (c_ {t}) + b V_ {t + 1} (k_ {t + 1}) \ prawej)} z$ zastrzeżeniem $\ Displaystyle k_ {t + 1}=Ak_{t}^{a}-c_{t}\geq 0}$

$}$ { \ $t}$ . Intuicyjnie, zamiast wybierać plan na całe życie w momencie narodzin, konsument może robić wszystko krok po kroku. W chwili t podany jest $+1}}$ obecny kapitał $on$ musi tylko wybrać bieżącą konsumpcję $} }$ oszczędzać. $k_$ .

Aby faktycznie rozwiązać ten problem, pracujemy wstecz. Dla uproszczenia aktualny poziom kapitału oznaczamy jako k . ${\ Displaystyle V_ {T + 1} (k)}$ jest już znany, więc używając równania Bellmana, gdy możemy obliczyć, ${\ Displaystyle V_ {T} (k)$ } i tak dalej $aż$ dojdziemy do wartością początkowego problemu decyzyjnego dla całego życia. Innymi $k)}$ gdy już wiemy $k$ możemy obliczyć $V_$ , co jest maksimum ${\ Displaystyle \ ln (c_ {Tj}) + bV_ {T -j + 1} (Ak ^ {a} -c_ {Tj})}$ , gdzie ${\ Displaystyle c_ {Tj}}$ jest zmienną wyboru i ${\ Displaystyle Ak ^{a}-c_{Tj}\geq 0}$ .

Działając wstecz, można pokazać, że funkcja wartości w czasie jest ${\ displaystyle t = Tj}$

${\ Displaystyle V_ {Tj} (k) \ = \ a \ suma _ {i = 0}$

gdzie każdy $jot {\$$Tj$ , a optymalna ilość do spożycia w czasie to

${\ Displaystyle c_ {Tj} (k) \ = \, {\ Frac {1} {\ suma _ {i = 0$

do czego można uprościć

${\ Displaystyle {\ rozpocząć {wyrównane} c_ {T} (k) & = Ak ^ {a} \\ c_ {T-1} (k) & = {\ Frac {Ak ^ {a}} {1+ab}}\\c_{T-2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}}}\\&\ kropki \\c_{2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^ {T-2}}}\\c_{1}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{ T-2}b^{T-2}+a^{T-1}b^{T-1}}}\\c_{0}(k)&={\frac {Ak^{a}}{ 1+ab+a^{2}b^{2}+\ldokropki +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}+a^ {T}b^{T}}}\end{wyrównane}}}$

Widzimy, że optymalne jest konsumowanie większej części obecnego bogactwa wraz z wiekiem, ostatecznie konsumując całe pozostałe bogactwo w okresie T , ostatnim okresie życia.

Programowanie komputerowe

Istnieją dwa kluczowe atrybuty, które musi posiadać problem, aby można było zastosować programowanie dynamiczne: optymalna podstruktura i nakładające się podproblemy . Jeśli problem można rozwiązać, łącząc optymalne rozwiązania nienakładających się podproblemów, strategia nazywa się „ dziel i zwyciężaj ”. Z tego powodu sortowanie przez scalanie i sortowanie szybkie nie są klasyfikowane jako problemy programowania dynamicznego.

Optymalna podstruktura oznacza, że ​​rozwiązanie danego problemu optymalizacyjnego można uzyskać przez połączenie optymalnych rozwiązań jego podproblemów. Takie optymalne podstruktury są zwykle opisywane za pomocą rekurencji . Na przykład, biorąc pod uwagę graf G=(V,E) , najkrótsza ścieżka p od wierzchołka u do wierzchołka v wykazuje optymalną podstrukturę: weź dowolny pośredni wierzchołek w na tej najkrótszej ścieżce p . Jeśli p jest naprawdę najkrótszą ścieżką, to można ją podzielić na ścieżki podrzędne p ₁ od u do w i p ₂ od w do v tak, że te z kolei są rzeczywiście najkrótszymi ścieżkami między odpowiednimi wierzchołkami (przez proste argument „wytnij i wklej” opisany we Wstępie do algorytmów ). W związku z tym można łatwo sformułować rozwiązanie polegające na znajdowaniu najkrótszych ścieżek w sposób rekurencyjny, co algorytm Bellmana – Forda lub algorytm Floyda – Warshalla .

Nakładające się podproblemy oznaczają, że przestrzeń podproblemów musi być mała, to znaczy każdy rekurencyjny algorytm rozwiązujący problem powinien rozwiązywać w kółko te same podproblemy, zamiast generować nowe podproblemy. Rozważmy na przykład formułę rekurencyjną do generowania ciągu Fibonacciego: F _i = F _{i −1} + F _{i −2} , z przypadkiem podstawowym F ₁ = F ₂ = 1. Wówczas F ₄₃ = F ₄₂ + F ₄₁ i F ₄₂ = fa ₄₁ + fa ₄₀ . Teraz F ₄₁ jest rozwiązywany w rekurencyjnych poddrzewach zarówno F ₄₃ , jak i F ₄₂ . Mimo że całkowita liczba podproblemów jest w rzeczywistości niewielka (tylko 43 z nich), ostatecznie rozwiązujemy te same problemy w kółko, jeśli przyjmiemy naiwne rozwiązanie rekurencyjne, takie jak to. Programowanie dynamiczne uwzględnia ten fakt i rozwiązuje każdy podproblem tylko raz.

Rysunek 2. Wykres podproblemu dla ciągu Fibonacciego. Fakt, że nie jest to drzewo, wskazuje na nakładające się podproblemy.

Można to osiągnąć na dwa sposoby:

• Podejście odgórne : Jest to bezpośredni wynik rekurencyjnego sformułowania dowolnego problemu. Jeśli rozwiązanie dowolnego problemu można sformułować rekurencyjnie przy użyciu rozwiązania jego podproblemów, a jego podproblemy nakładają się, to można łatwo zapamiętać lub zapisać rozwiązania podproblemów w tabeli. Za każdym razem, gdy próbujemy rozwiązać nowy podproblem, najpierw sprawdzamy w tabeli, czy nie został on już rozwiązany. Jeśli rozwiązanie zostało zapisane, możemy użyć go bezpośrednio, w przeciwnym razie rozwiązujemy podproblem i dodajemy jego rozwiązanie do tabeli.
• Podejście oddolne : Kiedy sformułujemy rozwiązanie problemu rekurencyjnie, jeśli chodzi o jego podproblemy, możemy spróbować przeformułować problem w sposób oddolny: najpierw spróbuj rozwiązać podproblemy i wykorzystaj ich rozwiązania do zbudowania i dojść do rozwiązań większych podproblemów. Zwykle odbywa się to również w formie tabelarycznej poprzez iteracyjne generowanie rozwiązań coraz większych podproblemów przy użyciu rozwiązań małych podproblemów. Na przykład, jeśli znamy już wartości F ₄₁ i F ₄₀ , możemy bezpośrednio obliczyć wartość F ₄₂ .

Niektóre języki programowania mogą automatycznie zapamiętywać wynik wywołania funkcji z określonym zestawem argumentów, aby przyspieszyć ocenę wywołania według nazwy (ten mechanizm jest określany jako call-by-need ). Niektóre języki umożliwiają przenośność (np. Scheme , Common Lisp , Perl lub D ). Niektóre języki mają wbudowane automatyczne zapamiętywanie , na przykład tabled Prolog i J , który obsługuje zapamiętywanie z przysłówkiem M. . W każdym razie jest to możliwe tylko dla przezroczystej referencyjnie . Zapamiętywanie jest również spotykane jako łatwo dostępny wzorzec projektowy w językach opartych na przepisywaniu terminów, takich jak Wolfram Language .

Bioinformatyka

Programowanie dynamiczne jest szeroko stosowane w bioinformatyce do zadań takich jak dopasowanie sekwencji , fałdowanie białek , przewidywanie struktury RNA i wiązanie białko-DNA. Pierwsze dynamiczne algorytmy programowania wiązania białko-DNA zostały opracowane w latach 70. XX wieku niezależnie przez Charlesa DeLisi w USA oraz Georgii Gurskii i Alexandra Zasedateleva w ZSRR. Ostatnio algorytmy te stały się bardzo popularne w bioinformatyce i biologii obliczeniowej , szczególnie w badaniach pozycjonowania nukleosomów i wiązania czynników transkrypcyjnych .

Przykłady: algorytmy komputerowe

Algorytm Dijkstry dla problemu najkrótszej ścieżki

Z punktu widzenia programowania dynamicznego algorytm Dijkstry dla problemu najkrótszej ścieżki jest schematem kolejnych aproksymacji, który rozwiązuje równanie funkcyjne programowania dynamicznego dla problemu najkrótszej ścieżki metodą Reaching .

W rzeczywistości wyjaśnienie Dijkstry dotyczące logiki stojącej za algorytmem, a mianowicie

Zadanie 2. Znajdź ścieżkę o minimalnej całkowitej długości między dwoma podanymi węzłami i $P}$$\ displaystyle$ .

Korzystamy z faktu, że jeśli jest $węzłem$ na minimalnej ścieżce od $displaystyle$ drugim implikuje znajomość minimalnej ścieżki z $displaystyle P.$${\$$}$ do ${\ displaystyle R}$ .

jest parafrazą słynnej zasady optymalności Bellmana w kontekście problemu najkrótszej ścieżki .

ciąg Fibonacciego

Zastosowanie programowania dynamicznego do obliczania n -tego elementu ciągu Fibonacciego znacznie poprawia jego wydajność. Oto naiwna implementacja, oparta bezpośrednio na definicji matematycznej:

 funkcja  fib(n)  jeśli  n <= 1  powrót  n  powrót  fib(n − 1) + fib(n − 2) 

Zauważ, że jeśli wywołamy, powiedzmy, fib(5) , stworzymy drzewo wywołań, które wywołuje tę samą wartość wiele razy:

1. fikcja(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1) )

W szczególności fib(2) obliczono trzykrotnie od zera. W większych przykładach ponownie oblicza się znacznie więcej wartości fib lub podproblemów , co prowadzi do algorytmu czasu wykładniczego.

Załóżmy teraz, że mamy prosty obiekt map , m , który odwzorowuje każdą wartość fib , która została już obliczona, na jej wynik, i modyfikujemy naszą funkcję, aby z niej korzystała i aktualizowała. Wynikowa funkcja wymaga tylko O ( n ) zamiast czasu wykładniczego (ale wymaga przestrzeni O ( n )):

 var  m :=  map  (0 → 0, 1 → 1)  funkcja  fib(n)  jeśli  klucza  n  nie ma na  mapie  mm[n] := fib(n − 1) + fib(n − 2)  return  m[n] 

Ta technika zapisywania wartości, które zostały już obliczone, nazywana jest zapamiętywaniem ; jest to podejście odgórne, ponieważ najpierw dzielimy problem na podproblemy, a następnie obliczamy i przechowujemy wartości.

W podejściu oddolnym najpierw obliczamy mniejsze wartości fib , a następnie budujemy z nich większe wartości. Ta metoda również wykorzystuje czas O( n ), ponieważ zawiera pętlę, która powtarza się n − 1 razy, ale zajmuje tylko stałą (O(1)) przestrzeń, w przeciwieństwie do podejścia odgórnego, które wymaga przestrzeni O ( n ) do przechowywać mapę.

 0
    
         
             funkcja  fib(n)  if  n = 0  return  else  var  poprzedniFib := 0, currentFib := 1  powtórz  n − 1  razy  // pętla jest pomijana if n = 1  var  newFib := poprzedniFib + bieżącyFib poprzedniFib := aktualnyFib bieżącyFib := nowyFib  zwróć  bieżącyFib 

W obu przykładach obliczamy fib(2) tylko jeden raz, a następnie używamy go do obliczania zarówno fib(4), jak i fib(3) , zamiast obliczania go za każdym razem, gdy oceniany jest którykolwiek z nich.

Rodzaj zrównoważonej macierzy 0–1

Rozważmy problem przypisania wartości, zero lub jeden, do pozycji macierzy n × n , gdzie n jest parzyste, tak aby każdy wiersz i każda kolumna zawierały dokładnie n /2 zer i n /2 jedynek. Pytamy, ile jest różnych zadań dla danego ${\ displaystyle n}$ . Na przykład, gdy n = 4 , istnieje pięć możliwych rozwiązań

${\ Displaystyle {\ rozpocząć {bmatrix} 0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\koniec {bmatrix}}{\tekst {i}}}{\zacząć{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end {bmatrix}}{\text{ i }}{\begin{bmatrix}1&1&0&0\\0&0&1&1\\1&1&0&0\\0&0&1&1\end{bmatrix}}{\text{i }}{\begin{bmatrix}1&0&0&1\\0&1&1&0 \\0&1&1&0\\1&0&0&1\end{bmatrix}}{\text{ i }}{\begin{bmatrix}1&1&0&0\\1&1&0&0\\0&0&1&1\\0&0&1&1\end{bmatrix}}.}$

Istnieją co najmniej trzy możliwe podejścia: brutalna siła , wycofywanie się i programowanie dynamiczne.

Brutalna siła polega na sprawdzaniu wszystkich przypisań zer i jedynek oraz liczeniu tych, które mają zrównoważone wiersze i kolumny ( n /2 zer i n /2 jedynek). ${\ Displaystyle {\ tbinom {n} {n/2}} ^ {$ istnieją możliwe przypisania i $)$ sensowne zadań, ta strategia nie jest praktyczna, z wyjątkiem może do ${\ displaystyle n = 6}$ .

Powrót do tego problemu polega na wybraniu pewnej kolejności elementów macierzy i rekurencyjnym umieszczeniu jedynek lub zer, przy jednoczesnym sprawdzeniu, czy w każdym wierszu i kolumnie liczba elementów, które nie zostały przypisane, plus liczba jedynek lub zer, wynosi co najmniej n / 2 . Chociaż podejście to jest bardziej wyrafinowane niż brutalna siła, odwiedzi każde rozwiązanie raz, co czyni je niepraktycznym dla n większych niż sześć, ponieważ liczba rozwiązań wynosi już 116 963 796 250 dla n = 8, jak zobaczymy.

Programowanie dynamiczne umożliwia policzenie wielu rozwiązań bez odwiedzania ich wszystkich. Wyobraź sobie cofanie się wartości dla pierwszego wiersza – jakich informacji potrzebowalibyśmy o pozostałych wierszach, aby móc dokładnie policzyć rozwiązania uzyskane dla każdej wartości pierwszego wiersza? Rozważamy $2}$ k × n , gdzie 1 ≤ ≤ n , których $/$ zera i jedynki $displaystyle n$ . Funkcja f , do której zastosowano zapamiętywanie , odwzorowuje wektory n par liczb całkowitych na liczbę dopuszczalnych tablic (rozwiązań). W każdej kolumnie jest jedna para, a jej dwa składniki wskazują odpowiednio liczbę zer i jedynek, które jeszcze nie zostały umieszczone w tej kolumnie. Szukamy wartości ${\ Displaystyle f ((n/2, n / 2), (n/2, n/2), \ ldots (n/2, n/2)}} ($ argumenty $displaystyle$ jeden wektor elementów $n}$ ). Proces tworzenia $podproblemu$ obejmuje iterację każdego z dla górnego rzędu tablicy i przeglądanie jeden z odpowiedniego elementu pary dla tej kolumny, w zależności od tego, czy przypisanie dla górnego wiersza zawierało zero czy jedynkę na tej pozycji. Jeśli którykolwiek z wyników jest ujemny, to przypisanie jest nieważne i nie przyczynia się do zbioru rozwiązań (przystanki rekurencji). W przeciwnym razie mamy przypisanie dla górnego rzędu tablicy k × n i rekurencyjnie obliczamy liczbę rozwiązań dla pozostałej ( k − 1) × n planszy, dodając numery rozwiązań dla każdego dopuszczalnego przypisania górnego rzędu i zwracając suma, która jest zapamiętywana. Podstawowym przypadkiem jest trywialny podproblem, który występuje dla 1 × n . Liczba rozwiązań dla tej $1,0)}$ lub jeden, w zależności od / 2 $($ czy wektor jest permutacją i n ( $\ displaystyle$ par lub nie.

Na przykład na pierwszych dwóch planszach pokazanych powyżej byłyby to sekwencje wektorów

((2, 2) (2, 2) (2, 2) (2, 2)) ((2, 2) (2, 2) (2, 2) (2, 2)) k = 4 0 1 0 1 0 0 1 1 ((1, 2) (2, 1) (1, 2) (2, 1)) ((1, 2) (1, 2) (2, 1) (2, 1)) k = 3 1 0 1 0 0 0 1 1 ((1, 1) (1, 1) (1, 1) (1, 1)) ((0, 2) (0, 2) (2, 0) (2 , 0)) k = 2 0 1 0 1 1 1 0 0 ((0, 1) (1, 0) (0, 1) (1, 0)) ((0, 1) (0, 1) (1 , 0) (1, 0)) k = 1 1 0 1 0 1 1 0 0 ((0, 0) (0, 0) (0, 0) (0, 0)) ((0, 0) (0 , 0), (0, 0) (0, 0))

Liczba rozwiązań (sekwencja A058527 w OEIS ) wynosi

${\ Displaystyle 1, \, 2, \, 90, \, 297200, \, 116963796250, \, 6736218287430460752 ,\ldkropki}$

linków zewnętrznych można znaleźć linki do implementacji metody programowania dynamicznego przez MAPLE .

Szachownica

Rozważmy szachownicę z n × n kwadratów i funkcją kosztu c(i, j) , która zwraca koszt związany z kwadratem (i,j) ( i to wiersz, j to kolumna). Na przykład (na szachownicy 5 × 5),

5	6	7	4	7	8
4	7	6	1	1	4
3	3	5	7	8	2
2	–	6	7	0	–
1	–	–	*5*	–	–
	1	2	3	4	5

Zatem c(1, 3) = 5

Załóżmy, że istnieje szachownica, która może zaczynać się na dowolnym polu w pierwszym rzędzie (tj. rzędzie), a ty chcesz znać najkrótszą ścieżkę (suma minimalnych kosztów na każdym odwiedzonym rzędzie), aby dostać się do ostatniego rzędu; zakładając, że pionek może poruszać się tylko po przekątnej w lewo do przodu, po przekątnej w prawo do przodu lub prosto do przodu. Oznacza to, że pionek na (1,3) może przesunąć się na (2,2) , (2,3) lub (2,4) .

5
4
3
2		X	X	X
1			o
	1	2	3	4	5

Ten problem wykazuje optymalną podstrukturę . Oznacza to, że rozwiązanie całego problemu polega na rozwiązaniach podproblemów. Zdefiniujmy funkcję q(i, j) jako

q ( ​​i , j ) = minimalny koszt dotarcia do kwadratu ( i , j ).

Zaczynając od rangi n i schodząc do rangi 1 , obliczamy wartość tej funkcji dla wszystkich kwadratów na każdym kolejnym rzędzie. Wybranie kwadratu, który zawiera minimalną wartość na każdym poziomie, daje nam najkrótszą ścieżkę między rangą n a rangą 1 .

Funkcja q(i, j) jest równa minimalnemu kosztowi dotarcia do dowolnego z trzech kwadratów poniżej (ponieważ są to jedyne kwadraty, które mogą do niej dotrzeć) plus c(i, j) . Na przykład:

5
4			A
3		B	C	D
2
1
	1	2	3	4	5

${\ Displaystyle q (A) = \ min (q (B), q (C), q ( D))+c(A)\,}$

Teraz zdefiniujmy q(i, j) w nieco bardziej ogólny sposób:

${\ Displaystyle q (i, j) = {\ rozpocząć {przypadki} \ infty & j <1 {\ tekst {lub}} j> n \\ c (i, j) i i = 1 \\\ min (q (i -1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\text{inaczej.}}\end{przypadki}} }$

Pierwszy wiersz tego równania dotyczy planszy modelowanej jako kwadraty indeksowane na 1 przy najniższej granicy i n przy najwyższej granicy. Druga linia określa, co dzieje się na pierwszym poziomie; zapewnienie podstawy. Trzecia linia, rekurencja, jest ważną częścią. Reprezentuje A, B, C, D w przykładzie. Z tej definicji możemy wyprowadzić prosty kod rekurencyjny dla q(i, j) . W poniższym pseudokodzie n to rozmiar tablicy, c(i, j) to funkcja kosztu, a min() zwraca minimalną liczbę wartości:

          funkcja  minCost(i, j)  if  j < 1  or  j > n  return  infinity  else if  i = 1  return  c(i, j)  else  return  min  ( minCost(i-1, j-1), minCost(i-1, j), minKoszt(i-1, j+1) ) + c(i, j) 

Ta funkcja oblicza tylko koszt ścieżki, a nie rzeczywistą ścieżkę. Rzeczywistą ścieżkę omawiamy poniżej. To, podobnie jak przykład z liczbami Fibonacciego, jest strasznie powolne, ponieważ również wykazuje nakładających się problemów podrzędnych . Oznacza to, że wielokrotnie przelicza te same koszty ścieżki. Możemy jednak obliczyć to znacznie szybciej w sposób oddolny, jeśli przechowujemy koszty ścieżki w dwuwymiarowej tablicy q[i, j] zamiast używać funkcji. Pozwala to uniknąć ponownego obliczania; wszystkie wartości potrzebne dla tablicy q[i, j] są obliczane z wyprzedzeniem tylko raz. Wstępnie obliczone wartości dla (i, j) są po prostu wyszukiwane w razie potrzeby.

Musimy również wiedzieć, jaka jest rzeczywista najkrótsza ścieżka. W tym celu używamy innej tablicy p[i, j] ; tablica poprzednika . Ta tablica rejestruje ścieżkę do dowolnego kwadratu s . Poprzednik s jest modelowany jako przesunięcie względem indeksu (w q[i, j] ) wstępnie obliczonego kosztu ścieżki s . Aby zrekonstruować całą ścieżkę, szukamy poprzednika s , następnie poprzednika tego kwadratu, potem poprzednika tego kwadratu i tak dalej rekurencyjnie, aż dojdziemy do kwadratu początkowego. Rozważ następujący pseudokod:

 funkcja  obliczKrótkaPathArrays()  dla  x  od  1  do  n q[1, x] := c(1, x)  dla  y  od  1  do  n q[y, 0] := nieskończoność q[y, n + 1] := nieskończoność  dla  y  od  2  do  n  dla  x  od  1  do  n m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1]) q[y, x ] := m + c(y, x)  jeśli  m = q[y-1, x-1] p[y, x] := -1  w przeciwnym razie jeśli  m = q[y-1, x] p[y, x] := 0  inaczej  p[y, x] := 1 

Teraz reszta to prosta kwestia znalezienia minimum i wydrukowania go.

 funkcja  computeShortestPath() computeShortestPathArrays() minIndex := 1 min := q[n, 1]  for  i  od  2  do  n  if  q[n, i] < min minIndex := i min := q[n, i] printPath( n, minIndex) 

 funkcja  printPath(y, x)  print  (x)  print  ("<-")  if  y = 2  print  (x + p[y, x])  else  printPath(y-1, x + p[y, X]) 

Wyrównanie sekwencji

W genetyce dopasowanie sekwencji jest ważnym zastosowaniem, w którym niezbędne jest programowanie dynamiczne . Zwykle problem polega na przekształceniu jednej sekwencji w inną za pomocą operacji edycyjnych, które zastępują, wstawiają lub usuwają element. Każda operacja ma powiązany koszt, a celem jest znalezienie sekwencji zmian o najniższym łącznym koszcie .

Problem można naturalnie określić jako rekurencję, sekwencja A jest optymalnie edytowana w sekwencję B przez:

1. wstawienie pierwszego znaku B i wykonanie optymalnego wyrównania A i końca B
2. usunięcie pierwszego znaku A i wykonanie optymalnego wyrównania ogona A i B
3. zastąpienie pierwszego znaku A pierwszym znakiem B i wykonanie optymalnego wyrównania ogonów A i B.

Częściowe dopasowania można zestawić w macierzy, gdzie komórka (i,j) zawiera koszt optymalnego dopasowania A[1..i] do B[1..j]. Koszt w komórce (i,j) można obliczyć, dodając koszt odpowiednich operacji do kosztu sąsiednich komórek i wybierając optimum.

Istnieją różne warianty, patrz algorytm Smitha-Watermana i algorytm Needlemana-Wunscha .

Układanka Wieża Hanoi

Zestaw modeli Wież Hanoi (z 8 dyskami)

Animowane rozwiązanie zagadki Wieża Hanoi dla T(4,3) .

Wieża Hanoi lub Wieże Hanoi to gra matematyczna lub łamigłówka . Składa się z trzech prętów i kilku dysków o różnych rozmiarach, które można wsunąć na dowolny pręt. Układanka zaczyna się od dysków ułożonych w zgrabny stos w rosnącej kolejności wielkości na jednym pręcie, najmniejszy u góry, tworząc w ten sposób stożkowy kształt.

Celem układanki jest przeniesienie całego stosu na inny pręt, przestrzegając następujących zasad:

• Jednocześnie można przenosić tylko jeden dysk.
• Każdy ruch polega na wyjęciu górnego krążka z jednego z prętów i wsunięciu go na inny pręt, na inne krążki, które mogą już znajdować się na tym pręcie.
• Żaden dysk nie może być umieszczony na mniejszym dysku.

Rozwiązanie programowania dynamicznego polega na rozwiązaniu równania funkcjonalnego

S(n,h,t) = S(n-1,h,nie(h,t)) ; S(1,h,t) ; S(n-1,nie(h,t),t)

gdzie n oznacza liczbę krążków do przesunięcia, h oznacza pręt macierzysty, t oznacza pręt docelowy, not(h,t) oznacza trzeci pręt (ani h, ani t), „;” oznacza konkatenację i

S(n, h, t) := rozwiązanie problemu składającego się z n krążków, które należy przesunąć z pręta h na pręt t.

Dla n=1 problem jest trywialny, mianowicie S(1,h,t) = "przenieś krążek z pręta h na pręt t" (pozostał tylko jeden krążek).

Liczba ruchów wymaganych przez to rozwiązanie wynosi 2 ⁿ - 1. Jeśli celem jest maksymalizacja liczby ruchów (bez cykli), to równanie funkcyjne programowania dynamicznego jest nieco bardziej skomplikowane i wymagane są 3 ⁿ - 1 ruchy.

Łamigłówka upuszczania jajek

Poniżej znajduje się opis przykładu tej słynnej układanki z N=2 jajkami i budynkiem o H=36 pięter:

Załóżmy, że chcemy wiedzieć, z których pięter w 36-piętrowym budynku można bezpiecznie zrzucić jajka, a które spowodują pęknięcie jaj podczas lądowania (używając terminologii w języku angielskim , w której pierwsze piętro znajduje się na poziomie gruntu). Przyjmujemy kilka założeń:

• Jajko, które przetrwa upadek, może być ponownie użyte.
• Rozbite jajko należy wyrzucić.
• Efekt upadku jest taki sam dla wszystkich jaj.
• Jeśli jajko pęknie po upuszczeniu, rozbiłoby się, gdyby spadło z wyższego okna.
• Jeśli jajko przeżyje upadek, to przetrwa krótszy upadek.
• Nie jest wykluczone, że okna na pierwszym piętrze rozbijają jajka, ani nie jest wykluczone, że jaja mogą przetrwać okna na 36 piętrze.

Jeśli dostępne jest tylko jedno jajo, a chcemy mieć pewność uzyskania prawidłowego wyniku, eksperyment można przeprowadzić tylko w jeden sposób. Zrzuć jajko z okna na pierwszym piętrze; jeśli przeżyje, zrzuć go z okna drugiego piętra. Kontynuuj w górę, aż pęknie. W najgorszym przypadku ta metoda może wymagać 36 odchodów. Załóżmy, że dostępne są 2 jajka. Jaka jest najmniejsza liczba odchodów jaj, która gwarantuje zadziałanie we wszystkich przypadkach?

Aby wyprowadzić równanie funkcyjne programowania dynamicznego dla tej układanki, niech stan modelu programowania dynamicznego będzie parą s = (n, k), gdzie

n = liczba dostępnych jaj testowych, n = 0, 1, 2, 3, ..., N - 1.

k = liczba (kolejnych) pięter do przetestowania, k = 0, 1, 2, ... , H -1.

Na przykład s = (2,6) wskazuje, że dostępne są dwa jaja testowe, a 6 (kolejnych) pięter nie zostało jeszcze przetestowanych. Stan początkowy procesu to s = ( N , H ), gdzie N oznacza liczbę jaj testowych dostępnych na początku eksperymentu. Proces kończy się, gdy nie ma już jaj testowych ( n = 0) lub gdy k = 0, w zależności od tego, co nastąpi wcześniej. Jeśli zakończenie występuje w stanie s = (0, k ) i k > 0, to test się nie powiódł.

Teraz pozwól

W ( n , k ) = minimalna liczba prób wymaganych do określenia wartości dolnego poziomu krytycznego w najgorszym scenariuszu, przy założeniu, że proces jest w stanie s = ( n , k ).

Wtedy można to wykazać

W ( n , k ) = 1 + min{max ( W ( n - 1, x - 1), W ( n , k - x )): x = 1, 2, ..., k }

gdzie W ( n , 0) = 0 dla wszystkich n > 0 i W (1, k ) = k dla wszystkich k . Łatwo jest rozwiązać to równanie iteracyjnie, systematycznie zwiększając wartości n i k .

Szybsze rozwiązanie DP przy użyciu innej parametryzacji

$że$ powyższe rozwiązanie zajmuje DP $powtórzeniu$${\ Displaystyle W (n-1, x-1)}$ poprawić $wyszukiwanie$ optymalnego powyższym rośnie w ${\ Displaystyle x}$ , podczas gdy ${\ Displaystyle W (n, kx)}$ maleje w ${ \ Displaystyle x}$ , a więc lokalne minimum ${\ Displaystyle \ max (W (n-1, x-1), W (n,kx))}$ jest minimum globalnym. Ponadto, przechowując optymalną $komórki w tabeli DP i odnosząc się do jej wartości dla poprzedniej komórki,$ można znaleźć optymalną dla każdej komórki w stałym czasie, poprawiając ją do ${\ displaystyle x}$${\ Displaystyle O (nk)}$ czas. Istnieje jednak jeszcze szybsze rozwiązanie polegające na innej parametryzacji problemu:

Niech będzie całkowitą liczbą pięter, tak aby jajka pękły po upuszczeniu z $piętra$$($ powyższy przykład jest równoważny z wzięciem $\ displaystyle k = 37}$ .

Niech będzie $minimalną$ podłogą, z której jajko musi zostać upuszczone, aby zostało rozbite

Niech $($ maksymalną liczbą wartości , które można odróżnić za pomocą prób i jaj $fa ( t , n ) {$$t$$}$

Wtedy ${\ Displaystyle f (t, 0) = f (0, n) = 1}$ dla wszystkich ${\ Displaystyle t, n \ geq 0}$ .

Niech będzie $,$ z której spada pierwsze jajko w optymalnej strategii.

Jeśli pierwsze jajko pękło, $\$$n-1}$ 1 $displaystyle 1}$ do za $displaystyle a}$ i można je odróżnić za pomocą co najwyżej prób i $t-1}$$displaystyle$ jaj.

Jeśli pierwsze jajko nie pękło, $k$ od do $\ displaystyle$$}$ i można je odróżnić za pomocą i $} \displaystyle n}$${\ displaystyle t-1} m$ jajka.

Dlatego ${\ Displaystyle f (t, n) = f (t-1, n-1) + f (t-1,n)}$ .

Wtedy problem jest równoważny ze znalezieniem minimum $fa$ , że $\ Displaystyle f (x, n) \ geq k}$ .

Aby to zrobić, moglibyśmy obliczyć w kolejności rosnącej $} t}$$\ Displaystyle \ {f (t, i): 0 \ równoważnik i \ równoważnik n \}$ , co zajęłoby czas ${\ Displaystyle O (nx)} .$

$Tak$$więc$ jeśli przypadkiem zajmie

Ale w rzeczywistości relację powtarzalności można rozwiązać, dając $}}} ,$${\ Displaystyle f (t, n) = \ suma _ {i = 0} ^ {n} {\$${\ displaystyle {\ binom {t} {i + 1}} = {\ binom {t} {i}} {\ frac {ti} {i + 1}}} dla wszystkich ja ≥ {\ Displaystyle i$$)$ można obliczyć w czasie przy użyciu tożsamości \ $i\geq 0$.

Ponieważ ${\ Displaystyle f (t, n) \ równoważnik f (t + 1, n)}$ dla wszystkich ${\ Displaystyle t \ geq 0$ } może wyszukiwać binarnie, $znaleźć$$}$ ) { \ $log$

Mnożenie łańcucha macierzy

Główny artykuł: mnożenie łańcucha macierzy

Mnożenie łańcucha macierzowego jest dobrze znanym przykładem demonstrującym użyteczność programowania dynamicznego. Na przykład aplikacje inżynierskie często muszą mnożyć łańcuch macierzy. Nie jest zaskakujące znalezienie macierzy o dużych wymiarach, na przykład 100 × 100. Dlatego naszym zadaniem jest pomnożenie macierzy ${\ Displaystyle A_ {1}, A_ {2}, .... A_ {n}}$ . Mnożenie macierzy nie jest przemienne, ale asocjacyjne; a jednocześnie możemy mnożyć tylko dwie macierze. Możemy więc pomnożyć ten łańcuch macierzy na wiele różnych sposobów, na przykład:

((A ₁ × ZA ₂ ) × ZA ₃ ) × ... ZA _n

ZA ₁ × ((((A ₂ × ZA ₃ ) × ... ) × ZA _n )

(A ₁ × ZA ₂ ) × (A ₃ × ... A _n )

i tak dalej. Istnieje wiele sposobów na pomnożenie tego łańcucha macierzy. Wszystkie dadzą ten sam wynik końcowy, jednak obliczenie, na podstawie którego poszczególne macierze są mnożone, zajmie mniej lub więcej czasu. Jeśli macierz A ma wymiary m×n, a macierz B ma wymiary n×q, to ​​macierz C=A×B będzie miała wymiary m×q i będzie wymagała m*n*q mnożenia skalarnego (używając uproszczonego algorytmu mnożenia macierzy dla celów ilustracji).

Na przykład pomnóżmy macierze A, B i C. Załóżmy, że ich wymiary to odpowiednio m×n, n×p i p×s. Macierz A×B×C będzie miała rozmiar m×s i można ją obliczyć na dwa sposoby pokazane poniżej:

1. Ax(B×C) Ta kolejność mnożenia macierzy będzie wymagać nps + mns skalarnych mnożeń.
2. (A×B)×C Ta kolejność mnożenia macierzy będzie wymagała obliczeń skalarnych mnp + mps.

Załóżmy, że m = 10, n = 100, p = 10 i s = 1000. Pierwszy sposób pomnożenia łańcucha będzie wymagał 1 000 000 + 1 000 000 obliczeń. Drugi sposób będzie wymagał tylko 10 000+100 000 obliczeń. Oczywiście drugi sposób jest szybszy i powinniśmy pomnożyć macierze, używając tego układu nawiasów.

Dlatego nasz wniosek jest taki, że kolejność nawiasów ma znaczenie, a naszym zadaniem jest znalezienie optymalnej kolejności nawiasów.

W tym momencie mamy kilka możliwości, z których jedną jest zaprojektowanie algorytmu programowania dynamicznego, który podzieli problem na nakładające się problemy i obliczy optymalne rozmieszczenie nawiasów. Rozwiązanie programowania dynamicznego przedstawiono poniżej.

Nazwijmy m[i,j] minimalną liczbą mnożeń skalarnych potrzebnych do pomnożenia łańcucha macierzy od macierzy i do macierzy j (tj. A i × .... × A j , tj. _i < ₌ j). Rozdzielamy łańcuch na pewnej macierzy k, takiej, że i <= k < j, i próbujemy dowiedzieć się, która kombinacja daje minimum m[i,j].

Formuła to:

        if  i = j, m[i,j]= 0  if  i < j, m[i,j]= min po wszystkich możliwych wartościach k  (m[i,k]+m[k+1,j] + ${\ Displaystyle p_ {i-1} * p_ {k} * p_ {j}}$ )  

gdzie k waha się od i do j - 1.

• ${\ displaystyle p_ {i-1}}$ jest wymiarem wiersza macierzy i,
• ${\ displaystyle p_ {k}}$ jest wymiarem kolumnowym macierzy k,
• ${\ displaystyle p_ {j}}$ jest wymiarem kolumnowym macierzy j.

Formułę tę można zakodować w sposób pokazany poniżej, gdzie parametrem wejściowym „łańcuch” jest łańcuch macierzy, tj. ${\ Displaystyle A_ {1}, A_ {2}, ... A_ {n}}$ :

    
            
                 function  OptimalMatrixChainParenthesis(łańcuch) n = długość(łańcuch)  dla  i = 1, n m[i,i] = 0  // Ponieważ nie trzeba wykonywać żadnych obliczeń, aby pomnożyć jedną macierz  dla  len = 2, n  dla  i = 1, n - len + 1 j = i + len -1 m[i,j] = nieskończoność  // Pierwsze obliczenie jest aktualizowane  dla  k = i, j-1  q = m[i, k] + m[k+1, j] + ${\ Displaystyle p_ {i-1} * p_ {k} * p_ {j}}$ if  q < m [i, j]  // Nowa kolejność nawiasów jest lepsza niż to, co mieliśmy  m[i, j] = q  // Aktualizuj  s[i, j] = k  // Zapisz, na którym k podzielić, tj. gdzie umieścić nawias 

Do tej pory obliczyliśmy wartości dla wszystkich możliwych m [ i , j ] , minimalną liczbę obliczeń potrzebnych do pomnożenia łańcucha od macierzy i do macierzy j , i zapisaliśmy odpowiedni „punkt podziału” s [ i , j ] . Na przykład, jeśli mnożymy łańcuch A ₁ × A ₂ × A ₃ × A ₄ i okazuje się, że m [1, 3] = 100 i s [1, 3] = 2 , oznacza to, że optymalne rozmieszczenie nawiasy dla macierzy od 1 do 3 to ${\ Displaystyle (A_ {1} \ razy A_ {2}) \ razy A_ {3}}$ i pomnożenie tych macierzy będzie wymagało 100 obliczeń skalarnych.

Ten algorytm utworzy „tabele” m [, ] i s [, ], które będą zawierały wpisy dla wszystkich możliwych wartości i oraz j. Ostatecznym rozwiązaniem dla całego łańcucha jest m[1, n], z odpowiednim podziałem na s[1, n]. Rozwiązywanie rozwiązania będzie rekurencyjne, zaczynając od góry i kontynuując aż do przypadku bazowego, czyli mnożenia pojedynczych macierzy.

Dlatego następnym krokiem jest faktyczne podzielenie łańcucha, tj. umieszczenie nawiasów tam, gdzie (optymalnie) one należą. W tym celu moglibyśmy użyć następującego algorytmu:

 funkcja  PrintOptimalParenthesis(s, i, j)  if  i = j print "A"i  else  print "(" PrintOptimalParenthesis(s, i, s[i, j]) PrintOptimalParenthesis(s, s[i, j] + 1, j ) drukuj ")" 

Oczywiście ten algorytm nie jest przydatny do rzeczywistego mnożenia. Ten algorytm jest po prostu przyjaznym dla użytkownika sposobem sprawdzenia, jak wygląda wynik.

Aby faktycznie pomnożyć macierze przy użyciu odpowiednich podziałów, potrzebujemy następującego algorytmu:

               
             
             

         
         
         
              
                
            
          
             
       
          

          
          
             
                
                  0
                   
                            
                 
       
            function  MatrixChainMultiply  (  łańcuch  od  1  do  n  )  // zwraca ostateczną macierz, tj. A1×A2×... ×An  OptimalMatrixChainParenthesis  (  łańcuch  od  1  do  n  )  // to da s[ . ] oraz m[ .  ] "tabele"   OptimalMatrixMultiplication  (  s  ,  łańcuch  od  1  do  n  ) //   funkcja  mnożenia  OptimalMatrixMultiplication  (  s  ,  i  ,  j  )  // zwraca wynik pomnożenia łańcucha macierzy od Ai do Aj w optymalny sposób,  jeśli  i  <  j  / / kontynuuj dzielenie łańcucha i mnożenie macierzy po lewej i prawej stronie  LeftSide  =  OptimalMatrixMultiplication  (  s  ,  i  ,  s  [  i  ,  j  ])  Right Side  =  OptimalMatrixMultiplication  (  s  ,  s  [  i  ,  j  ]  +  1  ,  j  )  return  MatrixMultiply  (  LeftSide  ,  RightSide  )  else  if  i  =  j  zwróć  Ai  // macierz na pozycji i  else  wypisz  „błąd, i <= j musi się trzymać”  funkcja  MatrixMultiply  (  A  ,  B  )  // funkcja mnożąca dwie macierze,  jeśli  kolumny  (  A  )  =  wiersze  (  b  )  dla  i  =  1  ,  wiersze  (  ZA  )  dla  j  =  1  ,  kolumny  (  B  )  do  [  ja  ,  j  ]  =  dla  k  =  1  ,  kolumny  (  ZA  )  do  [  ja  ,  j  ]  =  do  [  ja  ,  j  ]  +  A  [  i  ,  k  ]  *  B  [  k  ,  j  ]  return  C  inaczej  wypisz  „błąd, niezgodne wymiary”. 

Historia

Termin programowanie dynamiczne został pierwotnie użyty w latach czterdziestych XX wieku przez Richarda Bellmana do opisania procesu rozwiązywania problemów, w których należy znaleźć najlepsze decyzje jedna po drugiej. Do 1953 roku dopracował to do współczesnego znaczenia, odnosząc się w szczególności do zagnieżdżania mniejszych problemów decyzyjnych w większych decyzjach, a dziedzina ta została następnie uznana przez IEEE za temat analizy systemów i inżynierii . Wkład Bellmana jest pamiętany w nazwie równania Bellmana , głównego wyniku programowania dynamicznego, który ponownie przedstawia problem optymalizacji w formie rekurencyjnej .

Bellman wyjaśnia uzasadnienie terminu programowanie dynamiczne w swojej autobiografii Eye of the Hurricane: An Autobiography :

Jesienny kwartał (1950) spędziłem w RAND . Moim pierwszym zadaniem było znalezienie nazwy dla wieloetapowych procesów decyzyjnych. Interesującym pytaniem jest: „Skąd wzięła się nazwa programowanie dynamiczne?” Lata pięćdziesiąte nie były dobrym okresem dla badań matematycznych. Mieliśmy bardzo interesującego dżentelmena w Waszyngtonie, który nazywał się Wilson . Był sekretarzem obrony i faktycznie odczuwał patologiczny strach i nienawiść do słowa „badania”. Nie używam tego terminu lekko; Używam go dokładnie. Twarz mu się zalewała, robił się czerwony i stawał się agresywny, gdy ludzie używali w jego obecności terminu „badania”. Można więc sobie wyobrazić, jak się czuł w związku z terminem matematyczny. Korporacja RAND była zatrudniona przez Siły Powietrzne, a Siły Powietrzne miały zasadniczo Wilsona jako swojego szefa. Dlatego czułem, że muszę coś zrobić, aby ochronić Wilsona i Siły Powietrzne przed faktem, że naprawdę zajmowałem się matematyką w Korporacji RAND. Jaki tytuł, jakie imię mógłbym wybrać? Przede wszystkim interesowało mnie planowanie, podejmowanie decyzji, myślenie. Ale planowanie nie jest dobrym słowem z różnych powodów. Postanowiłem więc użyć słowa „programowanie”. Chciałem przekazać ideę, że to było dynamiczne, to było wieloetapowe, to było zmienne w czasie. Pomyślałem, upieczmy dwie pieczenie na jednym ogniu. Weźmy słowo, które ma absolutnie precyzyjne znaczenie, a mianowicie dynamiczny, w klasycznym sensie fizycznym. Ma również bardzo interesującą właściwość jako przymiotnik, a mianowicie niemożliwe jest użycie słowa dynamiczny w pejoratywnym znaczeniu. Spróbuj wymyślić jakąś kombinację, która prawdopodobnie nada mu pejoratywne znaczenie. To niemożliwe. Dlatego pomyślałem, że programowanie dynamiczne to dobra nazwa. To było coś, czemu nawet kongresman nie mógłby się sprzeciwić. Użyłem go więc jako parasola dla moich działań.

— Richard Bellman, Oko huraganu: autobiografia (1984, strona 159)

słowo „ dynamika” , aby uchwycić zmienny w czasie aspekt problemów i dlatego, że brzmiało imponująco. Słowo programowanie odnosiło się do zastosowania metody w celu znalezienia optymalnego programu w sensie wojskowego harmonogramu szkolenia lub logistyki. To użycie jest takie samo, jak w wyrażeniach programowanie liniowe i programowanie matematyczne , które są synonimem optymalizacji matematycznej .

Brakuje powyższego wyjaśnienia pochodzenia tego terminu. Jak napisali Russell i Norvig w swojej książce, odnosząc się do powyższej historii: „To nie może być do końca prawdą, ponieważ jego pierwszy artykuł, w którym użył tego terminu (Bellman, 1952), ukazał się, zanim Wilson został sekretarzem obrony w 1953 roku”. Jest też komentarz w przemówieniu Harolda J. Kushnera , w którym wspomina on Bellmana. Cytując Kushnera, gdy mówi o Bellmanie: „Z drugiej strony, kiedy zadałem mu to samo pytanie, odpowiedział, że próbuje przewyższyć liniowe programowanie Dantziga, dodając dynamikę. Być może obie motywacje były prawdziwe”.

Algorytmy wykorzystujące programowanie dynamiczne

• Powtarzające się rozwiązania modeli sieciowych do wiązania białko-DNA
• Indukcja wsteczna jako metoda rozwiązywania problemów optymalizacji dynamicznej w czasie dyskretnym o skończonym horyzoncie
• Metodę współczynników nieokreślonych można wykorzystać do rozwiązania równania Bellmana w problemach optymalizacji dynamicznej o nieskończonym horyzoncie, czasie dyskretnym, zdyskontowanych , niezmiennych w czasie
• Wiele algorytmów łańcuchowych , w tym najdłuższy wspólny podsekwencja , najdłuższy rosnący podsekwencja , najdłuższy wspólny podciąg , odległość Levenshteina (edycja odległości)
• Wiele problemów algorytmicznych na grafach można skutecznie rozwiązać dla grafów o ograniczonej szerokości drzewa lub ograniczonej szerokości kliki , stosując programowanie dynamiczne na dekompozycji drzewa grafu.
• Algorytm Cocke-Younger-Kasami (CYK) , który określa, czy i jak dany ciąg może zostać wygenerowany przez daną gramatykę bezkontekstową
• Algorytm zawijania słów Knutha , który minimalizuje poszarpanie podczas zawijania tekstu
• Wykorzystanie tablic transpozycji i tablic obalenia w szachach komputerowych
• Algorytm Viterbiego (używany do ukrytych modeli Markowa , a zwłaszcza w tagowaniu części mowy )
• Algorytm Earleya ( rodzaj parsera wykresów )
• Algorytm Needlemana-Wunscha i inne algorytmy stosowane w bioinformatyce , w tym dopasowanie sekwencji , dopasowanie strukturalne , przewidywanie struktury RNA
• Algorytm najkrótszej ścieżki Floyda dla wszystkich par
• Optymalizacja kolejności mnożenia macierzy łańcuchowej
• czasu pseudowielomianowego dla problemów sumy podzbioru , plecakowego i podziału
• Algorytm dynamicznego dopasowania czasu do obliczania globalnej odległości między dwoma szeregami czasowymi
• Selingera (aka System R ) do optymalizacji zapytań w relacyjnej bazie danych
• Algorytm De Boora do oceny krzywych B-sklejanych
• Metoda Duckwortha-Lewisa w celu rozwiązania problemu, gdy gry w krykieta są przerywane
• Metoda iteracji wartości do rozwiązywania procesów decyzyjnych Markowa
• Niektóre krawędzie obrazu graficznego są zgodne z metodami zaznaczania, takimi jak narzędzie zaznaczania „magnes” w programie Photoshop
• Niektóre metody rozwiązywania problemów z szeregowaniem interwałowym
• Niektóre metody rozwiązywania problemu komiwojażera , dokładnie (w czasie wykładniczym ) lub w przybliżeniu (np. poprzez wycieczkę bitoniczną )
• Rekurencyjna metoda najmniejszych kwadratów
• Śledzenie rytmu w wyszukiwaniu informacji muzycznych
• Strategia szkolenia adaptacyjno-krytycznego dla sztucznych sieci neuronowych
• Algorytmy stereo do rozwiązywania problemu korespondencji stosowane w widzeniu stereo
• Rzeźbienie szwów (zmiana rozmiaru obrazu uwzględniająca zawartość)
• Bellmana -Forda do znajdowania najkrótszej odległości na wykresie
• Niektóre przybliżone metody rozwiązania problemu przeszukiwania liniowego
• Algorytm Kadane'a dla problemu maksymalnej podtablicy
• Optymalizacja planów rozbudowy generacji elektrycznej w pakiecie Wein Automatic System Planning (WASP).

Zobacz też

• Wypukłość w ekonomii – Ważny temat w ekonomii
• Algorytm zachłanny – Sekwencja lokalnie optymalnych wyborów
• Niewypukłość (ekonomia) - Naruszenie założeń wypukłości elementarnej ekonomii
• Programowanie stochastyczne - Ramy modelowania problemów optymalizacyjnych z niepewnością
• Stochastyczne programowanie dynamiczne - 1957 technika modelowania problemów podejmowania decyzji w warunkach niepewności
• Uczenie ze wzmocnieniem - Dziedzina uczenia maszynowego

Dalsza lektura

•   Adda, Hieronim; Cooper, Russell (2003), Dynamiczna ekonomia , MIT Press, ISBN 9780262012010 . Przystępne wprowadzenie do programowania dynamicznego w ekonomii. Kod MATLAB do książki Archived 2020-10-09 at the Wayback Machine .
•   Bellman, Richard (1954), „Teoria programowania dynamicznego”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , 60 (6): 503–516, doi : 10.1090/S0002-9904-1954-09848-8 , MR 0067459 . Zawiera obszerną bibliografię literatury przedmiotu do roku 1954.
•   Bellman, Richard (1957), Programowanie dynamiczne , Princeton University Press . Wydanie Dover w miękkiej oprawie (2003), ISBN 0-486-42809-5 .
•   Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), Wprowadzenie do algorytmów (wyd. 2), MIT Press & McGraw – Hill, ISBN 978-0-262-03293-3 . Zwłaszcza s. 323–69.
•   Dreyfus, Stuart E.; Prawo, Averill M. (1977), Sztuka i teoria programowania dynamicznego , Academic Press, ISBN 978-0-12-221860-6 .
• Giegerich R.; Meyer, C.; Steffen, P. (2004), „Dyscyplina programowania dynamicznego na danych sekwencyjnych” (PDF) , Science of Computer Programming , 51 (3): 215–263, doi : 10.1016/j.scico.2003.12.005 .
•   Meyn, Sean (2007), Control Techniques for Complex Networks , Cambridge University Press, ISBN 978-0-521-88441-9 , zarchiwizowane od oryginału w dniu 19.06.2010 .
• Sritharan, SS (1991). „Dynamiczne programowanie równań Naviera-Stokesa”. Systemy i listy kontrolne . 16 (4): 299–307. doi : 10.1016/0167-6911(91)90020-f .
•   Stokey, Nancy ; Lucas, Robert E .; Prescott, Edward (1989), Recursive Methods in Economic Dynamics , Harvard Univ. Prasa, ISBN 978-0-674-75096-8 .

Linki zewnętrzne

• Samouczek dotyczący programowania dynamicznego
• Kurs MIT na temat algorytmów - Obejmuje 4 wykłady wideo na temat DP, wykłady 19-22
• Stosowane programowanie matematyczne autorstwa Bradleya, Haxa i Magnantiego, rozdział 11
• Więcej notatek DP
• King, Ian, 2002 (1987), „ Proste wprowadzenie do programowania dynamicznego w modelach makroekonomicznych ”. Wprowadzenie do programowania dynamicznego jako ważnego narzędzia w teorii ekonomii.
• Programowanie dynamiczne: od nowicjusza do zaawansowanego Artykuł Dumitru na stronie TopCoder.com dotyczący programowania dynamicznego
• Algebraic Dynamic Programming - sformalizowane ramy programowania dynamicznego, w tym kurs podstawowy do DP, University of Bielefeld
• Dreyfus, Stuart, „ Richard Bellman o narodzinach programowania dynamicznego ” .
• Kurs programowania dynamicznego
• Delikatne wprowadzenie do programowania dynamicznego i algorytmu Viterbiego
• Tabela Prolog BProlog , XSB , SWI-Prolog
• Interaktywne moduły programowania dynamicznego online IFORS , w tym najkrótsza ścieżka, komiwojażer, plecak, fałszywa moneta, upuszczenie jajka, most i pochodnia, wymiana, łańcuchowe produkty macierzowe i problem ścieżki krytycznej.