Exploration exhaustive et retour sur trace

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

Le retour sur trace : une solution au problème des quatre reines, trouvée en essayant puis en revenant en arrière.

14.1 Quand on ne sait rien de mieux

Les quatre chapitres qui suivent celui-ci — diviser pour régner, gloutons, programmation dynamique — sont des méthodes : elles exploitent une structure du problème pour éviter d'en examiner toutes les solutions. Ce chapitre traite du cas où l'on n'a pas cette chance : il faut les examiner.

Le programme donne à ces chapitres un objectif commun, et il est ambitieux : « donner des outils de conception d'algorithmes et parvenir à ce que les étudiants puissent, dans une situation simple, sélectionner une stratégie pertinente par eux-mêmes et la mettre en œuvre de façon autonome ».

14.2 La force brute

Définition 14.1Recherche par force brute

Énumérer toutes les solutions candidates, tester chacune, garder celles qui conviennent. C'est toujours correct, et c'est presque toujours trop lent.

Exemple 14.2Le coût de l'exhaustif, en trois ordres de grandeur

Ce qu'on énumère	Nombre	$n = 20$	$n = 40$
Les sous-ensembles de $n$ objets	$2^{n}$	$1 0^{6}$	$1 0^{12}$
Les permutations de $n$ objets	$n!$	$2, 4 \cdot 1 0^{18}$	$8 \cdot 1 0^{47}$
Les mots de longueur $n$ sur ${0, 1, 2}$	$3^{n}$	$3, 5 \cdot 1 0^{9}$	$1 0^{19}$

À 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.

Exemple 14.3Énumérer les sous-ensembles par leurs bits

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 $Θ (n 2^{n})$ .

Exercices du chapitre

Ordonner avant de parcourir : deux nombres de somme donnée corrigé
Ce que chaque test d'élagage rapporte corrigé
Énumérer les permutations d'un mot à lettres répétées corrigé
L'ordre des choix change tout corrigé
Le même sous-problème, vingt-deux millions de fois corrigé
Problème — Colorier un graphe, et casser les symétries corrigé

La suite du cours · Tous les exercices du chapitre