Dynamisch programmeren

Dynamisch programmeren (DP; Engels: dynamic programming, DP) — is een methode voor het oplossen van complexe optimalisatieproblemen, gebaseerd op het opdelen van het oorspronkelijke probleem in een reeks eenvoudigere deelproblemen. De methode wordt toegepast op meerstapsprocessen voor besluitvorming, waarbij de optimale oplossing van het gehele probleem kan worden opgebouwd uit de optimale oplossingen van de deelproblemen.

De term werd geïntroduceerd door de Amerikaanse wiskundige Richard Bellman in de jaren 1950. In deze context wordt het woord "programmeren" gebruikt in de betekenis van "plannen" of "het opstellen van een optimaal actieplan", en niet het schrijven van computercode.

Belangrijkste eigenschappen en stellingen

De toepasbaarheid van dynamisch programmeren op een probleem wordt bepaald door de aanwezigheid van twee fundamentele eigenschappen.

Bellmans optimaliteitsprincipe

Het centrale concept van de methode is het optimaliteitsprincipe van Bellman (Engels: Bellman's principle of optimality). Dit stelt: ongeacht de begintoestand en de initiële beslissing, moeten de daaropvolgende beslissingen een optimale strategie vormen ten opzichte van de toestand die het resultaat is van de eerste beslissing.

Met andere woorden: elk deel van een optimaal traject is op zichzelf ook optimaal. Deze eigenschap maakt het mogelijk het algemene probleem op te splitsen in een reeks eenvoudigere deelproblemen en deze recursief op te lossen.

Overlappende deelproblemen

Een probleem heeft de eigenschap van overlappende deelproblemen (Engels: overlapping subproblems) als bij de recursieve oplossing ervan dezelfde deelproblemen meerdere keren opduiken. DP maakt het mogelijk herhaalde berekeningen te vermijden door de oplossingen van reeds tegengekomen deelproblemen op te slaan (deze techniek wordt memoïzatie of tabulatie genoemd), wat de efficiëntie aanzienlijk verhoogt ten opzichte van naïeve recursieve opsomming.

Bellmanvergelijking

Uit het optimaliteitsprincipe volgt de fundamentele recursiebetrekking van de methode — de Bellmanvergelijking. Deze koppelt de "waarde" (optimale winst of kosten) van de huidige toestand aan de waarden van de daaropvolgende toestanden. In algemene vorm ziet de vergelijking er voor een deterministisch meerstapsproces met een additieve doelfunctie als volgt uit:

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

waar:

• $k$ — het stapnummer (van $m$ tot 1);
• $x$ — de toestand van het systeem op stap $k-1$;
• $y$ — de bestuurbare beslissing die wordt genomen op stap $k$;
• ${\phi }_k(x,y)$ — de winst (of kosten) op de k-de stap;
• $f_k(x,y)$ — de functie die de nieuwe toestand van het systeem bepaalt;
• $V_k(s)$ — de optimale waarde van de doelfunctie voor het deelprobleem dat begint op stap $k$ in toestand $s$.

De vergelijking wordt stapsgewijs opgelost, doorgaans "van achteren af", door van de laatste stap naar de eerste stap te werken.

Toepassingsvoorbeelden

• Het kortste-padprobleem in een graaf: Dit probleem heeft de eigenschap van optimale deelstructuur, omdat elk segment van het kortste pad zelf ook het kortste pad is. De algoritmen van Bellman-Ford en Floyd-Warshall zijn klassieke voorbeelden van de toepassing van DP voor het oplossen van dit probleem.
• Het knapzakprobleem: Het probleem van de optimale vulling van een knapzak met beperkte capaciteit met voorwerpen van verschillende waarden en gewichten. DP maakt het mogelijk dit probleem op te lossen door de voorwerpen stapsgewijs te beschouwen en bij elke stap de maximale waarde te berekenen voor alle mogelijke waarden van de resterende capaciteit.
• Het middelenverdelingsprobleem: Het verdelen van een beperkte hoeveelheid middelen (bijvoorbeeld investeringen) over meerdere projecten om het totale effect te maximaliseren.

Beperkingen

De belangrijkste beperking van de methode is de vloek van de dimensionaliteit (Engels: curse of dimensionality) — een term die door Bellman werd geïntroduceerd om de exponentiële groei van het aantal toestanden en daarmee de rekenkundige complexiteit aan te duiden, naarmate het aantal variabelen dat de toestand van het systeem beschrijft toeneemt. Dit beperkt de praktische toepassing van exacte DP voor problemen met een zeer grote dimensionaliteit.

Verwante begrippen

• Operations research
• Theorie van optimale regeling
• Markov-beslissingsproces (stochastische veralgemening)
• Hamilton-Jacobi-Bellmanvergelijking (analogon voor continue tijd)

Noten

</references>