La recherche combinatoire & le backtracking

Certains problèmes ne se laissent pas résoudre par une formule ni par un algorithme glouton : il faut, d'une manière ou d'une autre, parcourir l'ensemble des configurations possibles. Vérifier un circuit sur toutes ses entrées, énumérer tous les ordonnancements, trouver le meilleur trajet… autant de cas où l'on aimerait tout essayer. Le problème, c'est que « tout » grossit de façon vertigineuse : un ordinateur moderne examine de l'ordre du million de configurations par seconde, et il faut bien mesurer ce que cela représente. Un million de permutations, ce sont tous les arrangements de 10 ou 11 objets, pas plus. Un million de sous-ensembles, ce sont toutes les combinaisons d'une vingtaine d'éléments, pas plus.

Au-delà, l'exploration naïve devient impossible. Skiena propose alors deux armes complémentaires : le retour sur trace (backtracking), qui énumère proprement toutes les solutions et que l'on rend praticable par un élagage (pruning) astucieux ; et, lorsque l'espace reste trop vaste pour tout visiter, les méthodes heuristiques comme le recuit simulé, qui renoncent à l'optimalité garantie pour produire de très bonnes solutions en temps raisonnable.

Le backtracking : un parcours en profondeur de l'arbre des solutions

Le backtracking est une façon systématique de passer en revue toutes les configurations d'un espace de recherche : permutations, sous-ensembles, arbres couvrants, chemins d'un graphe, partitions en classes de couleurs… Le point commun de ces problèmes est qu'il faut générer chaque configuration exactement une fois — ni doublon, ni oubli. On modélise donc la recherche par un vecteur a = (a₁, a₂, …, aₙ), où chaque aᵢ est choisi dans un ensemble fini ordonné Sᵢ.

À chaque étape, on tente d'étendre une solution partielle (a₁, …, aₖ) en lui ajoutant un élément. On teste ensuite : ce que l'on a est-il une solution complète ? Si oui, on la traite (on l'affiche ou on la compte). Sinon, on vérifie si cette solution partielle peut encore mener à une solution complète. Le backtracking construit ainsi un arbre de solutions partielles, et le parcourt par un parcours en profondeur (depth-first search, DFS).

Le squelette générique de Skiena

Skiena dégage une ossature réutilisable pour tout problème de backtracking. Elle s'appuie sur cinq sous-routines spécifiques à l'application : isASolution, constructCandidates, processSolution, et la paire makeMove / unmakeMove. Le drapeau finished autorise une terminaison anticipée (utile dès qu'on cherche une seule solution).

// Squelette générique de backtracking (DFS de l'arbre des solutions).
// Complexité : proportionnelle à la taille de l'arbre exploré.
interface Problem<C, I> {
  isASolution(a: C[], k: number, input: I): boolean;
  constructCandidates(a: C[], k: number, input: I): C[];
  processSolution(a: C[], k: number, input: I): void;
  makeMove?(a: C[], k: number, input: I): void;
  unmakeMove?(a: C[], k: number, input: I): void;
}

let finished = false; // arrêt prématuré possible

function backtrack<C, I>(a: C[], k: number, input: I, p: Problem<C, I>) {
  if (p.isASolution(a, k, input)) {
    p.processSolution(a, k, input);
    return;
  }
  k = k + 1;
  const candidates = p.constructCandidates(a, k, input);
  for (const c of candidates) {
    a[k] = c;
    p.makeMove?.(a, k, input);
    backtrack(a, k, input, p);
    p.unmakeMove?.(a, k, input);
    if (finished) return; // on coupe net si demandé
  }
}

Deux idées rendent cette structure correcte et efficace. La correction vient de l'énumération exhaustive : aucune configuration valide n'est manquée. L'efficacité vient du fait qu'aucun état n'est visité deux fois. La récursivité fait le reste : comme un nouveau tableau de candidats est calculé à chaque appel, les choix d'un niveau n'interfèrent jamais avec ceux d'un autre.

Générer les objets combinatoires

Tous les sous-ensembles

Combien y a-t-il de sous-ensembles d'un ensemble à n éléments ? Chaque nouvel élément double les possibilités, d'où 2ⁿ sous-ensembles. On représente un sous-ensemble par un vecteur de n booléens : aᵢ vaut true si et seulement si l'élément i est présent. Le candidat pour chaque position est donc simplement {true, false}, et a est une solution dès que k === n.

// Énumère les 2^n sous-ensembles de {1, …, n}. — O(n · 2^n)
function generateSubsets(n: number): number[][] {
  const out: number[][] = [];
  const a: boolean[] = [];

  function recurse(k: number): void {
    if (k === n) {
      const subset: number[] = [];
      for (let i = 0; i < n; i++) if (a[i]) subset.push(i + 1);
      out.push(subset);
      return;
    }
    for (const include of [true, false]) {
      a[k] = include; // candidats Sₖ = {true, false}
      recurse(k + 1);
    }
  }

  recurse(0);
  return out;
}

L'ordre de génération dépend de l'ordre des candidats : comme true précède false, le sous-ensemble plein sort en premier et l'ensemble vide en dernier.

Toutes les permutations

Il y a n! permutations de {1, …, n} : n choix pour la première position, n − 1 pour la deuxième, et ainsi de suite. La représentation naturelle : un vecteur de n cases, où les candidats pour la position k sont exactement les éléments non encore présents dans la solution partielle.

// Énumère les n! permutations de {1, …, n}. — O(n · n!)
function generatePermutations(n: number): number[][] {
  const out: number[][] = [];
  const a: number[] = [];
  const inPerm = new Array<boolean>(n + 1).fill(false);

  function recurse(k: number): void {
    if (k === n) {
      out.push(a.slice(0, n));
      return;
    }
    for (let i = 1; i <= n; i++) {
      if (inPerm[i]) continue; // candidats Sₖ = {1..n} − a
      a[k] = i;
      inPerm[i] = true; // makeMove
      recurse(k + 1);
      inPerm[i] = false; // unmakeMove
    }
  }

  recurse(0);
  return out;
}

L'astuce inPerm — un vecteur de bits des éléments déjà placés — remplace une recherche linéaire dans a par un test en temps constant. Du fait de l'ordre des candidats, les permutations sortent en ordre lexicographique : 123, 132, 213, 231, 312, 321.

L'élagage : couper les branches sans espoir

Énumérer toutes les possibilités garantit la correction, mais c'est souvent ruineux. Prenons le problème du voyageur de commerce (traveling salesman problem, TSP) : énumérer les n! permutations des sommets et garder la moins coûteuse donne le tour optimal. Mais construire toutes les permutations puis les analyser est un gâchis. Si l'arête (v₁, v₂) n'existe pas dans le graphe, les (n − 2)! permutations commençant par (v₁, v₂) sont du temps perdu. Mieux vaut élaguer après v₁, v₂ et passer à v₁, v₃.

L'élagage consiste à couper la recherche dès l'instant où l'on a établi qu'une solution partielle ne peut pas s'étendre en une solution complète. Pour le TSP, si l'on a déjà trouvé un tour de coût Ct et qu'une solution partielle a a déjà un coût d'arêtes CA > Ct, inutile de continuer : tout tour prolongeant ce préfixe coûtera plus cher que t. Une autre piste consiste à exploiter les symétries : tout tour est un cycle, on peut donc fixer v₁ comme premier sommet et économiser un facteur n sans manquer aucune solution intéressante (il n'y a que (n − 1)! tours distincts, pas n!).

Étude de cas : le Sudoku

Le Sudoku illustre à merveille la puissance de l'élagage. L'espace d'états est la suite des cases vides ; les candidats pour la case (i, j) sont les chiffres de 1 à 9 absents de la ligne i, de la colonne j et du secteur 3×3 contenant (i, j). On recule dès qu'une case n'a plus de candidat. Deux décisions changent radicalement le temps de calcul :

• Choix de la prochaine case. Plutôt qu'une case arbitraire, on choisit la case la plus contrainte — celle qui a le moins de candidats. Souvent elle n'en a qu'un : le choix est forcé, et le fixer réduit les possibilités des autres cases. Passer en moyenne de 3 à 2 choix par case est un gain énorme, car il se multiplie à chaque position.
• Valeurs possibles. Au lieu du simple comptage local (les chiffres non encore vus sur la ligne/colonne/secteur), on anticipe (look ahead) : si une autre case ouverte se retrouve sans aucun candidat, la solution partielle est condamnée — on recule immédiatement plutôt que d'attendre de tomber sur cette case.

Les chiffres mesurés par Skiena (nombre d'appels à isASolution) sont éloquents :

Choix de case	Valeurs	Facile	Moyen	Difficile
arbitraire	comptage local	1 904 832	863 305	jamais terminé
arbitraire	anticipation	127	142	12 507 212
plus contrainte	comptage local	48	84	1 243 838
plus contrainte	anticipation	48	65	10 374

Sans anticipation, le puzzle difficile ne se termine jamais ; avec les deux stratégies, il tombe en quelques milliers d'étapes. Le temps de résolution chute d'un facteur supérieur à 1 200 — de presque une heure à quelques secondes.

Quand l'exhaustif est hors de portée : les heuristiques

Le backtracking trouve l'optimum, mais tout algorithme qui parcourt toutes les configurations est condamné sur les grandes instances. Les méthodes heuristiques offrent une alternative : on renonce à la garantie d'optimalité pour obtenir de bonnes solutions rapidement. Skiena en compare trois sur le TSP. Toutes partagent deux ingrédients : une représentation de l'espace des solutions (pour le TSP, un tableau des sommets décrivant le tour) et une fonction de coût qui évalue la qualité d'une solution (la somme des poids des arêtes).

Échantillonnage aléatoire

L'échantillonnage aléatoire (random sampling), ou méthode de Monte-Carlo, est le plus simple : on tire des solutions au hasard, on les évalue, et on garde la meilleure rencontrée. Encore faut-il savoir tirer uniformément dans l'espace — un problème étonnamment subtil.

// Paire non ordonnée uniforme par rejet. — O(1) en espéré
function randomPair(n: number): [number, number] {
  for (;;) {
    let i = 1 + Math.floor(Math.random() * n);
    let j = 1 + Math.floor(Math.random() * n);
    if (i === j) continue; // on rejette et on recommence
    if (i > j) [i, j] = [j, i];
    return [i, j];
  }
}

Quand l'échantillonnage aléatoire est-il pertinent ? Quand les bonnes solutions sont abondantes (trouver un brin de paille dans une botte de foin), ou quand l'espace n'a aucune cohérence : si rien n'indique qu'on « se rapproche » de la solution, autant tirer au hasard. C'est le cas pour trouver un grand nombre premier (environ un entier sur ln n est premier, dispersés arbitrairement) — d'où son usage en cryptographie RSA. Sur le TSP, en revanche, c'est médiocre : 1,5 million de tirages donnent un tour plus de trois fois plus coûteux que l'optimum, car l'espace est presque entièrement peuplé de mauvaises solutions.

Recherche locale et montée de colline

Une recherche locale (local search) associe à chaque solution un voisinage et se déplace vers le voisin le plus prometteur. On n'explicite jamais le graphe des voisinages (il aurait (n − 1)! sommets pour le TSP) : on définit un mécanisme de transition qui modifie légèrement la solution courante. Pour le TSP, échanger les positions de deux sommets ne touche qu'une poignée d'arêtes, ce qui permet d'évaluer le coût de façon incrémentale en temps constant au lieu de tout recalculer en O(n).

La montée de colline (hill climbing) part d'un point arbitraire et n'accepte que les transitions qui améliorent le score, jusqu'à n'avoir plus aucun voisin meilleur.

// Montée de colline pour le TSP. delta < 0 = amélioration.
function hillClimbing(s: number[], cost: (a: number[]) => number,
                      swap: (a: number[], i: number, j: number) =>
                        number): void {
  let stuck = false;
  do {
    stuck = true;
    for (let i = 0; i < s.length; i++) {
      for (let j = i + 1; j < s.length; j++) {
        const delta = swap(s, i, j); // applique et renvoie Δcoût
        if (delta < 0) stuck = false; // on garde l'amélioration
        else swap(s, j, i); // sinon on défait l'échange
      }
    }
  } while (!stuck); // on s'arrête au sommet local
}

La recherche locale brille quand l'espace est très cohérent (un seul « relief », convexe : la recherche dichotomique et le simplexe en sont des cas) et quand l'évaluation incrémentale est bien moins chère que l'évaluation globale. Sur le TSP, elle fait bien mieux que l'aléatoire — un tour 19,6 % au-dessus de l'optimum — mais reste prisonnière de ses collines basses.

Recuit simulé : accepter parfois de reculer

Le recuit simulé (simulated annealing) autorise, de temps à autre, des transitions vers des solutions pires. Cela paraît contre-productif, mais c'est précisément ce qui permet de s'échapper d'un minimum local : notre malheureux coincé dans le chalet ferait mieux de briser la vitre et de sauter par la fenêtre. L'inspiration vient du refroidissement d'un métal en fusion : à haute température, les particules sautent volontiers vers des états plus énergétiques ; à mesure que le système refroidit, ces sauts se raréfient.

Le cœur du procédé est le critère d'acceptation. Une transition qui améliore le coût est toujours acceptée. Une transition qui le dégrade est acceptée avec la probabilité exp(−Δ / (k·T)) : plus la dégradation Δ est faible et plus la température T est élevée, plus elle a de chances de passer.

Recuit simulé
  Créer une solution initiale S ; température t
  répéter
    pour i = 1 à longueur-palier faire
      générer une transition aléatoire S -> Sᵢ
      si C(Sᵢ) <= C(S)              alors S = Sᵢ   (amélioration)
      sinon si exp(-(C(Sᵢ)-C(S))/(k·t)) > random[0,1)  alors S = Sᵢ
    réduire t                        (refroidissement)
  jusqu'à stabilisation de C(S)
  renvoyer S

Le calendrier de refroidissement (cooling schedule) gouverne tout. Au début, on explore largement (forte probabilité d'accepter une dégradation) ; à la fin, on se cantonne aux améliorations locales. Skiena recommande : température initiale t₁ = 1 ; décroissance exponentielle tₖ = α · tₖ₋₁ avec 0,8 ≤ α ≤ 0,99 ; et 100 à 1 000 itérations par palier de température.

// Recuit simulé. transition(i, j) applique l'échange et renvoie Δ.
function anneal(s: number[],
                transition: (i: number, j: number) => number,
                n: number): void {
  const COOLING = 0.95;   // α : décroissance exponentielle
  const STEPS = 500;      // itérations par palier
  const K = 1e-2;         // normalise la fonction d'énergie
  let temperature = 1.0;
  let cost = 0; // coût courant (calculé incrémentalement)

  for (let step = 0; step < 3000; step++) { // 3000 × STEPS = 1,5 M itérations
    temperature *= COOLING;
    for (let j = 0; j < STEPS; j++) {
      const i1 = Math.floor(Math.random() * n);
      const i2 = Math.floor(Math.random() * n);
      const delta = transition(i1, i2);
      const merit = Math.exp(-delta / (K * temperature));
      if (delta < 0) cost += delta;              // ACCEPTE (gain)
      else if (merit > Math.random()) cost += delta; // ACCEPTE (perte)
      else transition(i1, i2); // REJETTE : on défait
    }
  }
}

Sur le TSP à 48 villes, et avec le même budget de 1,5 million d'itérations, le recuit simulé descend à 9,2 % de l'optimum (contre 19,6 % pour la montée de colline et plus de 200 % pour l'aléatoire). En le laissant tourner 5 millions d'itérations, on atteint 2,2 % de l'optimum. C'est la méthode heuristique de prédilection de Skiena.

Modéliser pour le recuit simulé

La force du recuit simulé tient à la simplicité de la modélisation. Quelques exemples canoniques :

• Coupe maximale (maximum cut). Partitionner les sommets en V₁ et V₂ pour maximiser le poids des arêtes traversantes. Espace : 2ⁿ⁻¹ partitions (un vecteur de bits, v₁ fixé). Transition : déplacer un sommet d'un côté à l'autre (basculer un bit). Le coût se recalcule en temps proportionnel au degré du sommet.
• Ensemble indépendant (independent set). Plutôt qu'une fonction de coût rigide (0 dès qu'il reste une arête), Skiena suggère C(S) = |S| − λ · mₛ / T, où mₛ est le nombre d'arêtes induites et T la température : le terme dépendant de T chasse les arêtes plus vite à mesure que le système refroidit, tout en laissant plus de souplesse au début.

Les « war stories » de Skiena (l'assemblage sélectif de « non-radios », la compression de puces à ADN) racontent toutes la même chose : la fonction de coût se peaufine par tâtonnements. Sur la puce HIV, il a fallu ajouter terme après terme — créditer la petite dimension, favoriser une forme carrée, biaiser les tirages vers les préfixes/suffixes utiles — pour faire converger l'algorithme. Le résultat (puce 130×132 contre 192×192) fut excellent, mais obtenu en passant plus de temps à régler le programme qu'à l'écrire.

Un mot sur les algorithmes génétiques

D'autres méthodes s'inspirent de la nature : réseaux de neurones, colonies de fourmis, et surtout les algorithmes génétiques (genetic algorithms) — qui maintiennent une « population » de solutions se « reproduisant » par croisement et mutation selon leur « fitness ». L'intuition est séduisante, mais Skiena est franchement sceptique : ces techniques tiennent souvent plus de la jolie analogie que de résultats démontrés.

Exhaustif ou heuristique : que choisir ?

Critère	Recherche exhaustive (backtracking)	Heuristique (recuit simulé)
Garantie	Solution optimale	Bonne solution, non garantie optimale
Taille gérable	~15 à 50 éléments (avec élagage)	Milliers d'éléments et plus
Levier principal	Élagage des branches mortes	Fonction de coût et calendrier de refroidissement
Risque	Explosion combinatoire	Rester bloqué (atténué par les sauts)
Effort de mise au point	Modéliser l'espace d'états	Régler les constantes par tâtonnements
Quand l'utiliser	Petite instance, optimum requis, vérification	Grande instance, « assez bon » suffit

À retenir

• Le backtracking est un DFS de l'arbre des solutions partielles : on étend pas à pas, on traite si c'est une solution, on défait en cas d'impasse. Tout tient dans cinq routines : isASolution, constructCandidates, processSolution, makeMove/unmakeMove.
• Bien définir l'espace d'états suffit à générer sous-ensembles (2ⁿ, vecteur de booléens), permutations (n!, candidats = éléments non placés) ou chemins d'un graphe.
• L'élagage est le facteur décisif : couper une branche dès qu'elle ne peut plus aboutir fait passer un problème d'impossible à instantané. Sur le Sudoku, case la plus contrainte + anticipation divisent le travail par plus de 1 200.
• Le backtracking trouve l'optimum mais ne tient que pour de petites instances (~15 à 50 éléments) ; au-delà, passez aux heuristiques.
• L'échantillonnage aléatoire ne vaut que si les bonnes solutions sont abondantes ou l'espace incohérent ; la montée de colline trouve vite un optimum local mais s'y fait piéger.
• Le recuit simulé s'échappe des minima locaux en acceptant parfois une dégradation, contrôlée par la température qui décroît exponentiellement. C'est l'heuristique de référence de Skiena ; l'effort se concentre sur la fonction de coût, à régler par tâtonnements — contrairement aux algorithmes génétiques, qu'il déconseille.