Algorithmes gloutons

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• reconnaître un algorithme glouton à sa structure — une suite de décisions locales, irrévocables, prises selon un critère fixé — et nommer les deux propriétés qu'il exige de son problème: la propriété du choix glouton et la sous-structure optimale;
• écrire un argument d'échange complet, c'est-à-dire transformer une solution optimale quelconque en la solution gloutonne sans jamais dégrader sa valeur, et reconnaître les quatre étapes de cet argument dans une démonstration que vous lisez;
• démontrer l'optimalité de l'ordonnancement d'intervalles par date de fin la plus tôt, et réfuter par un contre-exemple explicite les deux critères plausibles que sont la durée la plus courte et la date de début la plus tôt;
• construire un arbre de Huffman à la main sur une instance donnée, en déduire les codes, compter les bits obtenus, et démontrer l'optimalité de l'arbre par échange;
• distinguer les problèmes où le glouton est optimal — sac à dos fractionnaire, rendu de monnaie sur le système suisse — de ceux où il ne l'est pas, sac à dos 0/1 et systèmes de pièces non canoniques, et dire ce qui change exactement;
• expliquer pourquoi «mon algorithme donne la bonne réponse sur mes trois exemples» n'est pas une démonstration, et ce qu'une recherche exhaustive de contre-exemples prouve — et ne prouve pas.

Ce qu'est un algorithme glouton

Décider une fois, ne jamais revenir

Les chapitres précédents résolvaient des problèmes où la structure de la solution était connue d'avance: trier un tableau, c'est produire une permutation; parcourir un graphe, c'est visiter tous les sommets. Les problèmes de ce chapitre et du suivant sont d'une autre nature. On vous donne un ensemble de possibilités, une contrainte, une mesure de valeur, et on vous demande de choisir un sous-ensemble: les réunions à placer dans une salle, les objets à emporter, les bits à donner à chaque caractère. Le nombre de sous-ensembles est exponentiel, l'énumération est hors de portée dès la cinquantaine d'éléments — le tableau du chapitre 1 le disait déjà: $2^n$ dépasse le milliard d'opérations à $n=30$ —, et il faut donc une méthode qui ne les regarde pas tous.

La méthode la plus simple qu'on puisse imaginer consiste à décider élément par élément, sans jamais revenir en arrière.

Deux mots de cette définition font tout le travail, et ce sont ceux dont dépendent à la fois l'efficacité et la difficulté du sujet.

Local. Le critère ne regarde pas l'avenir. Pour choisir la prochaine réunion, il ne simule pas ce que ce choix interdira; il applique une règle — «celle qui finit le plus tôt», «la plus courte», «celle qui commence en premier» — à ce qui reste disponible. C'est ce qui rend l'algorithme rapide: le schéma usuel est un tri, en $\Theta (n\log n)$ comparaisons, suivi d'un unique parcours linéaire. Comparez avec le chapitre 10, où la programmation dynamique remplit une table de $n\times W$ cases précisément parce qu'elle refuse de décider sans avoir comparé les deux branches.

Irrévocable. Une fois la réunion placée, elle y reste. C'est ce qui rend l'algorithme dangereux: si le critère se trompe une fois, rien dans la suite de l'exécution ne le rattrapera. Un glouton n'a pas de filet.

Le prix de cette simplicité est qu'un algorithme glouton n'est presque jamais optimal. Sur la plupart des problèmes de choix, aucun critère local ne peut l'être, et le chapitre 10 existe pour cette raison. Les quelques problèmes où un glouton est optimal sont donc précieux — et chacun d'eux mérite une démonstration, pas une conviction.

Les deux propriétés dont il a besoin

Que faut-il exactement au problème pour qu'un glouton l'emporte? Deux propriétés, et elles ne disent pas la même chose.

La sous-structure optimale est ce qui autorise la récurrence: elle dit que résoudre l'instance réduite optimalement suffit. Elle est partagée avec la programmation dynamique, qui l'exige tout autant — la différence entre les deux méthodes ne tient pas là. La propriété du choix glouton, elle, est spécifique: elle dit qu'on peut choisir sans comparer. C'est elle qui ramène un arbre de décision à un chemin.

L'argument d'échange

Une technique de démonstration mérite d'être enseignée pour elle-même quand elle sert cinq fois dans un chapitre. Celle-ci, appelée argument d'échange (exchange argument), est la démonstration standard d'optimalité d'un algorithme glouton, et vous l'avez déjà rencontrée au chapitre 8 sous une forme déguisée — la propriété de coupe qui justifie Kruskal est un argument d'échange sur les arêtes d'un arbre couvrant. Ce chapitre-ci ne fait que la nommer et la systématiser.

L'idée

On ne cherche pas à montrer que le glouton trouve *l'*optimum, ce qui n'aurait pas de sens puisqu'il y en a souvent plusieurs. On montre que toute solution optimale peut être transformée, pas à pas, en la solution gloutonne, chaque pas conservant la valeur. Si une telle transformation existe, la solution gloutonne est aussi bonne que celle dont on est parti; comme on est parti d'un optimum, elle est optimale.

L'image est celle d'un déménagement: on prend l'optimum de quelqu'un d'autre et on y substitue, un objet à la fois, les objets du glouton, en vérifiant à chaque substitution que rien n'est cassé ni perdu.

Deux variantes du même argument

La forme ci-dessus échange un élément. Une variante fréquente échange des positions dans l'arbre (c'est celle de Huffman: on échange deux feuilles), et une autre, dite greedy stays ahead, ne construit pas $S^{\prime }$ du tout: elle démontre par récurrence que le glouton est, après chaque étape, au moins aussi avancé que n'importe quelle solution — la $k$-ième tâche du glouton finit au plus tôt que la $k$-ième tâche de toute autre solution. Les deux formes sont interchangeables sur l'ordonnancement d'intervalles; nous écrirons l'échange, parce que c'est celle qui se transpose à Huffman et au sac à dos fractionnaire.

Ordonnancement d'intervalles

Le problème

Une salle de séminaire, une seule, et une pile de demandes de réservation. Chaque demande est un intervalle: elle commence à une date, se termine à une autre, et n'est pas négociable. Deux demandes qui se chevauchent ne peuvent pas être satisfaites toutes les deux. On veut en satisfaire le plus grand nombre possible — remarquez bien: le plus grand nombre, pas la plus grande durée occupée, ce qui serait un autre problème et n'aurait pas la même réponse.

Le choix de l'intervalle semi-ouvert n'est pas cosmétique: il dit qu'une tâche qui finit à 13h et une tâche qui commence à 13h sont compatibles, ce qui est la convention naturelle pour une salle et la convention des indices de ce cours — le chapitre 1 a fixé que les tranches $[i,j)$ sont semi-ouvertes, et les intervalles de temps suivent la même règle.

Voici l'instance sur laquelle tout ce chapitre travaillera. Ces huit tâches sont fictives; elles n'ont d'autre vertu que d'être toujours les mêmes, et les dates sont des entiers pour que vous puissiez refaire tous les calculs de tête.

Le critère qui marche

L'algorithme tient en dix lignes. Écrivons-le avant de le démontrer, parce qu'il faut savoir exactement ce qu'on démontre.

def ordonnancement(taches):
    """Taches = liste de (nom, debut, fin). Renvoie un ordonnancement maximal."""
    retenues = []
    fin_courante = float("-inf")
    for tache in sorted(taches, key=lambda t: t[2]):   # tri par date de fin
        if tache[1] >= fin_courante:                   # compatible avec le reste
            retenues.append(tache)
            fin_courante = tache[2]
    return retenues

Le coût se lit sur le code: un tri, donc $\Theta (n\log n)$ comparaisons dans le pire des cas avec un tri par comparaison du chapitre 3, puis un parcours qui effectue exactement $n$ comparaisons de dates, une par tâche. Le tri domine, et le total est $\Theta (n\log n)$ comparaisons dans le pire des cas. Si les tâches arrivent déjà triées par date de fin — ce qui est le cas d'un journal d'événements, par exemple —, il ne reste que le parcours linéaire.

Notez la variable fin_courante: c'est tout l'état de l'algorithme. Il n'a pas besoin de connaître les tâches déjà retenues, seulement la date à laquelle la salle se libère. C'est la signature d'un glouton bien posé.

Démonstration du théorème 9.1. Notons $G=(g_1,g_2,\dots ,g_k)$ les tâches retenues par l'algorithme, dans l'ordre où il les retient, et donc par dates de fin croissantes. Soit $S=(s_1,s_2,\dots ,s_m)$ une solution optimale quelconque, ses tâches étant également rangées par dates de fin croissantes. Comme est optimale, ; nous voulons .

L'échange. Montrons d'abord la propriété suivante, pour tout $j$ compris entre $1$ et $\min (k,m)$:

il existe une solution optimale dont les $j$ premières tâches sont exactement $g_1,\dots ,g_j$.

Raisonnons par récurrence sur $j$.

Pour $j=1$: soit $S$ une solution optimale. Sa première tâche $s_1$ a une date de fin $f(s_1)$. Or $g_1$ est, par construction, la tâche de date de fin minimale de toute l'instance, donc . Posons . Cette est : les tâches commencent toutes après la fin de , donc après , donc après la fin de ; elles restent compatibles entre elles, et le sont maintenant avec . Et : on a retiré une tâche et ajouté une tâche, donc est encore optimale. C'est l'échange, et il a bien fallu vérifier les deux moitiés.

Pour le pas de récurrence, supposons qu'il existe une solution optimale $S$ dont les $j$ premières tâches sont $g_1,\dots ,g_j$, avec $j<k$. Si $S$ n'a pas de -ième tâche, alors , ce qui contredit l'optimalité de : donc possède une tâche . Cette tâche est compatible avec , c'est-à-dire qu'elle commence après ; elle était donc au moment où l'algorithme a choisi , c'est-à-dire qu'elle faisait partie des tâches que la boucle examinait encore. Comme l'algorithme parcourt les tâches par date de fin croissante et retient la première compatible, on a . Le même échange qu'au cas de base — remplacer par — donne une solution admissible (les tâches commencent après ) et de même cardinal, donc optimale, et qui coïncide avec sur tâches.

La conclusion. Appliquons la propriété avec $j=k$: il existe une solution optimale $S^{\star }$ dont les $k$ premières tâches sont $g_1,\dots ,g_k$. Supposons que en contienne une de plus, disons . Alors commence après ; elle était donc compatible avec toutes les tâches retenues au moment où la boucle l'a examinée, et l'algorithme l'aurait retenue. Or il s'est arrêté avec tâches: contradiction. Donc , et comme est optimale, l'est aussi.

Relisez l'endroit exact où le critère est utilisé: une seule fois, à l'inégalité $f(g_{j+1})\le f(s_{j+1})$, et cette inégalité est l'énoncé littéral du critère. C'est toujours ainsi qu'un argument d'échange se lit: il y a une ligne et une seule où l'algorithme entre, et c'est celle-là qu'il faut regarder quand on teste un autre critère.

Deux critères plausibles, et pourquoi ils échouent

Trois critères viennent naturellement à l'esprit devant ce problème: la tâche qui finit le plus tôt, la tâche la plus courte, la tâche qui commence le plus tôt. Le premier est optimal, les deux autres ne le sont pas, et aucun raisonnement vague ne permet de les départager. Il faut des contre-exemples, et les voici — construits, puis vérifiés en exécutant les deux algorithmes.

La durée la plus courte. L'intuition est séduisante: une tâche courte occupe peu la salle, donc en laisse plus pour les autres. Elle est fausse, parce qu'une tâche courte peut être placée exactement à cheval sur deux tâches longues et les tuer toutes les deux. Trois réunions suffisent:

Le critère de la durée retient B, qui dure deux heures, et se retrouve bloqué: A commence à 9h et finit à 13h, donc chevauche B; C commence à 13h, ce qui est avant la fin de B à 14h, donc chevauche B aussi. Une réunion placée. Le critère de la date de fin retient A (fin 13h), rejette B (début 12h, salle libre à 13h), retient C (début 13h): deux réunions. L'énumération des huit sous-ensembles confirme que deux est l'optimum. Le rapport est donc de un à deux, sur une instance de trois éléments.

La date de début la plus tôt. L'intuition est ici celle du guichet: servir les demandes dans l'ordre où elles arrivent. Elle est fausse pour une raison symétrique — la première demande arrivée peut être une réunion d'une journée entière, qui écrase tout ce qui suit.

Le critère du début le plus tôt retient A et s'arrête: une réunion. Le critère de la date de fin retient B, C, D: trois réunions, et c'est l'optimum. Le rapport est de un à trois, et il s'aggrave autant qu'on veut en ajoutant des réunions courtes dans la journée de A.

Ce second critère est d'ailleurs déjà pris en défaut par l'instance témoin des huit tâches: il retient T3 $[0,6)$, puis T7 $[6,10)$, soit deux tâches contre les trois du bon critère. Vous n'aviez pas besoin d'une nouvelle instance pour le réfuter — mais vous aviez besoin de faire le calcul.

L'explorateur ci-dessous vous laisse déplacer trois des six réunions. Le seul affichage à surveiller est le troisième: c'est celui qui ne bouge pas.

Codage de Huffman

Pourquoi des mots de longueurs différentes

Un texte de cent caractères écrits sur un alphabet de six symboles peut se coder sur $\lceil {\log }_{2}6\rceil =3$ bits par caractère, soit 300 bits. Ce codage à longueur fixe a une qualité: le décodage est trivial, on découpe la suite de bits en tranches de trois. Il a un défaut: il donne autant de bits au caractère le plus fréquent qu'au plus rare. Si un caractère apparaît dans 45 % du texte, lui accorder trois bits est un gaspillage de plusieurs dizaines de bits.

L'idée du codage à longueur variable est de donner des mots courts aux caractères fréquents et des mots longs aux caractères rares. Elle soulève immédiatement une difficulté: si tous les mots n'ont pas la même longueur, comment le décodeur sait-il où s'arrête le premier? La réponse tient dans une contrainte structurelle.

L'ambiguïté qu'évite cette contrainte n'est pas théorique. Prenons le code $e=0$, $i=01$, $s=1$: il n'est pas préfixe, puisque $e=0$ est le préfixe de $i=01$. La suite de bits 01 se lit alors soit comme $i$, soit comme $e$ suivi de . Aucune quantité d'ingéniosité du décodeur ne lèvera cette ambiguïté: l'information n'est pas là.

Démonstration. Étant donné un arbre binaire dont les feuilles portent les caractères, le mot d'un caractère est le chemin qui mène à sa feuille. Un mot est préfixe d'un autre si et seulement si le chemin correspondant est un début du second, c'est-à-dire si la première feuille est un ancêtre de la seconde — impossible, puisqu'une feuille n'a pas de descendant. Le code est donc préfixe.

Réciproquement, donnons-nous un code préfixe et construisons l'arbre en insérant chaque mot comme un chemin depuis la racine. Aucun mot n'étant préfixe d'un autre, aucun caractère ne se retrouve sur un nœud interne du chemin d'un autre; chaque caractère occupe donc bien une feuille.

La relation (9.1) est une simple comptabilité: le caractère $c$ apparaît $f(c)$ fois dans le texte et coûte ${\ell }_T(c)$ bits à chaque apparition.

Reste la complétude locale. Supposons qu'un nœud interne $u$ n'ait qu'un seul enfant. Remplaçons $u$ par cet unique enfant: toutes les feuilles du sous-arbre remontent d'un niveau, donc leur profondeur diminue de 1, et $B$ diminue strictement dès qu'il y a au moins une feuille dessous — ce qui est le cas puisque l'arbre est fini et que tout chemin descendant aboutit à une feuille. Un arbre qui n'est pas localement complet n'est donc pas optimal. $\square$

L'algorithme de Huffman

Le critère glouton de Huffman est d'une simplicité désarmante: fusionner à chaque étape les deux nœuds de plus petit poids. On part d'une forêt de feuilles, une par caractère, portant sa fréquence; on répète $|A|-1$ fois: retirer les deux arbres les plus légers, en faire les deux enfants d'un nouveau nœud dont le poids est la somme, remettre ce nœud dans la forêt. À la fin il reste un seul arbre.

import heapq


def huffman(frequences):
    """frequences: dict caractere -> effectif. Renvoie la racine de l'arbre."""
    tas = [(f, i, (c, None, None)) for i, (c, f) in enumerate(sorted(frequences.items()))]
    heapq.heapify(tas)
    rang = len(tas)
    while len(tas) > 1:
        f1, _, gauche = heapq.heappop(tas)
        f2, _, droite = heapq.heappop(tas)
        heapq.heappush(tas, (f1 +

Le second champ du triplet, rang, ne sert qu'à départager deux nœuds de même poids de façon déterministe, pour que la trace du cours soit reproductible: à poids égal, le nœud créé le plus tôt sort le premier. Sans ce champ, Python tenterait de comparer les nœuds eux-mêmes et lèverait une exception; avec un autre départage, on obtiendrait un arbre différent, de même coût total — l'optimum n'est pas unique, ce qui est exactement la situation que la propriété du choix glouton décrit.

Le coût: une construction de tas en $\Theta (n)$ par la méthode de Floyd du chapitre 5, puis $n-1$ tours de boucle comportant chacun deux extractions et une insertion, donc $\Theta (\log n)$ comparaisons chacun. Total: $\Theta (n\log n)$ comparaisons, où $n$ est la taille de l'alphabet et non la longueur du texte.

L'arbre lu donne les codes, et les codes donnent le compte. Voici les deux ensemble.

contre $3\times 100=300$ bits pour le codage à longueur fixe, soit 2,24 bits par caractère au lieu de 3 et une économie de 25,3 %. À titre de repère, l'entropie de cette distribution — la borne inférieure de la théorie de l'information, hors programme de ce cours — vaut environ 2,22 bits par caractère: Huffman est à deux centièmes de bit du minimum absolu.

Pourquoi c'est optimal

La démonstration se fait en deux temps, et le premier temps est un argument d'échange pur. Il répond à la question: pourquoi a-t-on le droit de fusionner les deux plus petits poids?

Démonstration. Soit $T$ un arbre optimal quelconque. Comme il est localement complet (théorème 9.2), une feuille de profondeur maximale y possède une sœur, qui est également une feuille de profondeur maximale. Appelons $b$ et $c$ ces deux sœurs.

Sans perte de généralité, supposons $f(b)\le f(c)$ et $f(x)\le f(y)$. On a alors $f(x)\le f(b)$ et $f(y)\le f(c)$, puisque et sont de fréquences minimales.

Premier échange. Construisons $T^{\prime }$ en échangeant les positions de $x$ et de $b$ dans $T$. Le coût varie de

Le premier facteur est $\le 0$ puisque $f(x)\le f(b)$; le second est $\ge 0$ puisque $b$ est à profondeur maximale. Le produit est donc $\le 0$: on a $B(T^{\prime })\le B(T)$. Comme était optimal, et est optimal aussi.

Second échange. Dans $T^{\prime }$, échangeons de même $y$ et $c$; le même calcul donne un arbre $T^{\prime \prime }$ avec $B(T^{\prime \prime })\le B(T^{\prime })$, donc optimal. Une précaution s'impose ici: le premier échange a pu déplacer , mais il n'a pas pu l'amener à la place de , car et une position ne reçoit qu'un caractère; l'argument reste valable en appliquant le second échange à la position occupée par dans .

Dans $T^{\prime \prime }$, $x$ et $y$ occupent les positions de $b$ et $c$, qui étaient sœurs et à profondeur maximale. L'arbre $T^{\prime \prime }$ est optimal, et il répond à la question. $\square$

Ce lemme est la propriété du choix glouton pour Huffman, énoncée et démontrée. Reste la sous-structure optimale.

Démonstration. Par récurrence sur le nombre $k=|A|$ de caractères.

Base. Pour $k=2$, il n'existe qu'un seul arbre de code localement complet: une racine et deux feuilles, chaque caractère sur un bit. L'algorithme le produit, et il est trivialement optimal.

Hérédité. Supposons le résultat acquis pour $k-1$ caractères, avec $k\ge 3$. Soient $x$ et $y$ les deux caractères de fréquences minimales, ceux que l'algorithme fusionne en premier. Formons l'alphabet réduit $A^{\prime }$ en remplaçant $x$ et $y$ par un unique caractère $z$ de fréquence ; il compte caractères.

Le lien entre les deux coûts. À tout arbre $T^{\prime }$ sur $A^{\prime }$ correspond un arbre $T$ sur $A$, obtenu en remplaçant la feuille $z$ par un nœud interne portant les deux feuilles $x$ et $y$. Les profondeurs de tous les autres caractères sont inchangées, et $x$ et sont un niveau plus bas que ne l'était , d'où

La correspondance est réciproque: à tout arbre $T$ sur $A$ dans lequel $x$ et $y$ sont frères correspond un arbre $T^{\prime }$ sur $A^{\prime }$ vérifiant la même relation. Le terme $f(x)+f(y)$ étant une , minimiser sur les arbres où et sont frères revient exactement à minimiser sur . C'est la sous-structure optimale.

La conclusion. Notons $H$ l'arbre produit par l'algorithme sur $A$. Après la première fusion, l'algorithme travaille exactement sur $A^{\prime }$ — la forêt qu'il manipule est celle de l'instance réduite —, donc le sous-arbre qu'il construit est l'arbre de Huffman $H^{\prime }$ de $A^{\prime }$, optimal sur $A^{\prime }$ par hypothèse de récurrence. Par (9.4), .

Soit maintenant $T^{\star }$ un arbre optimal sur $A$. Le lemme 9.3 permet de le choisir tel que $x$ et $y$ y soient frères; soit $T^{\prime \star }$ l'arbre réduit correspondant. Alors

la majoration venant de l'optimalité de $H^{\prime }$ sur $A^{\prime }$. Donc $B(H)\le B(T^{\star })$, et $H$ est optimal. $\square$

La structure de cette démonstration mérite d'être retenue, car c'est celle de toutes les démonstrations d'optimalité d'un glouton: un lemme d'échange qui autorise le premier choix, une réduction qui montre que le reste est une instance du même problème, une récurrence qui recolle les deux. Le lemme d'échange est la partie difficile; la réduction est la partie qu'on oublie d'écrire.

Le sac à dos fractionnaire

Le problème, et sa version entière

Un cambrioleur, un sac de capacité $W$, et $n$ objets dont le $j$-ième pèse $p_j$ et vaut $v_j$. Il veut emporter le plus de valeur possible sans dépasser la capacité. Deux problèmes se cachent derrière cet énoncé, et ils n'ont pas la même difficulté.

Le second se résout gloutonnement et en $\Theta (n\log n)$ comparaisons; le premier est $NP$-difficile (chapitre 11) et se résout par programmation dynamique au chapitre 10. La seule différence entre les deux énoncés est la clause «entier ou pas du tout», et cette clause change tout. Voir précisément où elle intervient est le but de cette section.

L'instance du cours est la suivante — c'est la même qu'au chapitre 10, pour que les deux traitements se comparent directement. Capacité $W=9$; quatre objets:

Le critère: la valeur par unité de poids

Le critère glouton naturel n'est ni la valeur, ni le poids, mais leur rapport: on remplit le sac en commençant par l'objet dont chaque kilo rapporte le plus, et on continue jusqu'à ce que le sac soit plein — le dernier objet étant pris fractionnairement, pour occuper exactement la place restante.

from fractions import Fraction


def sac_fractionnaire(objets, capacite):
    """objets = liste de (nom, poids, valeur). Renvoie (valeur totale, prises)."""
    reste = Fraction(capacite)
    valeur = Fraction(0)
    prises = []
    for nom, p, v in sorted(objets, key=lambda o: -Fraction(o[2], o[1])):
        if reste == 0:
            break
        quantite 

Les Fraction ne sont pas une coquetterie: le résultat de cette instance est $41/3$, un rationnel non décimal, et l'écrire en virgule flottante donnerait $13,666666666666666$ avec une erreur au dernier chiffre. Le chapitre 1 d'Analyse numérique explique pourquoi; ici il suffit de savoir que, quand la réponse exacte est une fraction, on la calcule en fractions.

Démonstration. Supposons les objets numérotés par rapports décroissants: $v_1/p_1\ge v_2/p_2\ge \cdots \ge v_n/p_n$. Notons le vecteur des fractions produites par le glouton et celui d'une solution optimale quelconque.

Remarquons d'abord que le glouton remplit le sac: soit il épuise tous les objets, et alors aucune solution ne peut faire mieux puisqu'il a tout pris; soit il s'arrête faute de place, et alors ${\sum }_j{g}_j{p}_j=W$. Plaçons-nous dans ce second cas.

Soit $k$ le plus petit indice où $s$ diffère de $g$. Par construction du glouton, $g_j$ vaut 1 pour $j<k$ et le sac n'est pas encore plein après ces objets, donc $g_k>0$ est la plus grande fraction de l'objet que la place autorise. Comme coïncide avec avant et est admissible, on a nécessairement : la solution optimale prend de l'objet que le glouton.

L'échange. Posons $\delta =(g_k-s_k)p_k>0$, le poids manquant. Deux cas.

Si ${\sum }_j{s}_j{p}_j<W$, il reste de la place dans $s$ et l'on peut y ajouter une partie de l'objet $k$ sans rien retirer; cela augmente strictement la valeur, ce qui contredit l'optimalité de $s$. Donc remplit aussi le sac, et le poids manquant sur l'objet se retrouve nécessairement réparti sur des objets d'indice .

Construisons $s^{\prime }$ en retirant un poids total $\delta$ à ces objets d'indice $>k$ — c'est possible puisqu'ils en portent au moins $\delta$ — et en l'ajoutant à l'objet $k$, ce qui est licite puisque $s_k+\delta /p_k=g_k\le 1$. La solution est : son poids total est inchangé, donc encore , et chaque fraction reste dans . Sa valeur varie de

où ${\delta }_j\ge 0$ est le poids retiré à l'objet $j$ et où ${\sum }_{j>k}{\delta }_j=\delta$; l'inégalité vient de pour . Donc est encore optimale, et elle coïncide avec sur un indice de plus.

La conclusion. Chaque échange augmente strictement le nombre d'indices initiaux où la solution coïncide avec $g$; comme il n'y a que $n$ indices, on atteint $g$ après au plus $n$ échanges, sans jamais perdre de valeur. Donc $g$ est optimale. $\square$

Ce que la clause «entier ou rien» détruit

Regardez l'endroit précis où la démonstration utilise la divisibilité: à l'échange, lorsqu'on retire «un poids total $\delta$» à des objets d'indice supérieur. Dans la version 0/1, $\delta$ n'est pas un poids quelconque — on ne peut retirer que des objets entiers, et il n'y a en général aucune façon de retirer exactement $\delta$. L'argument s'effondre là, et il s'effondre parce que le résultat est faux.

Trois nombres pour une instance

Cette instance mérite d'être regardée une dernière fois, parce qu'elle porte trois valeurs distinctes qu'il ne faut jamais confondre:

Ces trois nombres répondent à trois questions différentes sur les mêmes quatre objets. Le premier est ce que fait un algorithme; le deuxième est ce qu'il aurait fallu faire; le troisième est ce qu'on obtiendrait si la contrainte d'intégrité disparaissait. Et l'ordre $11<13<41/3$ n'est pas un accident: l'optimum fractionnaire majore toujours l'optimum 0/1, puisque toute solution 0/1 est une solution fractionnaire particulière. C'est précisément à ce titre que le chapitre 11 réutilisera la valeur fractionnaire — comme borne supérieure dans un algorithme d'approximation.

Et les autres critères gloutons?

Puisque le rapport échoue, essayons les deux autres critères naturels sur le sac 0/1. Le résultat est instructif, et il est un piège.

• Par valeur décroissante: on prend $D$ (valeur 8), puis $C$ (valeur 5) tient dans les 4 unités restantes, et l'on obtient $\{C,D\}$, valeur 13. C'est l'optimum.
• Par poids croissant: on prend $A$, $B$, $C$ (poids $2+3+4=9$), valeur . Un de moins que l'optimum.

Le rendu de monnaie

Le problème le plus familier du chapitre

Une caisse doit rendre un montant $M$ avec des pièces de valeurs données, en minimisant le nombre de pièces. L'algorithme que tout le monde applique sans y penser est glouton: prendre à chaque fois la plus grosse pièce qui ne dépasse pas ce qui reste à rendre.

def rendu_glouton(pieces, montant):
    """Rend le montant avec le moins de pieces possible... si le systeme s'y prete."""
    rendu = []
    for piece in sorted(pieces, reverse=True):
        while montant >= piece:
            rendu.append(piece)
            montant -= piece
    return rendu if montant == 0 else None

Le coût est de $\Theta (k\log k)$ comparaisons pour le tri des $k$ valeurs de pièces, plus une opération par pièce rendue. La boucle while peut être remplacée par une division entière, nombre, montant = divmod(montant, piece), ce qui la rend $\Theta (k\log k)$ tout compris.

Sur le système suisse, il est optimal

Le système suisse en circulation comporte les pièces de 5, 10 et 20 centimes, de 50 centimes, de 1, 2 et 5 francs, c'est-à-dire, exprimées en centimes, les valeurs $5$, $10$, $20$, $50$, $100$, $200$, $500$ — tout montant rendu est un multiple de 5 centimes depuis le retrait de la pièce de 1 centime. Sur ce système, l'algorithme glouton est optimal, et ce n'est pas une évidence: c'est une propriété du système, pas de l'algorithme.

La vérification est mécanique et sans appel: pour chaque montant multiple de 5 entre CHF 0,05 et CHF 100, on compare le nombre de pièces du glouton à celui que donne la programmation dynamique du chapitre 10. Sur les deux mille montants testés, les deux nombres coïncident toujours. Cela ne démontre rien pour CHF 12 500, mais la propriété se démontre par ailleurs, et le principe de la démonstration est un argument d'échange: on montre qu'une solution optimale ne peut contenir, pour chaque valeur de pièce, plus d'un certain nombre d'exemplaires — pas plus d'une pièce de 5 dans un rendu optimal, car deux pièces de 5 se remplacent par une de 10, et ainsi de suite — et l'on en déduit que la solution optimale est forcée d'être celle du glouton.

Sur d'autres systèmes, il échoue

Prenons un système fictif à trois valeurs: 1, 10 et 25. Pour rendre 30, le glouton prend d'abord 25, parce que c'est la plus grosse pièce qui tient; il lui reste 5 à rendre, et comme il n'a plus que des pièces de 1, il en aligne cinq. Six pièces. L'optimum est évidemment $10+10+10$, trois pièces. Le glouton fait donc deux fois trop.

Ce n'est pas un accident isolé: sur les 99 montants de 1 à 99, ce système met le glouton en défaut trente fois — pour tous les montants de 30 à 34, de 40 à 44, de 55 à 59, de 65 à 69, de 80 à 84 et de 90 à 94. À chaque fois le mécanisme est le même: la grosse pièce est prise, et le reste ne se complète qu'avec de la petite monnaie.

Le détail troublant est qu'il suffit d'ajouter une pièce pour réparer le système. Avec les valeurs 1, 5, 10, 25 — le système américain — le glouton redevient optimal: sur les 999 montants de 1 à 999, aucun échec. Ajouter une possibilité rend donc l'algorithme meilleur, alors qu'il avait déjà toutes les anciennes à sa disposition. Une propriété de ce genre est le signe qu'on n'a pas affaire à une caractéristique de l'algorithme mais à une caractéristique arithmétique du système.

«Ça a marché sur mes trois exemples»

Il reste à dire pourquoi ce chapitre insiste tant sur les démonstrations, dans une discipline où l'on peut exécuter son code.

Ce que les tests peuvent et ne peuvent pas

Un algorithme glouton est un objet trompeur: il est court, il est lisible, et il donne presque toujours une réponse plausible. Les trois critères réfutés dans ce chapitre — la durée la plus courte, la date de début la plus tôt, le rapport valeur/poids en version 0/1 — donnent tous l'optimum sur une majorité d'instances tirées au hasard. Le critère de la durée, sur l'instance témoin des huit tâches, trouve même exactement trois tâches, comme le bon critère; c'est en fabriquant délibérément la configuration en trois réunions qu'on le met à terre. Un jeu de tests écrit par la même personne que l'algorithme teste les cas auxquels cette personne a pensé, c'est-à-dire précisément ceux que son critère traite bien.

Il y a pire. Un algorithme glouton faux n'échoue pas bruyamment: il ne lève pas d'exception, il ne boucle pas, il ne rend pas une solution inadmissible. Il rend une solution parfaitement valide, simplement pas la meilleure — et sans l'optimum sous les yeux, rien ne le trahit. C'est le mode de défaillance le plus coûteux qui soit, parce qu'il est silencieux et qu'il peut durer des années.

Ce qu'il faut faire à la place

La discipline tient en trois gestes, dans cet ordre.

Chercher un contre-exemple, exhaustivement. Avant de démontrer, essayez de réfuter. Sur des instances de moins d'une quinzaine d'éléments, énumérez toutes les configurations possibles — ou tirez-en quelques millions au hasard sur un petit domaine — et comparez la sortie du glouton à l'optimum obtenu par force brute. Cette recherche est bon marché, elle s'écrit en dix lignes, et elle tranche: ou bien elle trouve un contre-exemple, et votre critère est mort; ou bien elle n'en trouve pas, et vous avez gagné le droit d'essayer de démontrer.

Ne pas confondre l'absence de contre-exemple avec une démonstration. Une recherche exhaustive sur les instances de taille $\le 8$ n'exclut rien au-delà de 8, et il existe des critères gloutons qui ne fautent qu'à partir d'une taille appréciable. Un test qui ne trouve rien déplace une conjecture, il ne la démontre pas.

Écrire l'argument d'échange. C'est la seule chose qui ferme la question, et il a un avantage que les tests n'auront jamais: il vous dit pourquoi le critère marche. Rappelez-vous où le critère est entré dans la démonstration du théorème 9.1: une seule ligne, l'inégalité $f(g_{j+1})\le f(s_{j+1})$. Quand vous tentez le même argument avec le critère de la durée, cette ligne devient «la durée de $g_{j+1}$ est inférieure à celle de », qui est vraie — et parfaitement inutile, puisque ce dont l'échange a besoin est que au plus tôt, ce que la durée ne garantit pas. L'endroit exact où la démonstration refuse d'aboutir vous indique où chercher le contre-exemple: il suffit de construire une tâche courte qui finit tard.

Synthèse

• Un algorithme glouton construit sa solution par des choix locaux et irrévocables, selon un critère fixé. Il coûte typiquement un tri suivi d'un parcours, donc $\Theta (n\log n)$ comparaisons dans le pire des cas, et il n'est optimal que si le problème possède deux propriétés: la propriété du choix glouton — il existe au moins une solution optimale contenant le premier choix — et la sous-structure optimale, partagée avec la programmation dynamique du chapitre 10.
• L'argument d'échange est la démonstration standard: partir d'une solution optimale quelconque, repérer le premier choix où elle diffère du glouton, l'y remplacer, vérifier que la solution reste admissible et que sa valeur ne se dégrade pas, conclure par récurrence. Les deux vérifications de la troisième étape sont indissociables, et c'est l'admissibilité qui échoue quand le critère est faux.
• L'ordonnancement d'intervalles se résout par la date de fin la plus tôt, avec démonstration: sur l'instance témoin des huit tâches, le glouton retient T1, T4 et T8, soit trois tâches, et c'est l'optimum. Deux critères plausibles sont faux, et chacun a son contre-exemple vérifié: la durée la plus courte place une seule réunion là où l'optimum en place deux (A 9h–13h, B 12h–14h, C 13h–17h), et la date de début la plus tôt en place une là où l'optimum en place trois.
• Le codage de Huffman fusionne à chaque étape les deux nœuds de plus petit poids. Sur l'instance du cours — $e:45$, $s:16$, $a:13$, , , —, les cinq fusions , , , , donnent les codes , , , , , , soit contre 300 pour un code fixe de 3 bits, c'est-à-dire . L'optimalité se démontre par un lemme d'échange — les deux caractères les moins fréquents peuvent être frères à profondeur maximale — puis par récurrence sur l'alphabet réduit.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 15, «Greedy Algorithms»: l'ordonnancement d'intervalles, les deux propriétés, le codage de Huffman avec le lemme d'échange et sa récurrence, et la comparaison explicite entre les deux versions du sac à dos.
• Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française du même chapitre, utile pour fixer le vocabulaire («choix glouton», «sous-structure optimale», «code préfixe»).
• D. Pearson, «A polynomial-time algorithm for the change-making problem», Operations Research Letters 33(3), 2005, p. 231–234 (DOI 10.1016/j.orl.2004.06.001) — l'article qui décide en $O(n^3)$ si un système de pièces est canonique.
• Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 4, la meilleure exposition disponible des deux formes de l'argument d'échange, avec la démonstration greedy stays ahead de l'ordonnancement d'intervalles et l'ordonnancement par échéances.
• Dasgupta, Papadimitriou & Vazirani, Algorithms, McGraw-Hill — chapitre 5, court et vif, avec Huffman et une discussion de l'entropie qui situe ce que le codage préfixe peut et ne peut pas atteindre.
• Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — section 5.5 pour la compression de données et l'implémentation complète de Huffman, table des codes comprise.
• Beauquier, Berstel & Chrétienne, Éléments d'algorithmique, Masson — pour le rendu de monnaie et la question des systèmes canoniques, traitée avec plus de soin que dans la plupart des manuels.