Gloutons et programmation dynamique

Rendre la monnaie avec le moins de pièces possible, remplir un sac sans dépasser son poids, choisir les réunions qui tiennent dans une journée : ces problèmes ont en commun de demander non pas une solution, mais la meilleure. Le nombre de solutions candidates y grandit vite, et les examiner toutes devient impossible bien avant que les données ne soient grosses.

Deux familles de méthodes répondent à cette difficulté sans tout énumérer. La première décide vite et ne revient jamais en arrière. La seconde accepte de calculer davantage, mais refuse de calculer deux fois la même chose.

Le glouton : prendre le mieux tout de suite

Le rendu de monnaie est l'exemple canonique. Il s'agit de payer une somme avec le moins de pièces possible, en piochant dans un jeu de valeurs disponibles. Le critère local est immédiat : prendre à chaque fois la plus grosse pièce qui ne dépasse pas ce qu'il reste à rendre.

Le déroulement tient en trente-sept pas et produit la suite 50, 10, 5, 2, 1, soit cinq pièces pour 68 centimes. Aucune combinaison ne fait mieux, et ce n'est pas un hasard : sur le système de pièces européen, le glouton donne toujours l'optimum. La propriété est démontrable, elle repose sur les rapports entre les valeurs successives du jeu de pièces, et elle explique pourquoi personne n'a jamais eu à réfléchir en rendant la monnaie.

Le même glouton, mis en échec

La phrase « le glouton donne l'optimum » portait sur un jeu de pièces précis. Change le jeu de pièces, et la propriété disparaît. Voici le même algorithme, mot pour mot, sur un système à trois valeurs : 4, 3 et 1.

Le glouton prend la pièce de 4, se retrouve avec 2 à rendre, ne peut plus utiliser ni le 4 ni le 3, et termine avec deux pièces de 1 : trois pièces au total. Or 6 s'écrit 3 + 3, soit deux pièces. Le glouton n'est pas optimal sur ce jeu de pièces, et il suffisait de la somme 6 pour le montrer.

Affirmer que 2 est le minimum serait encore une affirmation. La figure suivante l'établit par énumération : elle parcourt toutes les combinaisons possibles de pièces de 4, de 3 et de 1 dont le total fait 6, et retient la plus courte.

La trace affiche successivement 6 pièces, puis 4, puis 2, et conclut sur optimum : 2 pièces. Le contre-exemple est établi, pas supposé.

Recalculer cent fois la même chose

Quand le glouton échoue, il faut envisager plusieurs choix à chaque étape au lieu d'un seul. La façon naturelle de le faire est récursive, et elle a un défaut spectaculaire que la suite de Fibonacci met à nu.

Chaque terme y est la somme des deux précédents. La définition récursive s'écrit d'elle-même, et la figure affiche chaque appel au moment où il se produit.

appel de Fib(6)

Pour obtenir le sixième terme, qui vaut 8, l'algorithme effectue quinze appels. La sortie les montre tous, et la répétition saute aux yeux : Fib(4) est calculé deux fois, Fib(3) trois fois, Fib(2) cinq fois. Aucune de ces valeurs ne change entre deux calculs, et pourtant chacune est recalculée de zéro.

Le nombre d'appels suit à peu près la valeur du terme cherché, c'est-à-dire qu'il est multiplié par environ 1,6 à chaque rang. Le compteur de pas le confirme sans ambiguïté : 135 pas au rang 9, 219 au rang 10, 355 au rang 11. Le rang 12 ne se déroule plus du tout.

Le moteur s'arrête au-delà de cinq cents pas et le signale. Le message qu'il affiche évoque une boucle dont rien ne fait avancer la condition de sortie, parce que c'est la cause habituelle ; ici la cause est autre, et plus inquiétante : l'algorithme se termine parfaitement, il demande simplement plus de pas que la page n'en déroule. Le rang 12 d'une suite dont le douzième terme vaut 144 suffit à épuiser le budget.

Retenir au lieu de recalculer

Le gaspillage a une cause unique : la même question est posée plusieurs fois, et la réponse n'est jamais conservée. La mémoïsation consiste précisément à conserver chaque résultat déjà obtenu, dans un tableau indexé par la question, et à le relire au lieu de le recalculer.

Le rang 11 est le plus grand qui se déroule entièrement dans la page, et c'est donc lui qui sert de point de comparaison. La version naïve y demande 355 pas.

La version qui retient range les termes déjà connus dans un tableau f, où f[k] contient le terme de rang k. Chaque case n'est remplie qu'une fois, et les cases suivantes la relisent au lieu de la recalculer.

Même rang, même résultat 89, et 24 pas au lieu de 355. Les deux nombres se relèvent sur le compteur des deux figures, et l'écart n'est pas un gain de constante : la version naïve coûte un facteur fixe de plus par rang supplémentaire, la version qui retient coûte un tour de boucle de plus par rang supplémentaire. Au rang 12, où la première ne se déroule plus, la seconde demande 26 pas.

Remplir le tableau de proche en proche

Renverser le sens de remplissage n'est pas un pis-aller : c'est le principe même de la programmation dynamique.

Sur Fibonacci, chaque case se déduisait de ses deux voisines de gauche, et l'ordre allait de soi. Le rendu de monnaie demande davantage, et c'est précisément ce que la programmation dynamique apporte de plus : une case y est le minimum sur plusieurs cases antérieures, une par pièce disponible.

L'idée tient en une phrase. Pour rendre la somme s avec le moins de pièces possible, il faut bien qu'une dernière pièce p ait été posée ; une fois qu'elle l'est, il reste à rendre s - p de façon optimale. La meilleure solution pour s vaut donc, pour la meilleure pièce p, un de plus que la meilleure solution pour s - p.

Le tableau se remplit de gauche à droite, et la trace donne les six cases dans l'ordre :

La case 6 vaut 2, ce qui était la réponse donnée par l'énumération exhaustive, obtenue cette fois sans énumérer quoi que ce soit. Et le détail du calcul de cette case mérite d'être lu dans la trace : la pièce de 1 propose m[5] + 1, soit 3 ; la pièce de 3 propose m[3] + 1, soit 2 ; la pièce de 4 propose m[2] + 1, soit 3. Le minimum des trois l'emporte, et c'est celui que le glouton avait écarté d'emblée en prenant la plus grosse pièce.

Il reste à savoir quelles pièces composent la solution, et pas seulement combien. Il suffit de noter, en même temps que le minimum, la pièce qui l'a produit, puis de remonter.

La sortie annonce deux pièces, puis les nomme : une pièce de 3, puis une autre. La boucle de remontée a son variant, s, qui décroît strictement puisque dernier[s] vaut au moins 1 : elle s'arrête donc toujours.

Vérification

Exercices type

Exercice 1 : trouver une somme que le glouton paie mal sur le jeu de pièces 1, 5 et 12.

Exercice 2 : donner l'invariant de la boucle qui remplit le tableau du rendu de monnaie.

Exercice 3 : dire lequel des deux algorithmes, glouton ou tableau, convient pour rendre la monnaie dans une caisse de supermarché français.

La méthode

1. Écrire d'abord le glouton, parce qu'il est court et qu'il donne une réponse immédiatement exploitable comme point de comparaison.
2. Chercher le contre-exemple avant de faire confiance. Essayer les sommes juste au-dessus de chaque valeur du jeu, là où un choix local engage un reste difficile à payer.
3. Le faire vérifier plutôt que l'affirmer. Une énumération exhaustive sur de petites données établit l'optimum réel et tranche la question.
4. Repérer les sous-problèmes qui reviennent. Si la formulation récursive repose deux fois sur la même question, le coût se multiplie à chaque niveau et le calcul devient inatteignable en quelques rangs.
5. Ranger chaque résultat dans un tableau indexé par la question, et remplir ce tableau du plus petit cas vers le plus grand pour qu'une case ne soit jamais lue avant d'être écrite.
6. Noter la décision en même temps que la valeur quand la solution elle-même est demandée, et remonter le tableau à la fin pour la reconstituer.

Synthèse

• Un glouton choisit le meilleur immédiat et ne revient jamais dessus. Il est optimal sur le rendu de monnaie en euros, et il ne l'est pas sur le jeu de pièces 4, 3 et 1, où la somme 6 lui coûte trois pièces au lieu de deux.
• Un contre-exemple s'exhibe et se vérifie ; l'énumération exhaustive a donné l'optimum de 2 pièces que le glouton manquait.
• Une récursion qui repose plusieurs fois sur la même question voit son coût se multiplier à chaque rang : 135 pas au rang 9, 219 au rang 10, 355 au rang 11, et plus rien au rang 12.
• Retenir chaque résultat au lieu de le recalculer ramène le rang 11 de 355 pas à 24, et l'écart grandit avec le rang.
• La programmation dynamique remplit un tableau du plus petit sous-problème au plus grand, chaque case se déduisant de cases déjà écrites. Sur le rendu de monnaie, chaque case est un minimum sur autant de cases antérieures qu'il y a de pièces.
• Un tableau des décisions, rempli en parallèle, permet de reconstituer la solution et pas seulement son coût.

Ce chapitre referme le parcours d'algorithmique, commencé sur la lecture d'un pseudo-code et achevé sur des algorithmes d'optimisation dont la correction se démontre. Deux prolongements attendent ailleurs sur le site. L'algorithme de Dijkstra, présenté dans le chapitre sur les plus courts chemins, est un glouton dont l'optimalité, elle, se démontre : c'est l'occasion de voir à quoi ressemble la preuve qui manquait au rendu de monnaie. Et le chapitre sur la complexité donne le vocabulaire qui permet de nommer les écarts relevés ici au compteur de pas, et de les comparer sans dérouler quoi que ce soit.