Les deux mauvais critères de la sélection d'activités

Un glouton par critère se réalise ainsi : prendre la meilleure activité restante, écarter toutes celles qui la chevauchent, recommencer. C'est ce programme, et non un simple parcours dans l'ordre trié, qui a été confronté à l'optimum calculé sur les $2^n$ sous-ensembles.

(* Nombre d'activités retenues par le glouton de critère cle.
   Précondition : a est un tableau de couples (début, fin) avec début < fin.
   Complexité : O(n^2) telle qu'écrite. *)
let glouton cle a =
  let n = Array.length a in
  let dispo = Array.make n true and compte = ref 0 and reste = ref true in
  while !reste do
    let meilleur = ref (-1) in
    for i = 0 to n - 1 do
      if dispo.(i) && (!meilleur < 0 || cle a.(i) < cle a.(!meilleur))
      then meilleur := i done;
    if !meilleur < 0 then reste := false
    else begin
      let (dm, fm) = a.(!meilleur) in
      incr compte;
      (* [d,f[ chevauche [dm,fm[ exactement quand d < fm et dm < f *)
      for i = 0 to n - 1 do
        if dispo.(i) then begin
          let (d, f) = a.(i) in
          if d < fm && dm < f then dispo.(i) <- false end done
    end
  done; !compte

« La plus courte d'abord » échoue sur $[0,3[$, $[2,4[$, $[3,6[$. Le glouton prend $[2,4[$, la plus courte, qui chevauche les deux autres : 1 activité. L'optimum est $\{[0,3[,[3,6[\}$, soit 2.

Pourquoi : la plus courte peut être au milieu, où elle chevauche deux activités qui, elles, ne se chevauchent pas entre elles. Sa brièveté ne dit rien de son encombrement.

« Celle qui commence le plus tôt » échoue sur $[0,10[$, $[1,3[$, $[4,6[$, $[7,9[$. Le glouton prend $[0,10[$ et n'en prendra pas d'autre : 1 activité, contre 3 pour l'optimum. Une seule activité longue commençant tôt bloque tout le reste, et l'écart est ici arbitrairement grand.

Les trois critères confrontés, d'abord sur les onze activités $[1,4[$, $[3,5[$, $[0,6[$, $[5,7[$, $[3,9[$, $[5,9[$, $[6,10[$, $[8,11[$, $[8,12[$, $[2,14[$, $[12,16[$, puis sur $200000$ instances de $3$ à $5$ activités tirées au hasard :

Deux remarques que la mesure impose. D'abord, « la plus courte d'abord » trouve l'optimum sur le jeu de onze : un glouton faux réussit souvent, et un unique essai bien choisi ne prouve rien — c'est tout l'objet de l'avertissement du cours. Ensuite, il ne se trompe que sur $2,4\%$ des instances aléatoires, six fois moins que le critère du début : être moins souvent faux n'est pas être correct, et il n'y a pas de demi-optimalité.

Pourquoi le bon critère est bon, en une phrase. Choisir l'activité qui finit le plus tôt, c'est laisser le plus de temps possible à tout ce qui suit. Aucun autre critère ne maximise la ressource restante — et c'est exactement ce que formalise l'argument d'échange du cours. Un glouton correct optimise, non pas ce qu'il prend, mais ce qu'il laisse.