Principe fondamental de la programmation dynamique
Fondamental : Principe de Bellmann
La programmation dynamique est basée sur le principe de Bellmann [Wolsey 1998] :
"Si C est un point qui appartient au chemin optimal entre A et B, alors la portion de ce même chemin allant de B à C est le sous-chemin optimal entre B et C"
Cette approche consiste donc à construire les sous-chemins optimaux pour ensuite construire par récurrence le chemin optimal pour le problème entier. Dans la figure suivante, le chemin vert entre A et B est optimal. Ce chemin passe par le point C. Le sous-chemin vert [C, B] est donc optimal et le sous-chemin gris [C, B] ne peut exister car il est plus court que le sous-chemin vert. Autrement dit, si le sous-chemin gris existe alors la solution optimale devient la séquence formée du sous-chemin vert [A, C] et du sous-chemin gris [C, B] au lieu du chemin vert [A, B].
La programmation dynamique s'appuie sur le principe de Bellman et consiste à prolonger le problème étudié en un problème plus général dont les paramètres sont entiers. Il faut généralement déterminer des relations de récurrence permettant de résoudre le problème d'un ordre donné en fonction de ses solutions pour les ordres inférieurs.
