Algorithmes gloutons

Cours complet · informatique (MP2I/MPI), chapitre 16 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

16.1 Choisir sans revenir en arrière

Un algorithme glouton construit une solution par une suite de choix, chacun étant le meilleur sur le moment, et aucun n'étant jamais remis en cause. Il ne revient pas en arrière — c'est ce qui le distingue du chapitre chap:exploration — et il n'explore pas d'alternatives — c'est ce qui le distingue du chapitre chap:dynamique.

D'où sa vitesse : souvent $Θ (n lo g n)$ , le temps d'un tri. Et d'où son danger : il donne presque toujours une réponse, et cette réponse est parfois fausse. Tout l'enjeu du chapitre est là. Le programme distingue d'ailleurs nettement les deux régimes : « algorithme glouton fournissant une solution exacte » en première année, « exemple d'algorithme d'approximation fourni par la méthode gloutonne » en seconde.

16.2 Quand le glouton échoue

Commençons par l'échec : il est plus instructif que le succès.

Exemple 16.1Le rendu de monnaie

Rendre une somme $S$ avec le moins de pièces possible. Le glouton naturel prend à chaque fois la plus grosse pièce qui tient.

Avec le système européen ${1, 2, 5, 10, 20, 50}$ , il est optimal. Avec le système ${1, 3, 4}$ et $S = 6$ :

	Choix	Total
Glouton	$4$ , puis $1$ , puis $1$	3 pièces
Optimal	$3$ , puis $3$	2 pièces

Le glouton a pris le $4$ parce qu'il était le plus gros, et s'est condamné à finir en pièces de $1$ . Aucun message d'erreur, aucune boucle infinie : simplement une réponse fausse.

AttentionUn glouton se démontre, ou ne s'emploie pas

C'est la règle du chapitre. Sur un problème d'optimisation, un glouton non démontré est une conjecture, et il faut soit prouver son optimalité, soit exhiber un contre-exemple, soit — si l'on garde le glouton parce qu'il est rapide — prouver une borne sur son écart à l'optimum. Ces trois issues sont les trois sections qui suivent.

16.3 Trois gloutons exacts

Le programme cite trois exemples d'algorithmes gloutons exacts : « codage de Huffman, sélection d'activité, ordonnancement de tâches unitaires avec pénalités de retard sur une machine unique ».

16.3.1 La sélection d'activités

Exemple 16.2Le problème

$n$ activités, la $i$ -ième occupant l'intervalle $[d_{i}, f_{i} [$ . Une seule salle. Combien d'activités peut-on tenir sans chevauchement ?

Méthode : Le bon critère : la fin la plus tôt

Trois gloutons plausibles, et un seul juste :

Critère	Verdict
la plus courte d'abord	faux
celle qui commence le plus tôt	faux
celle qui finit le plus tôt	optimal


(* Nombre maximal d'activités compatibles. Précondition : a est un tableau de
   couples (début, fin) avec début < fin. Complexité : Theta(n log n). *)
let selection a =
  let b = Array.copy a in
  Array.sort (fun (_, f1) (_, f2) -> compare f1 f2) b;   (* tri par FIN *)
  let compte = ref 0 and libre = ref neg_infinity in
  Array.iter (fun (d, f) ->
    if float_of_int d >= !libre then begin
      incr compte;
      libre := float_of_int f
    end) b;
  !compte

◆Théorème 16.3Optimalité

Le glouton « fin la plus tôt » rend une sélection de cardinal maximal.

Démonstration (Par échange)

Soit $g_{1}$ l'activité qui finit le plus tôt, et soit $O$ une solution optimale quelconque, dont la première activité (dans l'ordre des fins) est $o_{1}$ . Alors $f_{g_{1}} \leq f_{o_{1}}$ par définition de $g_{1}$ .

Remplaçons $o_{1}$ par $g_{1}$ dans $O$ . Le résultat est encore valide : $g_{1}$ finit avant $o_{1}$ , donc il ne chevauche aucune des activités suivantes de $O$ , qui commençaient toutes après $f_{o_{1}} \geq f_{g_{1}}$ . Et le cardinal est inchangé : la solution obtenue est donc encore optimale, et elle commence par le choix glouton.

En itérant sur le problème résiduel — les activités commençant après $f_{g_{1}}$ —, on transforme $O$ en la solution gloutonne sans jamais diminuer son cardinal. La solution gloutonne est donc optimale.

ImportantL'argument d'échange, à retenir

Cette démonstration est le patron de toutes les preuves de glouton :

prendre une solution optimale quelconque ;
montrer qu'on peut y substituer le premier choix glouton sans perdre en qualité ;
itérer.

La conclusion n'est pas « le glouton est l'unique optimum » — il peut y en avoir d'autres — mais « il en existe un qui commence par le choix glouton », ce qui suffit.

16.3.2 Tâches unitaires avec pénalités de retard

Exemple 16.4Le problème, et le glouton qui le résout

$n$ tâches, chacune durant une unité de temps, chacune ayant une échéance $e_{i}$ et une pénalité $p_{i}$ due si elle est en retard. Une seule machine. Minimiser la somme des pénalités.

Le glouton : trier les tâches par pénalité décroissante, et placer chacune au créneau libre le plus tardif possible avant son échéance. Si aucun n'est libre, la tâche sera en retard — on la relègue à la fin.


(* Somme minimale des pénalités. Précondition : t est un tableau de couples
   (échéance >= 1, pénalité >= 0). Complexité : O(n²) en version simple. *)
let ordonnancement t =
  let n = Array.length t in
  let u = Array.copy t in
  Array.sort (fun (_, p1) (_, p2) -> compare p2 p1) u;   (* pénalité DÉCROISSANTE *)
  let occupe = Array.make (n + 1) false in
  let perdu = ref 0 in
  Array.iter (fun (e, p) ->
    let c = ref (min e n) in
    while !c >= 1 && occupe.(!c) do decr c done;
    if !c >= 1 then occupe.(!c) <- true                  (* placée à temps *)
    else perdu := !perdu + p) u;                         (* en retard : on paie *)
  !perdu

Pourquoi le plus tard possible : occuper un créneau tardif laisse libres les créneaux précoces, dont les tâches à échéance serrée auront besoin. Placer au plus tôt bloquerait des créneaux dont d'autres dépendent — et le glouton deviendrait faux.

16.3.3 Le codage de Huffman

C'est l'exemple le plus riche, et le programme le cite deux fois : ici, et au chapitre chap:textes pour la compression.

Définition 16.5Le problème

Coder les caractères d'un texte par des mots binaires de longueurs variables, de façon que le texte codé soit le plus court possible. Les caractères fréquents doivent recevoir des codes courts.

Le code doit être préfixe : aucun mot de code ne doit être le préfixe d'un autre, sans quoi le décodage serait ambigu. Un code préfixe se représente exactement par un arbre binaire dont les feuilles portent les caractères : le chemin racine-feuille donne le code, gauche $= 0$ , droite $= 1$ .

Méthode : L'algorithme de Huffman

Mettre chaque caractère dans une file de priorité, avec sa fréquence comme clé.
Tant qu'il reste plus d'un élément : extraire les deux plus petites fréquences, en faire les deux fils d'un nouveau nœud de fréquence leur somme, réinsérer ce nœud.
Le dernier élément est la racine de l'arbre de codage.


type huff = Feuille of char * int | Interne of huff * huff * int
let freq = function Feuille (_, f) -> f | Interne (_, _, f) -> f

(* Arbre de Huffman des caractères pondérés. Précondition : liste non vide.
   Complexité : Theta(k log k) pour k caractères. *)
let huffman couples =
  let f = file_priorite_vide () in
  List.iter (fun (c, n) -> inserer f (Feuille (c, n))) couples;
  while taille f > 1 do
    let a = extraire_min f in
    let b = extraire_min f in
    inserer f (Interne (a, b, freq a + freq b))
  done;
  extraire_min f

La file de priorité du chapitre chap:tas est ici l'outil exact : on extrait $2 (k - 1)$ fois le minimum et l'on insère $k - 1$ fois, chacune en $O (lo g k)$ .

Exemple 16.6Sur un texte de 100 caractères

Caractère	Fréquence	Code Huffman	Bits	Longueur fixe
`a`	45	`0`	45	135
`b`	13	`101`	39	39
`c`	12	`100`	36	36
`d`	16	`111`	48	48
`e`	9	`1101`	36	27
`f`	5	`1100`	20	15
Total	100		224	300

Un code de longueur fixe demanderait 3 bits par caractère, soit 300 bits. Huffman en demande 224, soit un gain de 25 %. Le a, présent 45 fois, ne coûte qu'un bit ; le f, présent 5 fois, en coûte quatre.

◆Théorème 16.7Optimalité de Huffman

Le code produit minimise la longueur totale $\sum_{c} n_{c} ℓ_{c}$ parmi tous les codes préfixes.

Démonstration (Les deux lemmes, et l'échange)

Lemme 1. Dans un arbre optimal, deux caractères de fréquences minimales peuvent être placés en frères à la profondeur maximale. En effet, si un caractère $x$ de fréquence plus grande occupait une feuille plus profonde qu'un caractère $y$ moins fréquent, les échanger ferait varier le coût de

$(n_{x} - n_{y}) (ℓ_{y} - ℓ_{x}) \leq 0,$

car $n_{x} \geq n_{y}$ et $ℓ_{y} \leq ℓ_{x}$ : le coût ne peut qu'être inférieur ou égal. L'échange ne dégrade donc rien.

Lemme 2. Fusionner les deux caractères les moins fréquents en un seul, de fréquence la somme, donne un problème à $k - 1$ caractères dont toute solution optimale s'étend en une solution optimale du problème initial : le coût des deux problèmes diffère exactement de $n_{x} + n_{y}$ , indépendamment de l'arbre choisi.

Par récurrence sur $k$ , l'algorithme — qui fait précisément cette fusion à chaque étape — est optimal.

16.4 Le glouton comme approximation

Le programme prévoit ce second régime en deuxième année : « exemple d'algorithme d'approximation fourni par la méthode gloutonne. On peut traiter par exemple : couverture des sommets dans un graphe, problème du sac à dos en ordonnant les objets. »

Définition 16.8Algorithme d'approximation

Un algorithme est une $ρ$ -approximation d'un problème de minimisation si, sur toute instance, sa solution coûte au plus $ρ$ fois l'optimum. Le rapport $ρ$ est garanti, pas moyen.

Exemple 16.9Couverture des sommets : le glouton par les arêtes

Trouver un ensemble minimal de sommets touchant toutes les arêtes. Le problème est np-complet (chapitre chap:decidabilite). Un glouton très simple donne pourtant une garantie :


(* Une couverture des sommets, au plus 2 fois plus grande que l'optimale. *)
let couverture aretes =
  let couverts = Hashtbl.create 97 in
  List.iter (fun (u, v) ->
    if not (Hashtbl.mem couverts u) && not (Hashtbl.mem couverts v) then begin
      Hashtbl.replace couverts u ();      (* on prend LES DEUX extrémités *)
      Hashtbl.replace couverts v ()
    end) aretes;
  Hashtbl.fold (fun s () acc -> s :: acc) couverts []

Démonstration (C'est une 2-approximation)

Les arêtes qui déclenchent une prise n'ont deux à deux aucune extrémité commune : elles forment un couplage $M$ . Toute couverture, y compris l'optimale, doit contenir au moins un sommet par arête de $M$ , donc $∣ O P T ∣ \geq ∣ M ∣$ . Or l'algorithme prend exactement $2∣ M ∣$ sommets. D'où $∣ A L G ∣ = 2∣ M ∣ \leq 2∣ O P T ∣$ .

Ce que cela vaut. Un problème sans algorithme polynomial connu reçoit ici une solution en temps linéaire, jamais pire que le double de l'optimum. C'est le marché typique de l'approximation : on renonce à l'exactitude, on garde une garantie.

AttentionLe glouton « le plus gros rapport » sur le sac à dos n'a AUCUNE garantie

Prendre les objets par valeur/poids décroissante paraît raisonnable. Sur un sac de capacité $C$ avec deux objets — l'un de poids $1$ et valeur $2$ , l'autre de poids $C$ et valeur $C$ — le glouton prend le premier (rapport $2$ ), puis ne peut plus rien mettre : valeur $2$ , contre un optimum de $C$ . Le rapport d'approximation est donc arbitrairement mauvais.

La parade classique — prendre le meilleur entre la solution gloutonne et le meilleur objet seul — donne une $2$ -approximation. Un glouton d'approximation aussi se démontre : sans preuve, on ignore s'il vaut $2$ ou $n$ .

16.5 Ce qu'il faut retenir

ImportantGloutons : quatre points

Un choix localement optimal, jamais remis en cause. Rapide — souvent le temps d'un tri.
Il donne toujours une réponse, et elle est parfois fausse : rendre 6 avec ${1, 3, 4}$ coûte 3 pièces au glouton, 2 à l'optimum.
L'optimalité se démontre par échange : partir d'un optimum, y substituer le premier choix glouton sans perdre, itérer. Trois exemples exacts au programme : sélection d'activités, tâches unitaires avec pénalités, Huffman.
Quand l'exactitude est hors d'atteinte, un glouton peut offrir une garantie — la 2-approximation de la couverture des sommets. Mais cette garantie se démontre aussi ; sans preuve, il n'y en a aucune.

Continuer sur Adloun : animation, QCM, fiches, exercices