Exploration exhaustive et retour sur trace

À un milliard d'opérations par seconde, la première ligne passe d'un millième de seconde à dix-huit minutes quand $n$ double ; la deuxième était déjà hors de portée à $n=20$. Retenez cet écart : il justifie à lui seul tout le reste du livre.

Un sous-ensemble de $\{0,\dots ,n-1\}$ se code par un entier de $n$ bits : le bit $i$ vaut $1$ si l'élément $i$ est pris.

/* Énumère les 2^n sous-ensembles de {0, ..., n-1}. Précondition : 0 <= n < 31. */
for (int masque = 0; masque < (1 << n); masque = masque + 1) {
    for (int i = 0; i < n; i = i + 1) {
        if ((masque >> i) % 2 == 1) { /* l'élément i est dans ce sous-ensemble */ }
    }
}

Deux boucles, aucune récursion, aucune structure : c'est la manière la plus courte d'être exhaustif sur les parties d'un ensemble. Le coût est $\Theta (n{2}^n)$.

Placer $n$ reines sur un échiquier $n\times n$ sans qu'aucune n'en attaque une autre. On place une reine par colonne, de gauche à droite.

(* Compte les placements valides de n reines. Précondition : n >= 1.
   pos.(c) est la ligne de la reine de la colonne c ; on remplit de 0 à n-1. *)
let n_reines n =
  let pos = Array.make n 0 in
  let total = ref 0 in
  let compatible c l =
    (* la reine (c, l) n'attaque aucune des reines des colonnes 0 .. c-1 *)
    let ok = ref true in
    for j = 0 to c - 1 do
      if pos.(j) = l || abs (pos.(j) - l) = c - j then ok := false
    done;
    !ok
  in
  let rec explorer c =
    if c = n then incr total
    else
      for l = 0 to n - 1 do
        if compatible c l then begin
          pos.(c) <- l;
          explorer (c + 1)
          (* rien à défaire : pos.(c) sera réécrit au tour suivant *)
        end
      done
  in
  explorer 0;
  !total

Ce que l'élagage rapporte, mesuré en exécutant cet algorithme et en comptant ses appels :

Le facteur passe de $304$ à $281000$ quand $n$ va de $6$ à $10$ : l'élagage gagne d'autant plus que le problème est gros, parce qu'il coupe des sous-arbres dont la taille croît, elle aussi, exponentiellement.

Une seule ligne fait tout le travail : abs (pos.(j) - l) = c - j teste les deux diagonales à la fois — deux reines sont sur une même diagonale exactement lorsque l'écart des lignes égale l'écart des colonnes.

Le problème des huit reines figure aussi parmi les exemples possibles d'algorithmes de Las Vegas, au chapitre chap:probabilistes : on tire des placements au hasard jusqu'à en trouver un valide. Deux méthodes, un même problème — et c'est délibéré, le programme les met en regard.

$n$ objets de poids $p_i$ et de valeur $v_i$, un sac de capacité $C$. On veut la valeur maximale transportable.

(* Valeur maximale d'un sous-ensemble d'objets de poids total <= c.
   Précondition : c >= 0, i est l'indice du prochain objet examiné. *)
let rec sac p v c i =
  if i >= Array.length p then 0
  else
    let sans = sac p v c (i + 1) in
    if p.(i) > c then sans                     (* ÉLAGAGE : l'objet ne rentre pas *)
    else max sans (v.(i) + sac p v (c - p.(i)) (i + 1))

La complexité reste $O(2^n)$ dans le pire cas. Ce même problème sera résolu en $O(nC)$ au chapitre chap:dynamique, et de façon approchée en glouton au chapitre chap:gloutons : trois méthodes, trois compromis entre exactitude et coût.