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 rendu de monnaie suffit à montrer l'une et l'autre, et il sert de fil au chapitre entier.

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. Le critère local tient dans l'ordre du tableau : les pièces y sont rangées de la plus grosse à la plus petite, et c'est cet ordre qui fait essayer d'abord la plus grosse. 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é se démontre pour ce jeu précis, et elle n'a rien d'automatique : l'exercice 1 présente un jeu aux valeurs bien espacées où elle est fausse. Elle explique pourtant 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. Il suffit de changer le jeu de pièces pour que la propriété disparaisse. 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.

Que 2 soit le minimum reste à établir. La figure suivante l'établit par énumération : elle parcourt toutes les combinaisons de pièces de 4, de 3 et de 1, a, b et c comptant les pièces de chaque sorte, et retient la plus courte de celles dont le total fait 6. Chaque boucle s'arrête au plus grand nombre de pièces qui tient dans 6 : une pièce de 4, puisque deux font déjà 8, deux pièces de 3, puisque trois font 9, et six pièces de 1. La valeur 99 donnée au départ à meilleur signifie « aucune solution encore trouvée » : plus grande que tout nombre de pièces possible ici, elle est remplacée par la première combinaison qui convient.

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. Sur le rendu de monnaie, l'idée se dit simplement. Pour payer 6, la dernière pièce posée est une pièce de 1, de 3 ou de 4 : il suffit d'essayer les trois, de payer au mieux ce qui reste, 5, 3 ou 2, et de garder la meilleure des trois possibilités. Or payer au mieux ce qui reste est le même problème sur une somme plus petite : la fonction s'appelle elle-même, comme au chapitre sur la récursivité, et la descente s'arrête sur la somme 0, qui se paie sans aucune pièce. La figure affiche chaque appel au moment où il se produit.

La réponse est juste, deux pièces, et cette fois sans pari. La valeur 99 donnée au départ à meilleur joue le même rôle que dans l'énumération : elle signifie « aucune solution encore trouvée ». Mais la sortie compte vingt-quatre appels pour une somme de 6, et la répétition saute aux yeux : Rendre(3) est calculé deux fois, Rendre(2) quatre fois, Rendre(1) six fois et Rendre(0) neuf fois. Aucune de ces réponses ne change d'un calcul à l'autre, et pourtant chacune est recalculée de zéro.

Le compteur de pas mesure la croissance. La figure suivante retire la ligne qui annonce chaque appel et lit la somme à rendre dans son champ de saisie : la somme 6 y demande 274 pas, la somme 7 en demande 443, et la somme 8, proposée à l'ouverture, ne se déroule pas jusqu'au bout.

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. Une somme de 8, que deux pièces de 4 suffisent à payer, épuise déjà le budget. Chaque unité de plus multiplie le travail par un facteur à peu près fixe, voisin de 1,6, parce que chaque appel en relance jusqu'à trois autres.

Le mur est là bien avant les grands nombres. Un coût qui se multiplie par un facteur fixe à chaque unité de plus devient inatteignable en quelques dizaines d'unités, quelle que soit la machine. La suite de Fibonacci, où chaque terme est la somme des deux précédents, en donne l'exemple le plus connu : écrite de la même façon récursive, elle fait quinze appels pour obtenir son sixième terme, 8, et calcule cinq fois le deuxième. La comparaison des classes de coût et la notation qui les décrit sont traitées dans le chapitre sur la complexité.

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. Deux remèdes existent.

La mémoïsation garde la récursion telle quelle et lui adjoint un carnet partagé par tous les appels : avant de calculer, chaque appel regarde si la réponse y figure déjà, et l'y inscrit sinon. Ce carnet commun n'existe pas dans le pseudo-code du cours, où une fonction ne communique que par ses paramètres, reçus en copie, et par sa valeur de retour : ce qu'un appel noterait dans sa copie serait perdu à son retour. Python, qui partage au contraire une liste ou un dictionnaire passé en paramètre, permet de l'écrire en quelques lignes.

Le second remède obtient le même gain sans récursion. Il part des plus petites sommes et monte, en rangeant chaque réponse dans un tableau où les suivantes viennent la relire : quand la somme 6 a besoin de la meilleure façon de payer 3, celle-ci est déjà écrite, et il suffit de la lire. Cette façon de faire porte un nom, la programmation dynamique, et la section suivante la construit sur le rendu de monnaie.

Remplir le tableau de proche en proche

Le second remède n'est pas un pis-aller : c'est le principe même de la programmation dynamique.

L'idée est celle de la fonction Rendre, débarrassée de ses répétitions. Pour rendre la somme s au mieux, on essaie chaque pièce p comme dernière pièce, on lui ajoute la meilleure façon de rendre le reste s - p, et on garde la plus petite des possibilités. Le reste doit lui-même être payé au mieux : une solution qui paierait mal son reste s'améliorerait en remplaçant ce reste par une meilleure façon de le payer. Le tableau m range ces réponses, m[s] étant le nombre minimal de pièces pour la somme s, et chaque case se calcule à partir de cases plus petites, déjà remplies.

Deux détails du pseudo-code tiennent aux conventions du cours. La case m[0], qui vaudrait 0, n'existe pas, puisque les tableaux commencent à 1 : le cas où la pièce vaut exactement la somme, p = s, est donc traité à part, et il donne une seule pièce, le minimum possible. Et chaque case démarre à 99, qui signifie, comme dans Rendre, « aucune solution encore trouvée ». La figure affiche la proposition de chaque pièce avant de conclure sur la case, et son champ de saisie règle la somme à rendre.

Le tableau se remplit de gauche à droite, en 129 pas. Chaque ligne ci-dessous reprend un tour de la boucle extérieure : les trois colonnes du milieu sont les propositions des trois pièces, et la dernière retient la plus petite.

La case 6 vaut 2, la réponse de l'énumération exhaustive, obtenue cette fois en ne calculant chaque somme qu'une fois. Sa ligne résume le chapitre : la pièce de 4, celle que le glouton prend d'emblée, propose 3 ; la pièce de 3 propose 2, et c'est elle qui l'emporte. L'ordre des pièces dans le tableau pieces n'a d'ailleurs plus d'importance, puisque toutes sont essayées à chaque case.

Le champ de saisie permet de reprendre la comparaison avec la version récursive. Pour la somme 7, la plus grande que celle-ci déroule jusqu'au bout, elle demandait 443 pas ; la table en demande 153, en affichant pourtant chacune de ses propositions. Pour la somme 12, que la version récursive ne déroule pas, la table conclut à 3 pièces en 272 pas. L'écart n'est pas un gain de constante : la version récursive coûte un facteur à peu près fixe de plus par unité de somme, la table coûte un tour de boucle de plus par unité. La somme 10 montre au passage un second échec du glouton : la table y trouve 3 pièces, 4 + 3 + 3, là où le glouton en rend 4.

Ce que le tableau change par rapport au glouton. Le glouton prend une décision et l'oublie. Le tableau garde, pour chaque somme intermédiaire, la meilleure façon connue de la payer, et compare toutes les dernières pièces possibles avant de conclure. Il ne parie pas : il choisit après avoir vu.
Le prix de ce choix informé est le tableau lui-même, une case par sous-problème, là où le glouton ne retenait rien.

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 figure suivante reprend la même boucle, sans ses affichages, avec un tableau dernier en plus.

La sortie annonce deux pièces, puis les nomme : une pièce de 3, puis une autre. Le tableau dernier vaut [1, 1, 3, 4, 1, 3] : la pièce notée pour 6 est un 3, la remontée passe à la somme 3, dont la pièce notée est encore un 3, et arrive à 0. Avec 10, elle nomme 3, 3 puis 4, la solution que le glouton manquait. La boucle de remontée a son variant, s, qui décroît strictement puisque dernier[s] vaut au moins 1, et qui ne descend jamais sous 0, puisque la pièce notée pour une somme ne la dépasse jamais : elle s'arrête donc toujours.

Mettre en pratique

Le glouton se compte pièce par pièce, et la table case par case, chaque case ne lisant que des cases déjà remplies. Les deux calculs se font à la main.

Les deux dernières réponses mesurent l'écart que le compteur de pas montrait : la récursion multiplie ses appels à chaque unité de somme en plus, la table n'ajoute que trois propositions par case.