Dynamisk programmering

Ej att förväxla med Dynamiskt programmeringsspråk eller Dynamiskt problem .

Figur 1. Hitta den kortaste vägen i en graf med optimal understruktur; en rak linje indikerar en enda kant; en vågig linje indikerar den kortaste vägen mellan de två hörnen som den förbinder (bland andra vägar, ej visade, som delar samma två hörn); den fetstilta linjen är den totalt sett kortaste vägen från start till mål.

Dynamisk programmering är både en matematisk optimeringsmetod och en datorprogrammeringsmetod. Metoden utvecklades av Richard Bellman på 1950-talet och har hittat tillämpningar inom många områden, från flygteknik till ekonomi .

I båda sammanhangen syftar det på att förenkla ett komplicerat problem genom att bryta ner det i enklare delproblem på ett rekursivt sätt. Även om vissa beslutsproblem inte kan tas isär på detta sätt, går beslut som sträcker sig över flera tidpunkter ofta sönder rekursivt. På samma sätt, inom datavetenskap, om ett problem kan lösas optimalt genom att dela upp det i delproblem och sedan rekursivt hitta de optimala lösningarna på delproblemen, så sägs det ha optimal understruktur .

Om delproblem kan kapslas rekursivt inuti större problem, så att dynamiska programmeringsmetoder är tillämpliga, så finns det ett samband mellan värdet av det större problemet och värdena för delproblemen. I optimeringslitteraturen kallas detta förhållande för Bellman-ekvationen .

Översikt

Matematisk optimering

När det gäller matematisk optimering avser dynamisk programmering vanligtvis att förenkla ett beslut genom att dela upp det i en sekvens av beslutssteg över tiden. Detta görs genom att definiera en sekvens av värdefunktioner V ₁ , V ₂ , ..., Vn _med y som ett argument som representerar systemets tillstånd vid tidpunkterna i från 1 till n . Definitionen av Vn ₍ y ) är det värde som erhölls i tillstånd y vid den senaste tiden n . Värdena V _i vid tidigare tidpunkter i = n −1, n − 2, ..., 2, 1 kan hittas genom att arbeta baklänges, med hjälp av ett rekursivt samband som kallas Bellman-ekvationen . För i = 2, ..., n , beräknas V _{i −1} i vilket tillstånd som helst y från V _i genom att maximera en enkel funktion (vanligtvis summan) av vinsten från ett beslut vid tidpunkten i − 1 och funktionen V _i vid det nya tillståndet för systemet om detta beslut fattas. Eftersom Vi redan har beräknats för de nödvändiga tillstånden _{−1 ,} ger ovanstående operation Vi för dessa tillstånd _. Slutligen är V ₁ i systemets initiala tillstånd värdet av den optimala lösningen. De optimala värdena för beslutsvariablerna kan återställas, en efter en, genom att spåra de redan utförda beräkningarna.

Kontrollteori

I kontrollteorin är ett typiskt problem att hitta en tillåten kontroll $\mathbf {u} ^{\ast }$ som orsakar systemet ${\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right )$ för att följa en tillåten bana $\mathbf {x} ^{\ast }$ på ett kontinuerligt tidsintervall $t_{0}\leq t\leq t_{1}$ som minimerar en kostnadsfunktion

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

Lösningen på detta problem är en optimal kontrolllag eller policy $\mathbf {u} ^{\ast }=h(\mathbf {x} (t),t )$ , som ger en optimal bana $\mathbf {x} ^{\ast }$ och en återstående funktion $J^{\ast }$ . Den senare följer den grundläggande ekvationen för dynamisk programmering:

$-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\}$

en partiell differentialekvation känd som Hamilton–Jacobi–Bellman $-$ där t $\ ast }={\frac {\partial J^{\ast }}{\partial t}}}$ . Man finner att minimera $\mathbf {u}$ i termer av $t$ , $\mathbf {x}$ och den okända funktionen $J_{x}^ {\ast }$ och ersätter sedan resultatet i Hamilton–Jacobi–Bellman-ekvationen för att få den partiella differentialekvationen som ska lösas med gränsvillkor ${\$ . I praktiken kräver detta i allmänhet numeriska tekniker för någon diskret approximation till det exakta optimeringsförhållandet.

Alternativt kan den kontinuerliga processen approximeras av ett diskret system, vilket leder till en följande återfallsrelation analog med Hamilton–Jacobi–Bellmans ekvation:

$J_{k}^{\ast }\left(\mathbf {x} _{nk}\right)=\min _{\mathbf {u} _{nk}}\left\{{\hat {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\}$

vid $k$ -:e steget av $n$ jämnt fördelade diskreta tidsintervall, och där ${\hat {f}}$ och ${\hat {\ mathbf {g} }}$ betecknar diskreta approximationer till $f$ och $\mathbf {g}$ . Denna funktionella ekvation är känd som Bellman-ekvationen , som kan lösas för en exakt lösning av den diskreta approximationen av optimeringsekvationen.

Exempel från ekonomi: Ramseys problem med optimalt sparande

Se även: Ramsey–Cass–Koopmans modell

Inom ekonomi är målet generellt sett att maximera (snarare än att minimera) någon dynamisk social välfärdsfunktion . I Ramseys problem relaterar denna funktion mängder av konsumtion till nivåer av nytta . Löst talat står planeraren inför avvägningen mellan samtida konsumtion och framtida konsumtion (via investeringar i kapitalstock som används i produktionen), känd som intertemporal choice . Framtida förbrukning diskonteras med en konstant kurs $\beta \in (0,1)$ . En diskret approximation till kapitalets övergångsekvation ges av

$k_{t+1}={\hat {g}}\left(k_{t},c_{ t}\right)=f(k_{t})-c_{t}$

där $c$ är konsumtion, $k$ är kapital och $f$ är en produktionsfunktion som uppfyller Inada-villkoren . En startkapitalstock $k_{0}>0$ antas.

Låt $c_{t}$ vara konsumtion i period t , och anta att konsumtion ger nyttan $u(c_{t})=\ln(c_{ t})$ så länge konsumenten lever. Antag att konsumenten är otålig, så att han diskonterar framtida nytta med en faktor b varje period, där $0<b<1$ . Låt $k_{t}$ vara stort i period t . Antag att startkapital är ett givet belopp $k_{0}>0$ , och anta att denna periods kapital och konsumtion bestämmer nästa periods kapital som ${\displaystyle k_{ t+1}=Ak_{t}^{a}-c_{t}} ,$ där A är en positiv konstant och $0<a<1$ . Antag att kapital inte kan vara negativt. Då kan konsumentens beslutsproblem skrivas så här:

${\displaystyle \max \sum _{t=0}^{T}b^{t}\ln(c_{t})} med förbehåll$ för $k_{t+1}=Ak_{t}^{a}-c_{t}\geq 0$ för alla ${\ displaystyle t=0,1,2,\ldots ,T}$

Skrivet på det här sättet ser problemet komplicerat ut, eftersom det handlar om att lösa alla valvariabler $c_{0},c_{1},c_{2},\ldots ,c_{T}$ . (Det stora $k_{0}$ är inte en valvariabel – konsumentens startkapital tas som givet.)

Den dynamiska programmeringsmetoden för att lösa detta problem innebär att dela upp det i en sekvens av mindre beslut. För att göra det definierar vi en sekvens av värdefunktioner ${\displaystyle V_{t}(k)} ,$ för $t=0, 1,2,\ldots ,T,T+1$ som representerar värdet av att ha valfri mängd stort k vid varje tidpunkt t . Det finns (genom antagande) ingen nytta av att ha kapital efter döden, $V_{T+1}(k)=0$ .

Värdet av valfri kvantitet kapital vid något tidigare tillfälle kan beräknas genom bakåtinduktion med hjälp av Bellmans ekvation . I detta problem, för varje $t=0,1,2,\ldots ,T$ , är Bellmans ekvation

${\displaystyle V_{t}(k_{t})\,=\,\max \left (\ln(c_{t})+bV_{t+1}(k_{t+1})\right)} med förbehåll$ för $k_{t+ 1}=Ak_{t}^{a}-c_{t}\geq 0$

Det här problemet är mycket enklare än det vi skrev ner tidigare, eftersom det bara involverar två beslutsvariabler, $c_{t}$ och $k_{t+1}$ . Intuitivt, istället för att välja hela sin livstidsplan vid födseln, kan konsumenten ta saker ett steg i taget. Vid tidpunkten t anges hans nuvarande kapital ${\displaystyle k_{t}} , och han behöver bara välja aktuell förbrukning$$c_{t}$ och spara $k_{t +1}$ .

För att faktiskt lösa detta problem arbetar vi baklänges. För enkelhetens skull betecknas den nuvarande kapitalnivån som k . $V_{T+1}(k)$ är redan känd, så med Bellmans ekvation när vi en gång kan beräkna $V_{T}(k)$ , och så vidare tills vi kommer till $V_{0}(k)$ , vilket är värdet av det initiala beslutsproblemet för hela livet. Med andra ord, när vi väl känner till ${\displaystyle V_{T-j+1}(k)} ,$ kan vi beräkna $V_{Tj}( k)$ , vilket är maximum av $\ln(c_{Tj})+bV_{T -j+1}(Ak^{a}-c_{Tj})$ , där $c_{Tj}$ är valvariabeln och $Ak ^{a}-c_{Tj}\geq 0$ .

Om man arbetar baklänges kan det visas att värdefunktionen vid tidpunkten $t=Tj$ är

$V_{Tj}(k)\,=\,a\sum _{i=0}^ {j}a^{i}b^{i}\ln k+v_{Tj}$

där varje $v_{Tj}$ är en konstant, och den optimala mängden att konsumera vid tidpunkten $t=Tj$ är

$c_{Tj}(k)\,=\,{\frac {1}{\sum _{i=0} ^{j}a^{i}b^{i}}}Ak^{a}$

vilket kan förenklas till

${\begin{aligned}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}}}\\&\ prickar \\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}+\ldots +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}+a^ {T}b^{T}}}\end{aligned}}$

Vi ser att det är optimalt att konsumera en större del av nuvarande förmögenhet när man blir äldre, för att slutligen konsumera all återstående förmögenhet i period T , den sista perioden av livet.

Dataprogramering

Det finns två nyckelattribut som ett problem måste ha för att dynamisk programmering ska vara tillämplig: optimal understruktur och överlappande delproblem . Om ett problem kan lösas genom att kombinera optimala lösningar på icke-överlappande delproblem, kallas strategin istället för " dela och härska" . Det är därför sammanslagningssortering och snabbsortering inte klassificeras som dynamiska programmeringsproblem.

Optimal understruktur innebär att lösningen på ett givet optimeringsproblem kan erhållas genom kombinationen av optimala lösningar på dess delproblem. Sådana optimala understrukturer beskrivs vanligtvis med hjälp av rekursion . Till exempel, givet en graf G=(V,E) , den kortaste vägen p från en vertex u till en vertex v uppvisar optimal understruktur: ta vilken mellanliggande vertex w på denna kortaste väg p . Om p verkligen är den kortaste vägen, så kan den delas upp i undervägar p ₁ från u till w och p ₂ från w till v så att dessa i sin tur verkligen är de kortaste vägarna mellan motsvarande hörn (med den enkla klipp-och-klistra-argument som beskrivs i Introduktion till algoritmer ). Därför kan man enkelt formulera lösningen för att hitta de kortaste vägarna på ett rekursivt sätt, vilket är vad Bellman–Ford-algoritmen eller Floyd–Warshall-algoritmen gör.

Överlappande delproblem innebär att utrymmet för delproblem måste vara litet, det vill säga att varje rekursiv algoritm som löser problemet bör lösa samma delproblem om och om igen, snarare än att generera nya delproblem. Tänk till exempel på den rekursiva formuleringen för att generera Fibonacci-serien: F i ₌ Fi −1 _{+ F} i _{−2 ,} med basfallet F ₁ = F ₂ = 1. Sedan F ₄₃ = F ₄₂ + F ₄₁ och F ₄₂ = F41 + F40 . _{_ _} Nu löses F _{41 i de rekursiva delträden för} såväl F _{43 som} F ₄₂ . Även om det totala antalet delproblem faktiskt är litet (bara 43 av dem), slutar vi med att lösa samma problem om och om igen om vi antar en naiv rekursiv lösning som denna. Dynamisk programmering tar hänsyn till detta faktum och löser varje delproblem endast en gång.

Figur 2. Underproblemsgrafen för Fibonacci-sekvensen. Att det inte är ett träd indikerar överlappande delproblem.

Detta kan uppnås på något av två sätt:

• Uppifrån-och-ned-metoden : Detta är det direkta utfallet av den rekursiva formuleringen av alla problem. Om lösningen på något problem kan formuleras rekursivt med hjälp av lösningen på dess delproblem, och om dess delproblem överlappar, så kan man enkelt memorera eller lagra lösningarna på delproblemen i en tabell. När vi försöker lösa ett nytt delproblem kontrollerar vi först tabellen för att se om det redan är löst. Om en lösning har registrerats kan vi använda den direkt, annars löser vi delproblemet och lägger till dess lösning i tabellen.
• Bottom-up-metoden : När vi väl formulerat lösningen på ett problem rekursivt som i termer av dess delproblem, kan vi försöka omformulera problemet på ett bottom-up-sätt: försök lösa delproblemen först och använd deras lösningar för att bygga- på och komma fram till lösningar på större delproblem. Detta görs också vanligtvis i tabellform genom att iterativt generera lösningar på större och större delproblem genom att använda lösningarna på små delproblem. Till exempel, om vi redan känner till värdena på F ₄₁ och F ₄₀ , kan vi direkt beräkna värdet på F ₄₂ .

Vissa programmeringsspråk kan automatiskt memorera resultatet av ett funktionsanrop med en viss uppsättning argument, för att snabba upp call-by-name- utvärderingen (denna mekanism kallas call-by-need ). Vissa språk gör det möjligt portabelt (t.ex. Scheme , Common Lisp , Perl eller D ). Vissa språk har automatisk memoisering inbyggd, som tabell Prolog och J , som stöder memoisering med M. adverb. Detta är i alla fall endast möjligt för en referenstransparent funktion. Memoization påträffas också som ett lättillgängligt designmönster inom term-rewrite-baserade språk som Wolfram Language .

Bioinformatik

Dynamisk programmering används i stor utsträckning inom bioinformatik för uppgifter som sekvensanpassning , proteinveckning , RNA-strukturförutsägelse och protein-DNA-bindning. De första dynamiska programmeringsalgoritmerna för protein-DNA-bindning utvecklades på 1970-talet oberoende av Charles DeLisi i USA och Georgii Gurskii och Alexander Zasedatelev i USSR. Nyligen har dessa algoritmer blivit mycket populära inom bioinformatik och beräkningsbiologi , särskilt i studier av nukleosompositionering och transkriptionsfaktorbindning .

Exempel: datoralgoritmer

Dijkstras algoritm för problemet med kortaste vägen

Ur en dynamisk programmeringssynpunkt är Dijkstras algoritm för det kortaste vägproblemet ett successivt approximationsschema som löser den dynamiska programmeringsfunktionekvationen för det kortaste vägproblemet med Reaching -metoden.

Faktum är att Dijkstras förklaring av logiken bakom algoritmen, nämligen

Problem 2. Hitta vägen för minsta totala längd mellan två givna noder $P$ och $Q$ .

Vi använder det faktum att, om $R$ är en nod på den minimala vägen från $P$ till $Q$ , innebär kunskap om den senare kunskapen om den minimala vägen från ${\ displaystyle P}$ till $R$ .

är en parafrasering av Bellmans berömda Optimalitetsprincip i samband med problemet med kortaste vägen .

Fibonacci-sekvens

Genom att använda dynamisk programmering i beräkningen av den n: e medlemmen av Fibonacci-sekvensen förbättras dess prestanda avsevärt. Här är en naiv implementering, baserad direkt på den matematiska definitionen:

 funktion  fib(n)  om  n <= 1  returnerar  n  returnerar  fib(n − 1) + fib(n − 2) 

Lägg märke till att om vi anropar, säg, fib(5) , producerar vi ett anropsträd som anropar funktionen på samma värde många olika gånger:

1. fib(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) )

I synnerhet beräknades fib(2) tre gånger från början. I större exempel omräknas många fler värden för fib , eller delproblem , vilket leder till en exponentiell tidsalgoritm.

Anta nu att vi har ett enkelt kartobjekt , m , som mappar varje värde på fib som redan har beräknats till dess resultat, och vi modifierar vår funktion för att använda den och uppdatera den. Den resulterande funktionen kräver bara O ( n ) tid istället för exponentiell tid (men kräver O ( n ) utrymme):

 var  m :=  map  (0 → 0, 1 → 1)  funktion  fib(n)  om  nyckeln  n  inte finns i  kartan  mm[n] := fib(n − 1) + fib(n − 2)  returnerar  m[n] 

Denna teknik för att spara värden som redan har beräknats kallas memoization ; detta är uppifrån och ner-metoden, eftersom vi först delar upp problemet i delproblem och sedan beräknar och lagrar värden.

I bottom-up- metoden beräknar vi först de mindre värdena för fib och bygger sedan större värden från dem. Denna metod använder också O( n ) tid eftersom den innehåller en slinga som upprepas n − 1 gånger, men den tar bara konstant (O(1)) utrymme, i motsats till top-down-metoden som kräver O( n ) utrymme för att lagra kartan.

 0
    
         
             funktion  fib(n)  om  n = 0  returnera  annars  var  föregåendeFib := 0, aktuellFib := 1  upprepning  n − 1  gånger  // loop hoppas över om n = 1  var  newFib := föregåendeFib + nuvarandeFib föregåendeFib := aktuellFib aktuellFib := newFib  returnera  strömFib 

I båda exemplen beräknar vi bara fib(2) en gång och använder det sedan för att beräkna både fib(4) och fib(3) istället för att beräkna det varje gång någon av dem utvärderas.

En typ av balanserad 0–1-matris

Tänk på problemet med att tilldela värden, antingen noll eller ett, till positionerna för en n × n matris, med n jämn, så att varje rad och varje kolumn innehåller exakt n / 2 nollor och n / 2 ettor. Vi frågar hur många olika tilldelningar det finns för ett givet $n$ . Till exempel, när n = 4 , är fem möjliga lösningar

${\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}{\text{ och }}{\begin{bmatrix}0&0&1&1\\0&0&1&1\\\1&1&1&0\\\\\ {bmatrix}}{\text{ och }}{\begin{bmatrix}1&1&0&0\\0&0&1&1\\1&1&0&0\\0&0&1&1\end{bmatrix}}{\text{ och }}{\begin{bmatrix}1&0&0&1\\0&1&1&0 \\0&1&1&0\\1&0&0&1\end{bmatrix}}{\text{ och }}{\begin{bmatrix}1&1&0&0\\1&1&0&0\\0&0&1&1\\0&0&1&1\end{bmatrix}}.$

Det finns åtminstone tre möjliga tillvägagångssätt: brute force , backtracking och dynamisk programmering.

Brute force består av att kontrollera alla tilldelningar av nollor och ettor och räkna de som har balanserade rader och kolumner ( n /2 nollor och n /2 ettor). Eftersom det finns $2^{n^{2}}$ möjliga tilldelningar och ${\tbinom {n}{n/2}}^{n}$ vettiga uppdrag är denna strategi inte praktisk utom kanske upp till $n=6$ .

Backtracking för detta problem består av att välja någon ordning på matriselementen och rekursivt placera ettor eller nollor, samtidigt som man kontrollerar att i varje rad och kolumn antalet element som inte har tilldelats plus antalet ettor eller nollor båda är minst n / 2 . Även om det är mer sofistikerat än brute force, kommer detta tillvägagångssätt att besöka varje lösning en gång, vilket gör det opraktiskt för n större än sex, eftersom antalet lösningar redan är 116 963 796 250 för n = 8, som vi ska se.

Dynamisk programmering gör det möjligt att räkna antalet lösningar utan att besöka dem alla. Föreställ dig backtracking-värden för den första raden – vilken information skulle vi behöva om de återstående raderna, för att korrekt kunna räkna de lösningar som erhållits för varje första radvärde? Vi betraktar k × n brädor, där 1 ≤ k ≤ n , vars $k$ -rader innehåller $n/2$ nollor och $n/2$ ettor. Funktionen f på vilken memoisering tillämpas mappar vektorer av n par heltal till antalet tillåtna kort (lösningar). Det finns ett par för varje kolumn, och dess två komponenter anger respektive antal nollor och ettor som ännu inte har placerats i den kolumnen. Vi söker värdet på ${\displaystyle f((n/2,n/ 2),(n/2,n/2),\ldots (n/2,n/2))} ($ n $\displaystyle n}$ argument eller en vektor av $n$ element). Processen för att skapa delproblem innefattar att iterera över var och en av ${\tbinom {n}{n/2}}$ möjliga tilldelningar för den översta raden på tavlan, och gå igenom varje kolumn, subtrahera en från lämpligt element i paret för den kolumnen, beroende på om tilldelningen för den översta raden innehöll en nolla eller en etta vid den positionen. Om något av resultaten är negativt är tilldelningen ogiltig och bidrar inte till uppsättningen av lösningar (rekursionen slutar). Annars har vi en tilldelning för den översta raden på k × n -brädet och beräknar rekursivt antalet lösningar till den återstående ( k − 1) × n -brädet, lägger till antalet lösningar för varje tillåten tilldelning av den översta raden och returnerar summan som memoreras. Basfallet är det triviala delproblemet, som uppstår för ett 1 × n kort. Antalet lösningar för detta kort är antingen noll eller en, beroende på om vektorn är en permutation av n / 2 $\displaystyle (0,1)}$ och n / 2 $( 1,0)$ par eller inte.

Till exempel, i de två första brädorna som visas ovan skulle sekvenserna av vektorer vara

((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))

Antalet lösningar (sekvens A058527 i OEIS ) är

$1,\,2,\,90,\,297200,\,116963791,367503791,367503796,7625,3725,8256,8256,8256,8256,8256,8256,3626,8256,8256,8256,8256,8250 \ldots$

Länkar till MAPLE-implementeringen av den dynamiska programmeringsmetoden kan hittas bland de externa länkarna .

Schackbräde

Betrakta ett schackbräde med n × n rutor och en kostnadsfunktion c(i, j) som returnerar en kostnad förknippad med kvadrat (i,j) ( i är raden, j är kolumnen). Till exempel (på ett 5 × 5 schackbräde),

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

Alltså c(1, 3) = 5

Låt oss säga att det fanns en pjäs som kunde börja vid vilken ruta som helst på den första rangen (dvs raden) och du ville veta den kortaste vägen (summan av minimikostnaderna för varje besökt rang) för att komma till den sista rangen; antar att brickan endast kunde röra sig diagonalt vänster framåt, diagonalt höger framåt eller rakt fram. Det vill säga, en bricka på (1,3) kan flytta till (2,2) , (2,3) eller (2,4) .

5
4
3
2		x	x	x
1			o
	1	2	3	4	5

Detta problem uppvisar optimal understruktur . Det vill säga att lösningen på hela problemet bygger på lösningar på delproblem. Låt oss definiera en funktion q(i, j) som

q ( ​​i , j ) = den lägsta kostnaden för att nå kvadraten ( i , j ).

Med början vid rang n och sjunkande till rang 1 , beräknar vi värdet av denna funktion för alla kvadrater vid varje successiv rangordning. Att välja den kvadrat som har det lägsta värdet vid varje rang ger oss den kortaste vägen mellan rang n och rang 1 .

Funktionen q(i, j) är lika med den lägsta kostnaden för att komma till någon av de tre kvadraterna under den (eftersom det är de enda kvadraterna som kan nå den) plus c(i, j) . Till exempel:

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

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

Låt oss nu definiera q(i, j) i något mer allmänna termer:

$q(i,j)={\begin{cases}\infty &j<1{\text{ eller }}j>n\\c(i,j)&i=1\\\min(q(i) -1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\text{annars.}}\end{fall}}$

Den första raden i denna ekvation handlar om en tavla modellerad som rutor indexerade på 1 vid den lägsta gränsen och n vid den högsta gränsen. Den andra raden anger vad som händer vid den första rangen; tillhandahålla ett basfall. Den tredje raden, rekursionen, är den viktiga delen. Det representerar A,B,C,D -termerna i exemplet. Från denna definition kan vi härleda enkel rekursiv kod för q(i, j) . I följande pseudokod n storleken på kortet, c(i, j) är kostnadsfunktionen och min() returnerar minimum av ett antal värden:

          funktion  minCost(i, j)  om  j < 1  eller  j > n  returnerar  oändligt  annat om  i = 1  returnerar  c(i, j)  annars  returnerar  min  ( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j) 

Denna funktion beräknar bara vägkostnaden, inte den faktiska vägen. Vi diskuterar själva vägen nedan. Detta, som exemplet med Fibonacci-nummer, är fruktansvärt långsamt eftersom det också uppvisar attributet överlappande delproblem . Det vill säga, den räknar om samma vägkostnader om och om igen. Men vi kan beräkna det mycket snabbare på ett bottom-up-sätt om vi lagrar vägkostnader i en tvådimensionell matris q[i, j] snarare än att använda en funktion. Detta undviker omräkning; alla värden som behövs för array q[i, j] beräknas i förväg endast en gång. Förberäknade värden för (i,j) slås helt enkelt upp när det behövs.

Vi måste också veta vad den faktiska kortaste vägen är. För att göra detta använder vi en annan array p[i, j] ; en föregångare array . Denna array registrerar sökvägen till valfri kvadrat s . Föregångaren till s modelleras som en offset i förhållande till indexet (i q[i, j] ) för den förberäknade vägkostnaden för s . För att rekonstruera hela banan slår vi upp föregångaren till s , sedan föregångaren till den kvadraten, sedan föregångaren till den kvadraten, och så vidare rekursivt, tills vi når startrutan. Tänk på följande pseudokod:

 funktion  computeShortestPathArrays()  för  x  från  1  till  n q[1, x] := c(1, x)  för  y  från  1  till  n q[y, 0] := oändligt q[y, n + 1] := oändligt  för  y  från  2  till  n  för  x  från  1  till  n m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1]) q[y, x ] := m + c(y, x)  om  m = q[y-1, x-1] p[y, x] := -1  annars om  m = q[y-1, x] p[y, x] := 0  annars  p[y, x] := 1 

Nu är resten en enkel fråga om att hitta minimum och skriva ut det.

 funktion  computeShortestPath() computeShortestPathArrays() minIndex := 1 min := q[n, 1]  för  i  från  2  till  n  om  q[n, i] < min minIndex := i min := q[n, i] printPath( n, minIndex) 

 funktion  printPath(y, x)  print  (x)  print  ("<-")  om  y = 2  print  (x + p[y, x])  annars  printPath(y-1, x + p[y, x]) 

Sekvensjustering

Inom genetik är sekvensanpassning en viktig applikation där dynamisk programmering är väsentlig . Vanligtvis består problemet i att omvandla en sekvens till en annan med hjälp av redigeringsoperationer som ersätter, infogar eller tar bort ett element. Varje operation har en associerad kostnad, och målet är att hitta sekvensen av redigeringar med den lägsta totala kostnaden .

Problemet kan uttryckas naturligt som en rekursion, en sekvens A redigeras optimalt till en sekvens B genom att antingen:

1. infoga det första tecknet i B och utföra en optimal anpassning av A och svansen på B
2. ta bort det första tecknet i A och utföra den optimala justeringen av svansen på A och B
3. ersätter det första tecknet i A med det första tecknet i B och utför optimala justeringar av svansarna på A och B.

De partiella inriktningarna kan tabelleras i en matris, där cell (i,j) innehåller kostnaden för den optimala inriktningen av A[1..i] till B[1..j]. Kostnaden i cell (i,j) kan beräknas genom att addera kostnaden för de relevanta operationerna till kostnaden för dess närliggande celler och välja det optimala.

Det finns olika varianter, se Smith–Waterman-algoritmen och Needleman–Wunsch-algoritmen .

Tower of Hanoi pussel

En modelluppsättning av Towers of Hanoi (med 8 skivor)

En animerad lösning av Tower of Hanoi pussel för T(4,3) .

The Tower of Hanoi eller Towers of Hanoi är ett matematiskt spel eller pussel . Den består av tre spön och ett antal skivor i olika storlekar som kan glida på vilken spö som helst. Pusslet börjar med skivorna i en prydlig stapel i stigande storleksordning på ett spö, det minsta i toppen, vilket gör en konisk form.

Syftet med pusslet är att flytta hela stapeln till ett annat spö, i enlighet med följande regler:

• Endast en skiva kan flyttas åt gången.
• Varje drag består av att ta den övre skivan från en av stängerna och skjuta den på en annan stav, ovanpå de andra skivorna som kanske redan finns på den staven.
• Ingen skiva får placeras ovanpå en mindre skiva.

Den dynamiska programmeringslösningen består av att lösa den funktionella ekvationen

S(n,h,t) = S(n-1,h, inte(h,t)); S(l,h,t); S(n-1,inte(h,t),t)

där n anger antalet skivor som ska flyttas, h betecknar hemmaspö, t betecknar målspö, inte(h,t) anger det tredje spöet (varken h eller t), ";" betecknar sammanlänkning och

S(n, h, t) := lösning på ett problem bestående av n skivor som ska flyttas från stång h till stång t.

För n=1 är problemet trivialt, nämligen S(1,h,t) = "flytta en skiva från stång h till stång t" (det finns bara en skiva kvar).

Antalet drag som krävs av denna lösning är 2 ⁿ − 1. Om målet är att maximera antalet drag (utan att cykla) är den dynamiska programmeringsfunktionsekvationen något mer komplicerad och 3 ⁿ − 1 drag krävs.

Ägg tappa pussel

Följande är en beskrivning av förekomsten av detta berömda pussel som involverar N=2 ägg och en byggnad med H=36 våningar:

Anta att vi vill veta vilka våningar i en byggnad med 36 våningar som är säkra att tappa ägg från, och vilka som kommer att få äggen att gå sönder vid landning (med amerikansk engelsk terminologi, där första våningen är på marknivå). Vi gör några antaganden:

• Ett ägg som överlever ett fall kan användas igen.
• Ett trasigt ägg måste kasseras.
• Effekten av ett fall är densamma för alla ägg.
• Om ett ägg går sönder när det tappas, skulle det gå sönder om det tappas från ett högre fönster.
• Om ett ägg överlever ett fall, så skulle det överleva ett kortare fall.
• Det är inte uteslutet att fönstren på första våningen bryter ägg och det är inte heller uteslutet att ägg kan överleva fönstren på 36:e våningen.

Om endast ett ägg är tillgängligt och vi vill vara säkra på att få rätt resultat, kan experimentet utföras på endast ett sätt. Släpp ägget från fönstret på första våningen; om den överlever, släpp den från fönstret på andra våningen. Fortsätt uppåt tills det går sönder. I värsta fall kan denna metod kräva 36 spillning. Anta att 2 ägg är tillgängliga. Vilket är det lägsta antalet äggdroppningar som garanterat fungerar i alla fall?

För att härleda en dynamisk programmeringsfunktionekvation för detta pussel, låt tillståndet för den dynamiska programmeringsmodellen vara ett par s = (n,k), där

n = antal tillgängliga testägg, n = 0, 1, 2, 3, ..., N − 1.

k = antal (på varandra följande) våningar som ännu inte testats, k = 0, 1, 2, ... , H - 1.

Till exempel indikerar s = (2,6) att två testägg är tillgängliga och att 6 (på varandra följande) våningar ännu inte har testats. Det initiala tillståndet för processen är s = ( N , H ) där N anger antalet testägg som är tillgängliga vid experimentets början . Processen avslutas antingen när det inte finns fler testägg ( n = 0) eller när k = 0, beroende på vilket som inträffar först. Om avslutning sker vid tillstånd s = (0, k ) och k > 0, misslyckades testet.

Nu, låt

W ( n , k ) = minsta antal försök som krävs för att identifiera värdet av det kritiska golvet under det värsta scenariot givet att processen är i tillståndet s = ( n , k ).

Då kan man visa det

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

med W ( n ,0) = 0 för alla n > 0 och W (1, k ) = k för alla k . Det är lätt att lösa denna ekvation iterativt genom att systematiskt öka värdena på n och k .

Snabbare DP-lösning med en annan parametrisering

Lägg märke till att ovanstående lösning tar $O(nk^{2})$ tid med en DP-lösning. Detta kan förbättras till $O(nk\log k)$ tid genom binär sökning på den optimala $x$ i ovanstående upprepning, eftersom $W(n-1,x-1)$ ökar i $x$ medan $W(n,kx)$ minskar i ${ \displaystyle x}$ , alltså ett lokalt minimum av $\max(W(n-1,x-1),W (n,kx))$ är ett globalt minimum. Genom att lagra den optimala $x$ för varje cell i DP-tabellen och hänvisa till dess värde för föregående cell, kan den optimala $x$ för varje cell hittas i konstant tid, vilket förbättrar den till $O(nk)$ tid. Det finns dock en ännu snabbare lösning som innebär en annan parametrisering av problemet:

Låt $k$ vara det totala antalet våningar så att äggen går sönder när de tappas från ${\displaystyle k}:$ e våningen (exemplet ovan motsvarar att ta $k=37$ ).

Låt $m$ vara det lägsta golvet från vilket ägget måste släppas för att brytas.

Låt $f(t,n)$ vara det maximala antalet värden på $m$ som kan särskiljas med $t$ försök och $n$ ägg.

Då $f(t,0)=f(0,n)=1$ för alla $t,n\geq 0$ .

Låt $a$ vara golvet från vilket det första ägget släpps i den optimala strategin.

Om det första ägget gick sönder är $m$ från $1$ till $a$ och kan särskiljas med högst $t-1$ försök och $n-1$ ägg.

Om det första ägget inte gick sönder är $m$ från $a+1$ till $k$ och kan särskiljas med $t-1$ försök och ${ \displaystyle n}$ ägg.

Därför är $f(t,n)=f(t-1,n-1)+f (t-1,n)$ .

Då är problemet likvärdigt med att hitta minsta $x$ så att $f(x,n)\geq k$ .

För att göra det skulle vi kunna beräkna $\{f(t,i):0\leq i\leq n\}$ i ordning med ökande $t$ , vilket skulle ta $O(nx)$ tid.

Således, om vi hanterar fallet med ${\displaystyle n=1} separat$ , skulle algoritmen ta $O(n{\sqrt {k}})$ tid.

Men återfallsrelationen kan faktiskt lösas, vilket ger $f(t,n)=\summa _{i=0}^{n}{\ binom {t}{i}}$ , som kan beräknas i $O(n)$ tid med hjälp av identiteten ${\ displaystyle {\binom {t}{i+1}}={\binom {t}{i}}{\frac {ti}{i+1}}} för all i ≥ {\displaystyle i$ \ $i\geq 0$.

Eftersom $f(t,n)\leq f(t+1,n)$ för alla $t\geq 0$ , vi kan binär söka på $t$ för att hitta $x$ , vilket ger en ${\displaystyle O(n\log k)}-$ algoritm.

Matriskedjemultiplikation

Huvudartikel: Matriskedjemultiplikation

Matriskedjemultiplikation är ett välkänt exempel som visar användbarheten av dynamisk programmering. Till exempel måste ingenjörstillämpningar ofta multiplicera en kedja av matriser. Det är inte förvånande att hitta matriser med stora dimensioner, till exempel 100×100. Därför är vår uppgift att multiplicera matriserna $A_{1},A_{2},....A_{n}$ . Matrismultiplikation är inte kommutativ, utan associativ; och vi kan bara multiplicera två matriser åt gången. Så vi kan multiplicera denna kedja av matriser på många olika sätt, till exempel:

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

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

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

och så vidare. Det finns många sätt att multiplicera denna kedja av matriser. De kommer alla att producera samma slutresultat, men de kommer att ta mer eller mindre tid att beräkna, baserat på vilka specifika matriser som multipliceras. Om matris A har dimensionerna m×n och matris B har dimensionerna n×q, så kommer matris C=A×B att ha dimensionerna m×q och kommer att kräva m*n*q skalära multiplikationer (med en förenklad matrismultiplikationsalgoritm för ändamålet illustration).

Låt oss till exempel multiplicera matriserna A, B och C. Låt oss anta att deras dimensioner är m×n, n×p respektive p×s. Matrisen A×B×C kommer att ha storleken m×s och kan beräknas på två sätt som visas nedan:

1. Ax(B×C) Denna ordning av matrismultiplikation kommer att kräva nps + mns skalära multiplikationer.
2. (A×B)×C Denna ordning av matrismultiplikation kommer att kräva mnp + mps skalära beräkningar.

Låt oss anta att m = 10, n = 100, p = 10 och s = 1000. Så det första sättet att multiplicera kedjan kräver 1 000 000 + 1 000 000 beräkningar. Det andra sättet kräver bara 10 000+100 000 beräkningar. Uppenbarligen är det andra sättet snabbare, och vi bör multiplicera matriserna med det arrangemanget av parentes.

Därför är vår slutsats att parentesordningen spelar roll, och att vår uppgift är att hitta den optimala parentesordningen.

Vid det här laget har vi flera val, varav ett är att designa en dynamisk programmeringsalgoritm som delar upp problemet i överlappande problem och beräknar det optimala arrangemanget av parentes. Den dynamiska programmeringslösningen presenteras nedan.

Låt oss kalla m[i,j] det minsta antalet skalära multiplikationer som behövs för att multiplicera en kedja av matriser från matris i till matris j (dvs. A i × .... × A j , dvs i< ₌ j ₎ . Vi delar kedjan vid någon matris k, så att i <= k < j, och försöker ta reda på vilken kombination som ger minsta m[i,j].

Formeln är:

        om  i = j, m[i,j]= 0  om  i < j, m[i,j]= min över alla möjliga värden på k  (m[i,k]+m[k+1,j] + $p_{i-1}*p_{k}*p_{j}$ )  

där k sträcker sig från i till j − 1.

• $p_{i-1}$ är raddimensionen för matris i,
• $p_{k}$ är kolumndimensionen för matris k,
• $p_{j}$ är kolumndimensionen för matris j.

Denna formel kan kodas enligt nedan, där indataparametern "kedja" är kedjan av matriser, dvs $A_{1},A_{2},...A_{n}$ :

    
            
                 funktion  OptimalMatrixChainParenthesis(kedja) n = längd(kedja)  för  i = 1, n m[i,i] = 0 //  Eftersom det inte krävs några beräkningar för att multiplicera en matris  för  len = 2, n  för  i = 1, n - len + 1 j = i + len -1 m[i,j] = oändlighet  // Så att den första beräkningen uppdateras  för  k = i, j-1  q = m[i, k] + m[k+1, j] + $p_{i-1}*p_{k}*p_{j}$ om  q < m[i, j]  // Den nya ordningen av parenteser är bättre än vad vi hade  m[i, j] = q  // Uppdatera  s[i, j] = k  // Spela in vilken k som ska delas på, dvs var parentesen ska placeras 

Hittills har vi beräknat värden för alla möjliga m [ i , j ] , det minsta antalet beräkningar för att multiplicera en kedja från matris i s [ i , j ] till matris j , och vi har registrerat motsvarande "splitpunkt" . Till exempel, om vi multiplicerar kedja A ₁ ×A ₂ ×A ₃ ×A ₄ , och det visar sig att m [1, 3] = 100 och s [1, 3] = 2 , betyder det att den optimala placeringen av parentes för matriserna 1 till 3 är $(A_{1}\ gånger A_{2})\ gånger A_{3}$ och för att multiplicera dessa matriser krävs 100 skalära beräkningar.

Denna algoritm kommer att producera "tabeller" m [, ] och s [, ] som kommer att ha poster för alla möjliga värden på i och j. Den slutliga lösningen för hela kedjan är m[1, n], med motsvarande split vid s[1, n]. Att riva upp lösningen kommer att vara rekursivt, från toppen och fortsätta tills vi når basfallet, dvs multiplikation av enstaka matriser.

Därför är nästa steg att faktiskt splittra kedjan, dvs att placera parentesen där de (optimalt) hör hemma. För detta ändamål kan vi använda följande algoritm:

 funktion  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 ) skriv ut ")" 

Naturligtvis är denna algoritm inte användbar för faktisk multiplikation. Denna algoritm är bara ett användarvänligt sätt att se hur resultatet ser ut.

För att faktiskt multiplicera matriserna med de rätta uppdelningarna behöver vi följande algoritm:

               
             
             

         
         
         
              
                
            
          
             
       
          

          
          
             
                
                  0
                   
                            
                 
       
            funktion  MatrixChainMultiply  (  kedja  från  1  till  n  )  // returnerar den slutliga matrisen, dvs A1×A2×... ×An  OptimalMatrixChainParenthesis  (  kedja  från  1  till  n  )  // detta kommer att producera s[ . ] och M[ .  ] "tabeller"   OptimalMatrixMultiplication  (  s  ,  kedja  från  1  till  n  )  // multiplicerar faktiskt  funktionen  OptimalMatrixMultiplication  (  s  ,  i  ,  j  )  // returnerar resultatet av att multiplicera en kedja av matriser från Ai till Aj på optimalt sätt  om  i  <  j  / / fortsätt att dela kedjan och multiplicera matriserna i vänster och höger sida  LeftSide  =  OptimalMatrixMultiplication  (  s  ,  i  ,  s  [  i  ,  j  ]  )  RightSide  =  OptimalMatrixMultiplication  (  s  ,  s  [  i  ,  j  ]  +  1  ,  j )   returnera  MatrixMultiplication  (  LeftSide  ,  RightSide  )  else  if  i  =  j  return  Ai  // matris vid position i  else  print  "fel, i <= j måste hålla"  funktion  MatrixMultiply  (  A  ,  B  )  // funktion som multiplicerar två matriser  om  kolumner  (  A  )  =  rader  (  B  )  för  i  =  1  ,  rader  (  A  )  för  j  =  1  ,  kolumner  (  B  )  C  [  i  ,  j  ]  =  för  k  =  1  ,  kolumner  (  A  )  C  [  i  ,  j  ]  =  C  [  i  ,  j  ]  +  A  [  i  ,  k  ]  *  B  [  k  ,  j  ]  return  C  annars  skriv ut  "fel, inkompatibla mått." 

Historia

Termen dynamisk programmering användes ursprungligen på 1940-talet av Richard Bellman för att beskriva processen att lösa problem där man behöver hitta de bästa besluten efter varandra. År 1953 förfinade han detta till den moderna betydelsen, och syftade specifikt på att bygga in mindre beslutsproblem i större beslut, och fältet erkändes därefter av IEEE som ett ämne för systemanalys och ingenjörskonst . Bellmans bidrag kommer ihåg i namnet på Bellman-ekvationen , ett centralt resultat av dynamisk programmering som återger ett optimeringsproblem i rekursiv form.

Bellman förklarar resonemanget bakom termen dynamisk programmering i sin självbiografi, Eye of the Hurricane: An Autobiography :

Jag tillbringade höstkvartalet (1950) på RAND . Min första uppgift var att hitta ett namn för beslutsprocesser i flera steg. En intressant fråga är, "Var kom namnet, dynamisk programmering, ifrån?" 1950-talet var inga bra år för matematisk forskning. Vi hade en mycket intressant gentleman i Washington som hette Wilson . Han var försvarsminister, och han hade faktiskt en patologisk rädsla och hat mot ordet "forskning". Jag använder inte termen lättvindigt; Jag använder den exakt. Hans ansikte skulle svälla, han skulle bli röd och han skulle bli våldsam om folk använde termen forskning i hans närvaro. Du kan föreställa dig hur han kände sig då om termen matematisk. RAND Corporation var anställd av flygvapnet, och flygvapnet hade Wilson som sin chef, i huvudsak. Därför kände jag att jag var tvungen att göra något för att skydda Wilson och flygvapnet från det faktum att jag verkligen höll på med matematik inom RAND Corporation. Vilken titel, vilket namn, kunde jag välja? I första hand var jag intresserad av planering, av beslutsfattande, av att tänka. Men planering är inte ett bra ord av olika anledningar. Jag bestämde mig därför för att använda ordet "programmering". Jag ville komma över tanken att det här var dynamiskt, det här var flerstegs, det här var tidsvarierande. Jag tänkte, låt oss slå två flugor i en smäll. Låt oss ta ett ord som har en absolut precis innebörd, nämligen dynamiskt, i klassisk fysisk mening. Det har också en mycket intressant egenskap som adjektiv, och det är omöjligt att använda ordet dynamisk i en nedsättande mening. Försök att tänka på någon kombination som möjligen kommer att ge det en nedsättande betydelse. Det är omöjligt. Därför tyckte jag att dynamisk programmering var ett bra namn. Det var något som inte ens en kongressledamot kunde invända mot. Så jag använde den som ett paraply för mina aktiviteter.

— Richard Bellman, Eye of the Hurricane: An Autobiography (1984, sida 159)

Ordet dynamisk valdes av Bellman för att fånga den tidsvarierande aspekten av problemen, och för att det lät imponerande. Ordet programmering syftade på användningen av metoden för att hitta ett optimalt program , i betydelsen ett militärt schema för träning eller logistik. Denna användning är densamma som i fraserna linjär programmering och matematisk programmering , en synonym för matematisk optimering .

Ovanstående förklaring av termens ursprung saknas. Som Russell och Norvig har skrivit i sin bok med hänvisning till ovanstående berättelse: "Detta kan inte vara strikt sant, eftersom hans första papper som använder termen (Bellman, 1952) dök upp innan Wilson blev försvarsminister 1953." Det finns också en kommentar i ett tal av Harold J. Kushner , där han minns Bellman. Citerar Kushner när han talar om Bellman: "Å andra sidan, när jag ställde samma fråga till honom, svarade han att han försökte höja Dantzigs linjära programmering genom att lägga till dynamik. Kanske var båda motivationerna sanna."

Algoritmer som använder dynamisk programmering

• Återkommande lösningar till gittermodeller för protein-DNA-bindning
• Bakåtinduktion som en lösningsmetod för diskreta tidsdiskreta dynamiska optimeringsproblem med ändlig horisont
• Metod med obestämda koefficienter kan användas för att lösa Bellman-ekvationen i oändlig horisont, diskret tid, diskonterade , tidsinvarianta dynamiska optimeringsproblem
• Många strängalgoritmer inklusive längsta gemensamma delsekvens , längsta ökande delsekvens , längsta gemensamma delsträng , Levenshtein-avstånd (redigera avstånd)
• Många algoritmiska problem på grafer kan lösas effektivt för grafer med begränsad trädbredd eller begränsad klickbredd genom att använda dynamisk programmering på en träduppdelning av grafen.
• Cocke –Younger–Kasami (CYK) algoritmen som bestämmer om och hur en given sträng kan genereras av en given kontextfri grammatik
• Knuths ordlindningsalgoritm som minimerar ojämnhet vid radbrytning av text
• Användningen av transponeringstabeller och vederlagstabeller i datorschack
• Viterbi -algoritmen (används för dolda Markov-modeller , och särskilt i en del av taltaggning )
• Earley -algoritmen (en typ av diagramparser )
• Needleman -Wunsch-algoritmen och andra algoritmer som används inom bioinformatik , inklusive sekvensanpassning , strukturell anpassning , RNA-strukturförutsägelse
• Floyds algoritm för kortaste väg i alla par
• Optimera ordningen för kedjematrismultiplikation
• Pseudopolynomiska tidsalgoritmer för delmängdssumman , ryggsäcks- och partitionsproblem
• Den dynamiska tidsförvrängningsalgoritmen för att beräkna det globala avståndet mellan två tidsserier
• Selinger (alias System R )-algoritmen för optimering av relationsdatabasfrågor
• De Boor-algoritm för att utvärdera B-spline-kurvor
• Duckworth–Lewis metod för att lösa problemet när cricketspel avbryts
• Värde iterationsmetoden för att lösa Markovs beslutsprocesser
• Vissa grafiska bildkanter följer urvalsmetoder som valverktyget "magnet" i Photoshop
• Några metoder för att lösa intervallschemaproblem
• Några metoder för att lösa problemet med resandeförsäljare , antingen exakt (i exponentiell tid ) eller ungefärligt (t.ex. via den bitoniska turen )
• Rekursiv minsta kvadratmetod
• Beatspårning vid hämtning av musikinformation
• Adaptiv kritikerutbildningsstrategi för artificiella neurala nätverk
• Stereoalgoritmer för att lösa korrespondensproblemet som används i stereovision
• Sömskärning (innehållsmedveten bildstorleksändring)
• Bellman –Ford-algoritmen för att hitta det kortaste avståndet i en graf
• Några ungefärliga lösningsmetoder för det linjära sökproblemet
• Kadanes algoritm för det maximala subarray-problemet
• Optimering av expansionsplaner för elproduktion i paketet Wein Automatic System Planning (WASP).

Se även

• Konvexitet i ekonomi – Viktigt ämne i ekonomi
• Girig algoritm – Sekvens av lokalt optimala val
• Icke-konvexitet (ekonomi) – Brott mot konvexitetsantagandena för elementär ekonomi
• Stokastisk programmering – Ramverk för modellering av optimeringsproblem som innebär osäkerhet
• Stokastisk dynamisk programmering – 1957 teknik för att modellera problem med beslutsfattande under osäkerhet
• Reinforcement learning – Område för maskininlärning

Vidare läsning

•   Adda, Jerome; Cooper, Russell (2003), Dynamic Economics , MIT Press, ISBN 9780262012010 . En tillgänglig introduktion till dynamisk programmering inom ekonomi. MATLAB-kod för boken Arkiverad 2020-10-09 på Wayback Machine .
•   Bellman, Richard (1954), "The theory of dynamic programmering", Bulletin of the American Mathematical Society , 60 (6): 503–516, doi : 10.1090/S0002-9904-1954-09848-8 , MR 0067459 . Innehåller en omfattande bibliografi över litteraturen i området fram till år 1954.
•   Bellman, Richard (1957), Dynamisk programmering , Princeton University Press . Dover pocketutgåva (2003), ISBN 0-486-42809-5 .
•   Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, ISBN 978-0-262-03293-3 . Särskilt s. 323–69.
•   Dreyfus, Stuart E.; Law, Averill M. (1977), The Art and Theory of Dynamic Programming , Academic Press, ISBN 978-0-12-221860-6 .
• Giegerich, R.; Meyer, C.; Steffen, P. (2004), "A Discipline of Dynamic Programming over Sequence Data" (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 , arkiverad från originalet 2010-06-19 .
• Sritharan, SS (1991). "Dynamisk programmering av Navier-Stokes ekvationer". System och styrbrev . 16 (4): 299–307. doi : 10.1016/0167-6911(91)90020-f .
•   Stokey, Nancy ; Lucas, Robert E .; Prescott, Edward (1989), Rekursiva metoder i ekonomisk dynamik , Harvard Univ. Press, ISBN 978-0-674-75096-8 .

externa länkar

• En handledning om dynamisk programmering
• MIT-kurs om algoritmer - Innehåller 4 videoföreläsningar om DP, föreläsningar 19-22
• Tillämpad matematisk programmering av Bradley, Hax och Magnanti, kapitel 11
• Fler DP-anteckningar
• King, Ian, 2002 (1987), " A Simple Introduction to Dynamic Programming in Macroeconomic Models. " En introduktion till dynamisk programmering som ett viktigt verktyg i ekonomisk teori.
• Dynamisk programmering: från nybörjare till avancerade En TopCoder.com-artikel av Dumitru om dynamisk programmering
• Algebraisk dynamisk programmering – ett formaliserat ramverk för dynamisk programmering, inklusive en nybörjarkurs till DP, Bielefelds universitet
• Dreyfus, Stuart, " Richard Bellman om födelsen av dynamisk programmering. "
• Handledning för dynamisk programmering
• En mild introduktion till dynamisk programmering och Viterbi-algoritmen
• Tabellerad Prolog BProlog , XSB , SWI-Prolog
• IFORS interaktiva dynamiska programmeringsmoduler online inklusive kortaste vägen, resande säljare, ryggsäck, falskt mynt, äggsläpp, bro och ficklampa, ersättning, kedjade matrisprodukter och problem med kritisk väg.