Programmation dynamique
Dans les grandes lignes
Principe
La programmation dynamique est un paradigme de programmation, c'est-à-dire une façon particulière d'appréhender un problème algorithmique donné. C'est une méthode utile pour obtenir une solution exacte à un problème algorithmique, là où une solution "classique" se trouve être trop complexe, c'est-à-dire trop peu efficace. On parle alors d'optimisation combinatoire.
Nous étudierons ici deux aspects de cette méthode : la combinaison de solutions ainsi que l'approche de résolution ascendante.
Combiner des solutions
La programmation dynamique est un paradigme de conception qu’il est possible de voir comme une amélioration ou une adaptation de la méthode diviser & régner. Nous faisons ici le parallèle avec cette méthode puisqu'elle est déjà bien connue de la pluspart des ingénieurs et techniciens dans notre domaine d'activité.
Méthode diviser & régner : de façon similaire à l'équation de Bellman, le principe de la méthode divide & conquer s'appuie sur la remarque suivante : la solution d’un problème dépend des solutions précédentes, obtenues des sous-problèmes.
Ainsi, la programmation dynamique, comme les méthodes diviser & régner, a pour essence la combinaison de solutions de problèmes de complexité moindre pour arriver à la résolution d'un problème d'envergure plus importante.
Cependant, une différence notoire entre ces deux paradigmes est le sens de résolution : en programmation dynamique, on parle de résolution ascendante.