Retour sur trace

Résumé en cinq points

1Principe du retour sur trace

1.1Solutions partielles et choix successifs

1.2L'arbre des solutions partielles

L'exploration se représente par un arbre :

• la racine est la solution partielle vide ;
• les fils d'un nœud sont ses prolongements d'un choix ;
• les feuilles de profondeur $n$ sont les candidats complets.

L'ensemble de cet arbre n'est jamais construit en mémoire. Il est parcouru en profondeur par les appels récursifs, et la pile d'exécution contient à chaque instant le chemin de la racine au nœud courant.

Revenir sur trace, c'est remonter d'un niveau dans cet arbre. L'arbre sert à raisonner sur le flot de contrôle : dans quel ordre les choix sont essayés, quand on remonte, ce qui reste à explorer.

1.3Élagage

Une branche coupée près de la racine supprime un sous-arbre entier. Tout l'art du retour sur trace est de détecter l'échec le plus tôt possible, avec un test de compatibilité qui ne regarde que le dernier choix par rapport aux précédents.

Il suffit donc de vérifier le dernier choix, car les précédents ont déjà été vérifiés entre eux quand on les a faits. C'est ce qui rend le test local et rapide.

2Problème des huit reines

2.1Énoncé et modélisation

Il s'agit de placer huit reines sur un échiquier de $8 \times 8$ cases de sorte qu'aucune ne menace une autre, c'est-à-dire que deux reines ne partagent ni ligne, ni colonne, ni diagonale. On généralise à $n$ reines sur un échiquier $n \times n$.

Première modélisation, qui élague déjà. Comme deux reines ne peuvent pas être sur la même ligne, il y en a exactement une par ligne. On cherche donc, pour chaque ligne $i$, sa colonne $c_i$. Les contraintes deviennent :

• $c_i \neq c_j$ pour les colonnes ;
• $\abs{c_i - c_j} \neq \abs{i - j}$ pour les diagonales.

Il y a $8^8$, environ 16,8 millions, suites de colonnes candidates, et $8!$, soit $40\,320$, si l'on impose des colonnes distinctes. Le problème compte 92 solutions.

2.2Programme récursif

On garde les colonnes déjà placées dans une liste, la plus récente en tête. Le test de compatibilité compare la nouvelle colonne $c$ à chaque colonne $c'$ placée $d$ lignes plus haut.

let compatible placees c =
  let rec aux l d = match l with
    | [] -> true
    | c' :: q -> c' <> c && abs (c' - c) <> d && aux q (d + 1)
  in aux placees 1

let rec compter n placees k =
  if k = n then 1
  else begin
    let total = ref 0 in
    for c = 0 to n - 1 do
      if compatible placees c then
        total := !total + compter n (c :: placees) (k + 1)
    done;
    !total
  end

L'appel compter 8 [] 0 renvoie 92. Pour obtenir les solutions elles-mêmes et non leur nombre, on remplace le compteur par une liste accumulée, et le cas k = n renvoie la liste [placees], dont on concatène les résultats. Le coût mémoire devient alors proportionnel au nombre de solutions.

Le retour en arrière est ici implicite. Comme la liste des colonnes est immuable, revenir d'un appel récursif retrouve automatiquement l'ancienne liste.

2.3Coût

Le test de compatibilité au niveau $k$ coûte de l'ordre de $k$. Le nombre de nœuds visités est très inférieur à $8^8$ grâce à l'élagage.

Le nombre de nœuds croît cependant de façon exponentielle avec $n$, et le problème des $n$ reines reste coûteux à énumérer pour $n$ de l'ordre de trente.

3Résolution d'un sudoku

3.1Modélisation

Une grille de sudoku est un tableau de $9 \times 9$ cases, certaines déjà remplies. Il faut remplir les cases vides avec des chiffres de 1 à 9, de sorte que chaque ligne, chaque colonne et chacun des neuf carrés de $3 \times 3$ contienne chaque chiffre une fois.

On représente la grille par une matrice mutable, int array array, avec 0 pour une case vide. Un choix consiste à placer un chiffre dans la première case vide rencontrée.

3.2Retour sur trace avec une structure mutable

let rec resoudre g k =
  if k = 81 then true
  else
    let i = k / 9 and j = k mod 9 in
    if g.(i).(j) <> 0 then resoudre g (k + 1)
    else begin
      let trouve = ref false and v = ref 1 in
      while not !trouve && !v <= 9 do
        if possible g i j !v then begin
          g.(i).(j) <- !v;
          if resoudre g (k + 1) then trouve := true
          else g.(i).(j) <- 0
        end;
        incr v
      done;
      !trouve
    end

Le test possible g i j v vérifie que v n'apparaît ni dans la ligne i, ni dans la colonne j, ni dans le carré de $3 \times 3$ qui contient la case. Le coin supérieur gauche de ce carré a pour coordonnées $3 \times (i / 3)$ et $3 \times (j / 3)$ en division entière. Le test parcourt 27 cases au plus, coût constant pour une grille de taille fixe.

let possible g i j v =
  let ok = ref true in
  for k = 0 to 8 do
    if g.(i).(k) = v || g.(k).(j) = v then ok := false
  done;
  let i0 = 3 * (i / 3) and j0 = 3 * (j / 3) in
  for a = i0 to i0 + 2 do
    for b = j0 to j0 + 2 do
      if g.(a).(b) = v then ok := false
    done
  done;
  !ok

Avec une structure mutable, le retour sur trace doit défaire explicitement les modifications, ici remettre la case à 0.

3.3Améliorer l'élagage

L'ordre des choix influe beaucoup sur le coût. Une heuristique efficace consiste à choisir d'abord la case vide qui a le moins de chiffres possibles :

• une case qui n'en a qu'un ne crée pas de branchement ;
• une case qui n'en a aucun détecte l'échec immédiatement.

On peut aussi maintenir pour chaque ligne, colonne et carré l'ensemble des chiffres déjà utilisés, pour tester la compatibilité en temps constant.

4Autres exemples et généralités sans théorie

4.1Sous-ensemble de somme donnée

Étant donné une liste d'entiers positifs et une cible $s$, existe-t-il une sous-liste de somme $s$ ? L'arbre des choix est binaire, chaque élément est pris ou non, soit $2^n$ feuilles. Deux règles d'élagage :

• si la somme partielle dépasse $s$, on abandonne la branche, puisque les entiers sont positifs ;
• si la somme partielle plus la somme de tous les éléments restants n'atteint pas $s$, on l'abandonne aussi.

Trier la liste par ordre décroissant avant de commencer rend la première règle d'élagage plus efficace, car les grandes valeurs font dépasser la cible plus tôt.

4.2Énumérer toutes les solutions ou s'arrêter à la première

Les deux variantes s'écrivent de la même manière :

• pour énumérer, on compte ou on accumule chaque solution complète et on continue ;
• pour s'arrêter à la première, on renvoie un booléen ou une option et on interrompt la boucle dès un succès, comme dans le sudoku.

En OCaml, une exception peut aussi servir à remonter d'un coup toute la pile au premier succès.

4.3Schéma commun

Tous les exemples suivent le même schéma, que le programme demande de dégager sans le formaliser. Une fonction récursive reçoit la solution partielle :

• si elle est complète, on la traite ;
• sinon, pour chaque prolongement possible qui respecte les contraintes, on prolonge et on appelle récursivement, puis on défait le prolongement si la structure est mutable.

Ce schéma repose sur deux preuves simples.

5Lien avec l'algorithme min-max

L'algorithme min-max du tronc commun explore lui aussi un arbre, l'arbre des coups d'un jeu à deux joueurs, en profondeur et par appels récursifs. À chaque nœud, il essaie tous les coups, évalue récursivement la position obtenue, puis revient pour essayer le coup suivant.

C'est la même mécanique que le retour sur trace, à ceci près que le résultat d'un nœud n'est pas un succès ou un échec mais le maximum ou le minimum des valeurs de ses fils, selon le joueur qui a la main. Le programme précise que la notion de retour sur trace est réinvestie à cette occasion.

Méthodes

Ce qu'il faut savoir refaire en khôlle

1. Expliquer le principe du retour sur trace et dessiner les premiers niveaux de l'arbre des solutions partielles pour le problème des quatre reines.
2. Écrire en OCaml le comptage des solutions du problème des $n$ reines, avec le test de compatibilité sur les colonnes et les diagonales.
3. Écrire un solveur de sudoku par retour sur trace sur une matrice mutable, en expliquant la remise à zéro.
4. Résoudre par retour sur trace le problème du sous-ensemble de somme donnée, avec deux règles d'élagage.
5. Majorer le nombre de nœuds explorés et expliquer pourquoi le pire cas reste exponentiel.
6. Comparer le retour sur trace à l'algorithme min-max.

Les résultats à connaître

Le programme présente le retour sur trace « sans théorie générale ». Les résultats ci-dessous ne sont donc pas des théorèmes de cours. Ce sont des propriétés à savoir établir sur chaque exemple.

• Terminaison. Supposons que chaque appel prolonge la solution partielle d'un choix, que la longueur soit bornée par n et que chaque choix soit pris dans un ensemble fini. Alors l'exploration termine. Exigible avec démonstration sur l'exemple traité.
• Validité. Supposons que la racine respecte les contraintes et que le test du dernier choix soit exact. Alors toute solution partielle présente sur la pile respecte toutes les contraintes, et toute solution renvoyée est correcte. Exigible avec démonstration.
• Complétude. Si l'on n'élague que des nœuds dont aucun descendant n'est une solution, toute solution est atteinte. Exigible avec démonstration.
• Pile. Le nombre d'appels imbriqués vaut au plus n + 1, sans compter les fonctions auxiliaires. Exigible.
• Majoration du nombre de nœuds. Si le niveau i offre au plus mᵢ choix, l'arbre a au plus 1 + m₁ + m₁m₂ + … + m₁m₂⋯mₙ nœuds. Exigible.
• n reines. Il y a 1 solution pour n = 1, aucune pour n = 2 et n = 3, et 2 pour n = 4, ce qui se vérifie à la main. La valeur 92 pour n = 8 est un résultat de calcul. L'existence d'une solution pour tout n ≥ 4 est admise et hors programme.
• n reines avec des colonnes distinctes. L'arbre a au plus Σ n!/(n − k)! nœuds, pour k de 0 à n, et cette somme est au plus e·n!. Exigible en exercice.
• Sous-ensemble de somme donnée. L'élagage « la somme partielle dépasse la cible » est correct si les entiers sont positifs ou nuls. Exigible.
• Min-max. C'est le même parcours en profondeur, mais la valeur d'un nœud est le maximum ou le minimum de celles de ses fils. Exigible au tronc commun.
• Hors programme : élagage alpha-bêta, propagation de contraintes, algorithme des liens dansants, et NP-complétude dans ce chapitre.

Clés de démonstration

Terminaison. On prend pour mesure n − k, où k est la longueur de la solution partielle. Chaque appel récursif augmente k de 1, et chaque boucle sur les choix est finie. Astuce : la mesure est un entier naturel qui décroît strictement le long de toute chaîne d'appels.

Validité. On raisonne par récurrence sur la profondeur. La solution vide respecte les contraintes. On ne descend que si le nouveau choix est compatible avec chacun des précédents. Or, dans les exemples du programme, les contraintes portent sur des paires de choix. Astuce : ce sont des contraintes binaires, donc tester le dernier choix contre les autres suffit.

Complétude. Soit s une solution complète. Chacun de ses préfixes respecte les contraintes, donc aucun n'est élagué. Par récurrence sur la longueur du préfixe, la boucle, qui essaie toutes les valeurs, finit par descendre jusqu'à s. Astuce : un préfixe de solution est toujours compatible. Dans la variante « première solution », on en déduit que la fonction réussit dès qu'une solution existe.

Nombre de nœuds. Le niveau k contient au plus m₁⋯m_k nœuds. Pour les reines à colonnes distinctes, cela donne n!/(n − k)!. Avec j = n − k, la somme vaut n!·Σ 1/j!, pour j de 0 à n, qui est au plus e·n!. Astuce : changer d'indice pour reconnaître la série de l'exponentielle.

Coût total. On multiplie le nombre de nœuds par le travail fait en un nœud, qui est le nombre de choix essayés fois le coût du test. Astuce : un test en temps constant fait gagner un facteur n sur tout l'arbre.

Exemples et contre-exemples à connaître

1. Deux et trois reines. L'arbre est parcouru en entier et renvoie 0. Pour prouver qu'il n'y a pas de solution, l'exploration doit être complète.
2. Quatre reines. Les deux solutions sont, colonnes numérotées de 0, (1, 3, 0, 2) et (2, 0, 3, 1). Elles sont symétriques l'une de l'autre par rapport à l'axe vertical.
3. Huit reines. Il y a 92 solutions, et 12 seulement à symétrie de l'échiquier près. Les symétries permettent un élagage supplémentaire.
4. Somme donnée avec un entier négatif. Pour la liste 5, −3 et la cible 2, la somme partielle 5 dépasse la cible, mais 5 − 3 = 2. Une règle d'élagage doit être une vraie condition d'échec.
5. Permutations. On passe de nⁿ feuilles à n! feuilles en refusant une valeur déjà utilisée. Une bonne modélisation vaut un élagage.
6. Mots bien parenthésés. L'élagage est parfait : chaque nœud mène à une solution, et il n'y a aucun échec (exercice 6).
7. Sudoku. La borne brute est 9⁸¹, environ 2·10⁷⁷ remplissages. Il n'existe pourtant qu'environ 6,7·10²¹ grilles complètes valides. Sur une grille réelle, le nombre de nœuds visités est infime devant ces nombres.
8. Min-max sur un arbre de profondeur 2. La racine maximise et a deux fils minimisants, de feuilles (3, 5) et (2, 9). Leurs valeurs sont 3 et 2, la racine vaut 3. Min-max sans alpha-bêta visite toutes les feuilles, c'est un retour sur trace sans élagage.
9. Un triangle n'est pas coloriable avec 2 couleurs. L'échec apparaît au troisième sommet, puis on remonte jusqu'à la racine.

Techniques du chapitre

Technique 1 : fixer les choix et leur domaine. On veut les mots binaires de longueur n sans deux 1 consécutifs. Le choix xᵢ vaut 0 ou 1, et le test refuse xᵢ = 1 si x₍ᵢ₋₁₎ = 1. Pour n = 3 on obtient 000, 001, 010, 100 et 101, soit 5 mots.

Technique 2 : choisir le type de retour. Pour compter, on renvoie un entier. Pour tester l'existence, on renvoie un booléen. Pour une solution, on renvoie une option. Pour toutes les solutions, on renvoie une liste. Une exception remonte d'un coup au premier succès (exercice 8).

Technique 3 : défaire dans une structure mutable. On marque, on appelle, on démarque : utilise.(v) <- true, puis aux (k + 1), puis utilise.(v) <- false. Le démarquage se place juste après l'appel, dans le même bloc que le marquage.

Technique 4 : rendre le test incrémental. Pour les reines, on marque les colonnes, les diagonales où i + c est constant et celles où i − c est constant. Le test coûte alors O(1) au lieu de O(k). L'indice i − c + n − 1 évite les indices négatifs.

Technique 5 : élaguer par une borne. Pour la liste 2, 3, 4 et la cible 10, la somme totale 9 est inférieure à 10. On élague dès la racine. Seul ce nœud est visité, aucun de ses descendants n'est exploré.

Technique 6 : compter les nœuds niveau par niveau. Pour les permutations de 3 éléments, on trouve 1 + 3 + 6 + 6 = 16 nœuds. Les feuilles ne sont qu'une partie du coût.

Technique 7 : essayer d'abord le choix le plus contraint. Au sudoku, une case qui n'a qu'un candidat ne crée pas de branchement. Il vaut mieux la remplir avant une case qui en a quatre.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

let permutations n =
  let utilise = Array.make n false and res = ref [] in
  let rec aux k acc =
    if k = n then res := acc :: !res
    else
      for v = 0 to n - 1 do
        if not utilise.(v) then begin
          utilise.(v) <- true;
          aux (k + 1) (v :: acc);
          utilise.(v) <- false
        end
      done in
  aux 0 [];
  !res

let rec cherche l reste s =
  if s = 0 then Some []
  else if s < 0 || reste < s then None
  else match l with
    | [] -> None
    | x :: q ->
        match cherche q (reste - x) (s - x) with
        | Some sol -> Some (x :: sol)
        | None -> cherche q (reste - x) s

let rec libre coul c l = match l with
  | [] -> true
  | v :: q -> coul.(v) <> c && libre coul c q

let colorable g k =
  let n = Array.length g in let coul = Array.make n (-1) in
  let rec aux s =
    if s = n then true
    else begin
      let ok = ref false in
      for c = 0 to k - 1 do
        if not !ok && libre coul c g.(s) then begin
          coul.(s) <- c;
          if aux (s + 1) then ok := true else coul.(s) <- -1
        end
      done;
      !ok
    end in
  aux 0

let reines n =
  let col = Array.make n false in
  let d1 = Array.make (2 * n - 1) false and d2 = Array.make (2 * n - 1) false in
  let rec aux i =
    if i = n then 1 else
    let t = ref 0 in
    for c = 0 to n - 1 do
      if not (col.(c) || d1.(i + c) || d2.(i - c + n - 1)) then begin
        col.(c) <- true; d1.(i + c) <- true; d2.(i - c + n - 1) <- true;
        t := !t + aux (i + 1);
        col.(c) <- false; d1.(i + c) <- false; d2.(i - c + n - 1) <- false
      end
    done;
    !t in
  aux 0

let rec dyck n o f =
  if f = n then 1
  else (if o < n then dyck n (o + 1) f else 0)
     + (if f < o then dyck n o (f + 1) else 0)

exception Trouve of int list

let premiere n =
  let rec aux placees k =
    if k = n then raise (Trouve placees)
    else
      for c = 0 to n - 1 do
        if compatible placees c then aux (c :: placees) (k + 1)
      done in
  try aux [] 0; None with Trouve l -> Some (List.rev l)

let rec gagnante n =
  let res = ref false in
  for k = 1 to min 3 n do
    if not !res && not (gagnante (n - k)) then res := true
  done;
  !res

Erreurs fréquentes