Rencontre #6: Programmation dynamique

Nous avons repris nos rencontres hebdomadaires en commençant par discuter des solutions aux problèmes de graphes. Nous avons ensuite débuté une nouvelle série de problèmes utilisant la programmation dynamique.

Problèmes

Nous nous intéressons à une série de problèmes portant pouvant se résoudre avec la technique dite de programmation dynamique. Voyez ci-dessous pour quelques explications à ce sujet. Les problèmes de la série sont en ordre croissant de difficulté.

1. “Radio Commercials” — Identifiez l’intervalle de temps pendant lequel la diffusion d’une publicité est susceptible de rapporter le plus gros bénéfice.
2. “Lattice Paths” — Calculez le nombre d’itinéraires possibles qui cheminent d’un bout à l’autre d’une grille \(20 \times 20\), en se déplaçant vers le bas ou vers la droite.
3. “Tri Tiling” — Combien y a-t-il de façons différentes de remplir un rectangle de taille \(3 \times n\) avec des tuiles de taille \(2 \times 1\)?
4. “Narrow Art Gallery” — Calculez la meilleure façon de fermer \(k\) pièces d’un musée, de sorte que les visiteurs puissent toujours y cheminer et de sorte que la valeur des pièces restant ouvertes soit maximale.
5. “Good Coalition” — Formez une coalition majoritaire de partis qui a le plus de chance de mener son mandat à son terme.

Explications et ressources

La programmation dynamique est une technique permettant de rechercher une solution optimale parmi un ensemble de possibilités, de façon plus efficace que par une simple exploration exhaustive (comme nous avons pu le faire pour le problème “Pebble Solitaire”, par exemple).

C’est une technique importante pour la programmation compétitive, et fort utile pour la conception d’algorithmes par ailleurs! La programmation dynamique demande un mode de pensée particulier, qui s’acquiert par la pratique.

(Note amusante: Le nom de “programmation dynamique” a été choisi seulement pour être un buzzword et n’a pas vraiment de sens, selon les propres mots de l’inventeur du terme, Richard Bellman.)

Pour qu’un problème se prête à de la programmation dynamique, une première condition est qu’il doit posséder une structure récursive. Cela signifie que chaque objet du problème est une combinaison de plus petits objets similaires, par exemple:

• un arbre binaire est formé de deux sous-arbres et d’une racine;
• une séquence est formée de deux moitiés concaténées ensemble;
• un ensemble de \(n\) éléments est formé d’un ensemble de \(n-1\) éléments auquel on ajoute un nouvel élément.

Une deuxième condition est que toute solution optimale doit être formée en combinant des solutions optimales elles aussi. (Cette condition est appelée le principe d’optimalité de Bellman.) Par exemple, le plus court chemin pour se rendre d’un point A à un point B est la concaténation du plus court chemin pour se rendre du point A à un point intermédiaire I, puis du plus court chemin du point I au point B.

Avec ces deux conditions, si l’on connaît deux solutions optimales, alors on peut en former une nouvelle en combinant ces deux. La programmation dynamique dite “bottom-up” consiste à démarrer des plus petites solutions puis à les combiner pour construire progressivement des solutions plus grandes, tout en gardant les solutions intermédiaires en mémoire. Il est également possible de procéder à rebours, en décomposant progressivement le problème initial en sous-problèmes: c’est la programmation dynamique dite “top-down”.

Pour en apprendre plus sur le sujet de la programmation dynamique, jetez un œil aux ressources suivantes:

• la section 1.6.5 du livre “Programmation efficace” donne une autre introduction au concept de programmation dynamique, ainsi que des astuces utiles pour l’implémenter en Python;
• la vidéo “5 Simple Steps for Solving Dynamic Programming Problems” de Reducible passe à travers deux exemples classiques en détail et tire les principes généraux utiles à la programmation dynamique;
• le chapitre 6 du livre “Guide to Competitive Programming” de A. Laaksonen entre dans plus de détails et détaille des exemples classiques de programmation dynamique, implémentés en C++;
• la section “Dynamic Programming” du site web cp-algorithms.com traite de sujets plus avancés en programmation dynamique.