Gloutons et programmation dynamique

Choisir sans regret : les algorithmes gloutons

Beaucoup de problèmes consistent à construire une solution par une suite de choix : quelle pièce rendre, quelle réservation accepter, quel objet glisser dans le sac. Un algorithme glouton fait à chaque étape le choix qui semble le meilleur sur le moment, et ne le remet jamais en cause. Dans l’arbre de tous les choix possibles, il ne suit qu’une seule branche : c’est ce qui le rend si rapide, et si simple à écrire. Toute la difficulté est ailleurs : savoir si cette branche mène bien à la meilleure solution.

Rendre la monnaie

Pour rendre une somme avec le moins de pièces possible, la caissière prend toujours la plus grosse pièce qui ne dépasse pas ce qui reste à rendre. Avec les euros, ça marche à tous les coups. Avec les pièces britanniques d’avant 1971 (1, 3, 6, 12, 24 et 30 pence), ça échoue : pour rendre 48 pence, le glouton donne $30+12+6$, trois pièces, alors que deux florins, $24+24$, suffisaient.

Pour connaître l’optimum, il faut une autre idée, que la bande du bas met en œuvre : le meilleur rendu d’un montant $m$ commence par une pièce $p$, suivie du meilleur rendu de $m-p$. Si l’on connaît déjà les meilleurs rendus de tous les montants plus petits, il suffit d’essayer chaque pièce. C’est de la programmation dynamique, l’objet de la seconde partie de cette page.

Quand peut-on faire confiance à un glouton ?

Il faut le démontrer, et l’argument classique est un échange. On part d’une solution optimale quelconque, et l’on montre qu’on peut la modifier, sans la dégrader, pour qu’elle commence par le choix du glouton. On recommence sur la suite, et, de proche en proche, la solution du glouton se révèle elle-même optimale. Pour les euros, l’échange marche : deux pièces de 1 centime se remplacent par une pièce de 2, trois pièces de 2 par une de 5 et une de 1, et ainsi de suite. Pour les anciens pence, il échoue sur 48. Les systèmes monétaires modernes sont conçus pour que le glouton de la caissière soit optimal.

Réserver une salle

Une salle reçoit des demandes de réservation pour la journée, chacune avec une heure de début et une heure de fin. On veut en satisfaire le plus grand nombre possible, sans que deux réservations se chevauchent. Plusieurs critères gloutons viennent à l’esprit : accepter d’abord les demandes qui commencent le plus tôt, ou les plus courtes, ou celles qui gênent le moins de monde. Un seul est toujours optimal.

Le bon critère est de prendre d’abord la demande qui se termine le plus tôt : c’est elle qui laisse la salle libre le plus tôt pour la suite. L’argument d’échange le confirme. Dans n’importe quelle solution optimale, on peut remplacer la première réservation par celle qui finit le plus tôt de toutes : elle se termine avant, donc ne gêne aucune des suivantes, et le nombre de réservations ne change pas. Les autres critères ont chacun leur cas piège, que le bouton du même nom construit.

Compresser : le code de Huffman

Un texte est stocké lettre par lettre, et l’ASCII consacre 8 bits à chaque caractère. Pourtant, toutes les lettres ne se valent pas : en français, le « e » est bien plus fréquent que le « w ». En donnant des codes courts aux caractères fréquents et des codes longs aux caractères rares, on raccourcit le texte. Encore faut-il pouvoir le relire sans ambiguïté : aucun code ne doit être le début d’un autre. C’est le cas si les codes sont les chemins d’un arbre binaire, de la racine aux feuilles, où chaque feuille porte un caractère.

En 1951, au MIT, Robert Fano laisse à ses étudiants le choix entre un examen final et un devoir : trouver le meilleur de ces codes. David Huffman cherche pendant des mois, s’apprête à renoncer et à réviser pour l’examen, quand l’idée lui vient. Au lieu de construire l’arbre depuis la racine, comme le faisait son professeur, il le construit depuis les feuilles, en fusionnant toujours les deux arbres les plus légers. Ce glouton est optimal, et il a battu la méthode de Fano.

Le codage de Huffman est partout : dans les fichiers ZIP, dans les images JPEG, dans la musique MP3, où il intervient à la dernière étape de la compression.

Les gloutons des graphes

Trois des grands algorithmes de la page Graphes sont des gloutons, et tous trois sont optimaux. Dijkstra valide à chaque étape le sommet le plus proche du départ parmi ceux qui attendent. Prim ajoute à son arbre l’arête la plus courte qui en sort. Kruskal examine les arêtes de la plus courte à la plus longue et garde toutes celles qui ne ferment pas de cycle. Chaque fois, un argument d’échange garantit que le choix du moment ne sera jamais regretté.

Quand le glouton se trompe : le sac à dos

Un cambrioleur dispose d’un sac qui supporte 10 kilos, et hésite entre six objets : une guitare de 6 kilos d’une valeur de 30, un appareil photo et un télescope de 5 kilos valant 24 chacun, une peluche de 3 kilos valant 13, des livres de 2 kilos valant 7, et un réveil d’un kilo valant 1. Le réflexe glouton est de prendre les objets dans l’ordre de leur valeur au kilo : la guitare (5 par kilo), puis la peluche, puis le réveil, pour une valeur de 44. Mais l’appareil photo et le télescope, ensemble, valent 48.

Le premier choix du glouton, la guitare, semblait le meilleur ; il interdit pourtant la meilleure combinaison. Aucun critère glouton ne résout ce problème. Faut-il alors essayer les $2^n$ sous-ensembles d’objets ?

Quand les sous-problèmes se répètent : la programmation dynamique

La suite de Fibonacci, $F_n=F_{n-1}+F_{n-2}$, appelle une fonction récursive immédiate. Mais son arbre des appels explose : pour calculer $F_5$, on calcule deux fois $F_3$, trois fois $F_2$, cinq fois $F_1$. Ces sous-problèmes ne sont pas indépendants, ce sont les mêmes : l’arbre n’est qu’un petit graphe déguisé.

F5F4F3F2F1F0F1F2F1F0F3F2F1F0F1l'arbre des appels : 15 appelsF0F1F2F3F4F5replié : 6 sous-problèmes

À gauche, l'arbre des appels récursifs de $F_5$ ; à droite, le même calcul une fois les doublons fusionnés.

L’idée de la programmation dynamique est de replier l’arbre : résoudre chaque sous-problème une seule fois, ranger la réponse, et la réutiliser. On peut le faire de haut en bas, en mémorisant les résultats de la fonction récursive (c’est la mémoïsation), ou de bas en haut, en remplissant un tableau des plus petits sous-problèmes vers les plus grands, comme la bande du rendu de monnaie. Beaucoup de problèmes qui semblent exiger d’explorer un nombre exponentiel de possibilités ne comportent en réalité qu’un petit nombre de sous-problèmes distincts, rencontrés un très grand nombre de fois.

Un nom choisi pour ne rien dire

Richard Bellman, qui invente la méthode au début des années 1950 à la RAND Corporation, a raconté d’où vient son nom. Le secrétaire à la Défense de l’époque, Charles Wilson, dont dépendait le financement de la RAND, avait « une peur et une haine pathologiques du mot recherche ». Bellman cherche donc un nom qui ne sente pas les mathématiques. Programming, au sens de planifier, convient. Et dynamic a cet avantage qu’il est impossible de l’employer dans un sens péjoratif : « c’était quelque chose à quoi même un membre du Congrès ne pourrait rien objecter ».

Fibonacci, quatre fois

Fibonacci offre même une petite échelle de raffinement. La version récursive naïve recalcule sans cesse les mêmes termes : son coût croît comme $\varphi^n$, exponentiellement. En mémorisant chaque terme, on descend à $\mathcal{O}(n)$ en temps et en mémoire. En ne gardant que les deux derniers termes, la mémoire tombe à $\mathcal{O}(1)$. Enfin, les formules de doublement, $F_{2k}=F_k(2F_{k+1}-F_k)$ et $F_{2k+1}=F_k^2+F_{k+1}^2$, permettent de sauter de $k$ à $2k$, comme l’exponentiation rapide : $\mathcal{O}(\log n)$ opérations.

La même idée, réduite à deux variables, fait la force de l’algorithme de Kadane : la meilleure tranche qui se termine en $i$ se déduit de celle qui se termine en $i-1$.

Le sac à dos

Revenons au cambrioleur. Essayer tous les sous-ensembles d’objets revient à parcourir un arbre binaire : à chaque objet, on le prend ou on le laisse. Avec $n$ objets, l’arbre a $2^n$ feuilles : un millier pour dix objets, un milliard pour trente.

Arbre des choix du sac à dos : à chaque objet, on le prend ou on le laisse

Mais beaucoup de branches aboutissent à la même situation : les mêmes objets restent à examiner, avec la même place libre. Notons $T[i][c]$ la meilleure valeur qu’on peut emporter avec les $i$ premiers objets dans un sac de capacité $c$. Pour le $i$-ème objet, de poids $p$ et de valeur $v$, il n’y a que deux possibilités : le laisser, et l’on obtient $T[i-1][c]$, ou le prendre, s’il tient, et l’on obtient $v+T[i-1][c-p]$. D’où la relation $$T[i][c]=\max\big(T[i-1][c],\ v+T[i-1][c-p]\big),$$ qui remplit une table ligne par ligne.

La table compte $(n+1)(C+1)$ cases, chacune calculée en temps constant : le coût est proportionnel à $n\times C$, au lieu de $2^n$. Attention pourtant : le sac à dos est un problème NP-complet, et la programmation dynamique ne contredit pas la conjecture P ≠ NP. Le coût dépend de la valeur de la capacité $C$, et non de la longueur de son écriture : avec une capacité d’un milliard de grammes, la table devient gigantesque. On parle d’algorithme pseudo-polynomial.

La distance d’édition

Combien faut-il d’opérations élémentaires (insérer une lettre, en supprimer une, en remplacer une) pour passer d’un mot à un autre ? Cette distance d’édition, introduite par Vladimir Levenshtein en 1965, sert aux correcteurs orthographiques, qui proposent les mots du dictionnaire les plus proches d’une faute de frappe, à la comparaison de séquences d’ADN, ou encore à l’outil diff, qui montre ce qui a changé d’une version d’un fichier à la suivante.

Le raisonnement est le même : pour transformer les $i$ premières lettres du premier mot en les $j$ premières du second, la dernière opération est soit la suppression de la $i$-ème lettre, soit l’insertion de la $j$-ème, soit le remplacement de l’une par l’autre (gratuit si ce sont les mêmes). La meilleure des trois se lit dans des cases déjà remplies.

Le voyageur de commerce : Held-Karp

Le problème du voyageur de commerce, rencontré à propos de P = NP, demande le plus court circuit passant une fois par chaque ville. On ne lui connaît pas d’algorithme polynomial, et essayer tous les circuits coûte $(n-1)!/2$ évaluations : plus de $10^{16}$ pour vingt villes. La programmation dynamique fait beaucoup mieux. Notons $C(S,i)$ la longueur du plus court chemin qui part de la ville $0$, visite exactement les villes de l’ensemble $S$ et termine en $i$ ; la dernière étape vient d’une ville $j$ de $S$, d’où $$C(S,i)=\min_{j\in S,\ j\neq i}\big(C(S\setminus\{i\},j)+d(j,i)\big).$$ Il y a $2^n$ ensembles $S$ et $n$ villes d’arrivée, et chaque case demande un minimum sur $n$ villes : un coût de l’ordre de $n^2 2^n$, soit environ quatre cents millions d’opérations pour vingt villes. C’est encore exponentiel, mais c’est, depuis 1962, le meilleur algorithme exact connu. Michael Held et Richard Karp le publient cette année-là, en même temps que Bellman.

Ci-dessous, Held-Karp à l’œuvre sur une carte de France, au départ de Paris : chaque étape calcule un état $C(S,i)$, le plus court chemin qui visite les villes de $S$ et arrive en $i$, en prolongeant d’une ville des chemins déjà calculés. On peut le comparer à la force brute, qui mesure un à un tous les circuits, et ajouter ou retirer des villes d’un clic pour voir les deux nombres d’étapes s’écarter.

Distances à vol d'oiseau. Contour de la France : Admin Express (IGN), Licence ouverte, via le dépôt france-geojson.

Une branche, toutes les branches

Les deux stratégies répondent à la même question, posée face à l’arbre de tous les choix possibles. Le glouton n’en suit qu’une branche : c’est rapide, mais il faut prouver que c’est la bonne, et il arrive qu’elle ne le soit pas. La programmation dynamique les explore toutes, mais chacune une seule fois, en reconnaissant les situations déjà rencontrées : c’est sûr, et souvent étonnamment rapide, à condition que ces situations ne soient pas trop nombreuses. Quand elles le sont, il reste à explorer l’arbre lui-même, en élaguant le plus tôt possible les branches sans avenir.