Dynamisk programmering

Dynamisk programmering (DP; eng. dynamic programming, DP) — är en metod för att lösa komplexa optimeringsproblem, baserad på att dela upp ursprungsproblemet i en sekvens av enklare delproblem. Metoden tillämpas på flerstegsprocesser för beslutsfattande, där den optimala lösningen för hela problemet kan byggas upp av optimala lösningar för dess delproblem.

Termen introducerades av den amerikanske matematikern Richard Bellman på 1950-talet. I detta sammanhang används ordet "programmering" i betydelsen "planering" eller "utformning av en optimal handlingsplan", och inte skrivande av datorkod.

Grundläggande egenskaper och satser

Tillämpligheten av dynamisk programmering på ett problem avgörs av att det uppvisar två fundamentala egenskaper.

Bellmans optimalitetsprincip

Centralt för metoden är Bellmans optimalitetsprincip (eng. Bellman's principle of optimality). Den lyder: oavsett vad det ursprungliga tillståndet och det ursprungliga beslutet är, måste efterföljande beslut utgöra en optimal strategi med avseende på det tillstånd som uppstår till följd av det första beslutet.

Med andra ord är varje del av en optimal bana i sig själv optimal. Denna egenskap gör det möjligt att dela upp det övergripande problemet i en sekvens av enklare delproblem och lösa dem rekursivt.

Överlappande delproblem

Ett problem uppvisar egenskapen överlappande delproblem (eng. overlapping subproblems) om samma delproblem uppstår upprepade gånger vid rekursiv lösning. DP gör det möjligt att undvika upprepade beräkningar genom att spara lösningarna på redan beräknade delproblem (denna teknik kallas memoisering eller tabulering), vilket avsevärt ökar effektiviteten jämfört med naiv rekursiv sökning.

Bellmans ekvation

Av optimalitetsprincipen följer metodens grundläggande rekurrensrelation — Bellmans ekvation. Den kopplar samman "värdet" (den optimala vinsten eller kostnaden) för det aktuella tillståndet med värdena för efterföljande tillstånd. I allmän form för en deterministisk flerstegsprocess med en additiv målfunktion har den följande utseende:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

där:

• $k$ — stegnumret (från $m$ till 1);
• $x$ — systemets tillstånd vid steg $k-1$;
• $y$ — det styrbara beslut som fattas vid steg $k$;
• ${\phi }_k(x,y)$ — vinsten (eller kostnaden) vid steg k;
• $f_k(x,y)$ — funktionen som definierar systemets nya tillstånd;
• $V_k(s)$ — det optimala värdet av målfunktionen för delproblemet som börjar vid steg $k$ i tillstånd $s$.

Ekvationen löses sekventiellt, i regel "bakifrån", med rörelse från det sista steget till det första.

Tillämpningsexempel

• Kortaste vägen i en graf: Detta problem uppvisar egenskapen optimal understruktur, eftersom varje delsträcka av den kortaste vägen i sig är kortast. Bellman-Fords algoritm och Floyd-Warshalls algoritm är klassiska exempel på tillämpning av DP för att lösa detta problem.
• Ryggsäcksproblemet: Problemet handlar om att optimalt fylla en ryggsäck med begränsad kapacitet med föremål av olika värde och vikt. DP gör det möjligt att lösa detta problem genom att behandla föremålen sekventiellt och vid varje steg beräkna det maximala värdet för alla möjliga värden på återstående kapacitet.
• Resursfördelningsproblemet: Fördelning av en begränsad resurs (till exempel investeringar) mellan flera projekt för att maximera den totala nyttan.

Begränsningar

Metodens huvudsakliga begränsning är dimensionalitetens förbannelse (eng. curse of dimensionality) — en term som Bellman införde för att beteckna den exponentiella ökningen av antalet tillstånd och, som en följd, beräkningskomplexiteten, vid ett ökat antal variabler som beskriver systemets tillstånd. Detta begränsar den praktiska tillämpningen av exakt DP för problem med mycket hög dimensionalitet.

Relaterade begrepp

• Operationsanalys
• Teorin om optimal styrning
• Markovsk beslutsprocess (stokastisk generalisering)
• Hamilton–Jacobi–Bellmans ekvation (analogin för kontinuerlig tid)

Referenser

</references>