Algorithmes gloutons

Cours · informatique (MP2I/MPI), chapitre 16 · MP2I et MPI · le début du chapitre, la suite sur Adloun

Un algorithme glouton : pour rendre la monnaie, on prend à chaque étape la plus grande pièce possible.

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.

Exercices du chapitre

La suite du cours · Tous les exercices du chapitre