La programmation dynamique fut conçue par R. Bellman dans les années 1950. Son application est régie par deux principes :
on plonge le problème à résoudre dans une famille plus générale de problèmes dont le problème initial fait partie ;
ces problèmes sont liés par des relations de récurrence permettant de les résoudre de proche en proche.
L’algorithme de Bellman (voir la partie 9.3.3, page 196) pour déterminer un plus court chemin d’un sommet r d’un graphe sans circuit = (S, A) vers un autre sommet t de ce graphe procède de cette démarche. Le plongement consiste ici à étendre la recherche d’un plus court chemin de r à t à la recherche d’un plus court chemin de r à tout autre sommet de . Les relations de récurrence s’appuient sur le fait que, pour atteindre un sommet t, on doit passer par un prédécesseur s de t, ce que traduit l’affectation (en reprenant les notations de la partie 9.3.3, page 196) : ; le calcul se fait alors de proche en proche, selon une numérotation topologique (qui existe puisque est supposé sans circuit) pour être sûr que val(s) contient la valuation d’un plus court chemin de r à s quand on l’utilise pour déterminer val(t).
Nous allons donner d’autres illustrations de la programmation dynamique en l’appliquant à divers problèmes.
On reprend le problème -complet PART de la partition décrit dans la partie 13.2.3, page 300 : étant donnés n entiers positifs ai (1 ≤ i ≤ n) de somme paire, existe-t-il ?Notons S la demi-somme des n entier…