Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• expliquer le principe du retour sur trace et le distinguer de la recherche exhaustive naïve ;
• représenter un problème de décision par un arbre de recherche ;
• identifier les états, les choix possibles, les contraintes et les cas de succès ou d’échec ;
• construire une solution progressivement puis annuler proprement un choix ;
• concevoir des conditions de validité partielle pour détecter rapidement les impasses ;
• appliquer la méthode aux permutations, aux N reines, aux labyrinthes, au Sudoku et à la somme de sous-ensembles ;
• améliorer une recherche grâce à l’élagage, à l’ordre des choix et à la mémorisation des états ;
• analyser la terminaison, la correction et la complexité d’un algorithme de retour sur trace.

Prérequis

• fonctions, procédures et récursivité ;
• tableaux, matrices, piles, ensembles et dictionnaires ;
• arbres et parcours en profondeur ;
• complexité temporelle et spatiale ;
• notions de contrainte, invariant et solution partielle.

Organisation indicative

14.1 Principe

Définition générale

Le retour sur trace, souvent appelé backtracking, est une méthode de recherche systématique adaptée aux problèmes où une solution doit être construite par une succession de décisions. Chaque décision étend une solution partielle. Dès qu’une contrainte est violée ou qu’aucune continuation n’est possible, la dernière décision est annulée.

La méthode repose sur une exploration en profondeur de l’espace des solutions. La pile des appels récursifs mémorise naturellement les décisions prises, ce qui permet de revenir à l’état précédent lorsque la branche courante échoue.

Construction progressive d’une solution

La solution est représentée par un état partiel : un préfixe de permutation, des reines déjà placées, un chemin partiel dans un labyrinthe, quelques cases remplies d’un Sudoku ou un sous-ensemble en cours de construction.

Test d’une possibilité

Pour chaque état, l’algorithme énumère les choix candidats. Un candidat peut être testé avant son application, après son application, ou aux deux moments. Tester avant évite une modification inutile ; tester après peut simplifier le code lorsque la validation porte sur l’état obtenu.

• Un choix admissible respecte les contraintes locales connues.
• Un choix prometteur possède encore une possibilité de mener à une solution.
• Un choix complet produit une solution lorsque tous les éléments attendus sont fixés.
• Un choix impossible doit être rejeté avant d’explorer ses descendants.

Annulation d’un choix

L’annulation restaure exactement l’état qui existait avant le choix. Cette propriété est fondamentale. Une variable, une case, une marque de visite ou une structure auxiliaire modifiée doit retrouver sa valeur précédente.

Exploration d’une autre possibilité

Lorsqu’une branche échoue, la boucle reprend avec le candidat suivant. L’ordre de cette boucle ne change pas l’ensemble des solutions théoriquement accessibles, mais il peut modifier fortement le temps nécessaire pour trouver la première solution.

Récursivité et pile explicite

La récursivité exprime naturellement la profondeur de l’arbre de recherche. Chaque appel correspond à un nœud et mémorise l’état local. Une version itérative peut utiliser une pile explicite contenant les états à explorer, mais l’annulation doit alors être remplacée par la création ou la copie d’états indépendants.

14.2 Arbre de recherche

Nœud de décision

Un nœud représente un état partiel. La racine correspond à l’état initial, avant toute décision. La profondeur indique le nombre de choix déjà réalisés. Une feuille peut être une solution complète, une impasse ou un état terminal ne nécessitant plus de décision.

Branche

Une branche est une séquence de décisions allant de la racine vers un nœud. Elle décrit donc une solution partielle. L’exploration en profondeur suit une branche aussi loin que possible avant de revenir vers un ancêtre possédant encore un enfant non exploré.

Solution partielle

Une solution partielle doit contenir suffisamment d’informations pour poursuivre la recherche et vérifier les contraintes. Elle ne doit pas nécessairement stocker tout l’historique si certaines informations peuvent être reconstruites ou maintenues dans des structures auxiliaires.

Impasse

Une impasse est un état non complet qui ne peut être prolongé vers une solution. Elle apparaît lorsqu’aucun candidat n’est admissible, lorsqu’une contrainte est déjà violée ou lorsqu’une borne prouve qu’un objectif ne peut plus être atteint.

• Dans les N reines, une ligne sans colonne sûre constitue une impasse.
• Dans un labyrinthe, une case dont toutes les voisines sont bloquées ou déjà visitées est une impasse.
• Dans un Sudoku, une case vide sans chiffre possible révèle une contradiction.
• Dans la somme de sous-ensembles à valeurs positives, une somme courante supérieure à la cible peut être abandonnée.

Élagage

L’élagage supprime une branche sans visiter tous ses descendants. Il est correct uniquement si l’on peut démontrer qu’aucun descendant supprimé ne peut produire une solution recherchée ou une solution meilleure que la meilleure déjà connue.

Exemple d’arbre de recherche

Pour former des suites de longueur 3 avec les symboles A et B, chaque nœud choisit le prochain symbole. Si l’on interdit deux B consécutifs, les branches contenant le préfixe BB sont immédiatement élaguées.

Profondeur, facteur de branchement et taille de l’espace

Si chaque nœud possède au plus b enfants et si la profondeur maximale est d, l’arbre brut peut contenir de l’ordre de b^d feuilles. Cette croissance exponentielle explique pourquoi les vérifications anticipées et les heuristiques d’ordre sont essentielles.

14.3 Exemples

Exemple 1 — Génération de permutations

Une permutation de n éléments est un ordre possible contenant chaque élément exactement une fois. Le retour sur trace choisit successivement une valeur non encore utilisée. Lorsque la longueur du préfixe atteint n, une permutation complète est obtenue.

Pour n éléments distincts, il existe n! permutations. L’algorithme ne peut donc pas être asymptotiquement plus rapide que Θ(n · n!) si chaque permutation complète doit être affichée, car l’écriture d’une solution coûte Θ(n).

Exemple 2 — Problème des N reines

Le problème demande de placer N reines sur un échiquier N × N sans que deux reines partagent une ligne, une colonne ou une diagonale. En plaçant exactement une reine par ligne, l’algorithme ne doit choisir qu’une colonne pour chaque ligne.

Le pire cas reste exponentiel, mais les tableaux de colonnes et de diagonales transforment le test de sécurité en O(1). Une version naïve qui parcourt toutes les reines déjà placées effectuerait un test en O(N) à chaque candidat.

Réduction par symétrie

Pour compter les solutions, on peut limiter la première reine à la moitié des colonnes, puis doubler les solutions obtenues par réflexion. Si N est impair, la colonne centrale doit être traitée séparément. Cette réduction exploite une symétrie sûre sans perdre de solutions distinctes à réflexion près.

Exemple 3 — Résolution d’un labyrinthe

Le labyrinthe est modélisé par une matrice. Une case peut être libre, bloquée, visitée, appartenir au chemin courant ou constituer la sortie. Depuis une case, l’algorithme essaie les déplacements disponibles dans un ordre choisi.

Pour trouver le chemin le plus court dans un labyrinthe non pondéré, le parcours en largeur est généralement préférable. Le retour sur trace convient à la recherche d’un chemin quelconque, à l’énumération de tous les chemins ou à des variantes comportant des contraintes supplémentaires.

Exemple 4 — Sudoku simplifié

Un Sudoku 4 × 4 utilise les chiffres 1 à 4 et des blocs 2 × 2. Le principe est identique à celui d’un Sudoku 9 × 9 : choisir une case vide, essayer chaque chiffre autorisé, poursuivre, puis effacer le chiffre si une contradiction apparaît.

Heuristique de la case la plus contrainte

Choisir la première case vide est correct mais parfois inefficace. L’heuristique MRV, Minimum Remaining Values, sélectionne la case possédant le moins de chiffres autorisés. Une contradiction est alors détectée plus tôt et le facteur de branchement est réduit.

Exemple 5 — Somme de sous-ensembles

Étant donné un tableau de nombres et une cible, il faut déterminer s’il existe un sous-ensemble dont la somme vaut la cible. Pour chaque élément, deux décisions sont possibles : l’inclure ou l’exclure.

Sans élagage, l’arbre comporte jusqu’à 2^n feuilles. Si tous les nombres sont positifs, une branche peut être abandonnée lorsque la somme courante dépasse la cible. On peut également utiliser la somme des éléments restants pour détecter une cible devenue inatteignable.

Comparaison des exemples

14.4 Optimisations

Vérification anticipée

Une vérification anticipée détecte une contradiction immédiatement après une décision, avant de descendre plus profondément. Elle réduit la taille de l’arbre sans modifier les solutions valides.

Réduction des possibilités

La réduction de domaine consiste à supprimer les candidats incompatibles avec les décisions déjà prises. Elle peut être appliquée explicitement au moyen d’ensembles de candidats ou implicitement grâce à des tableaux de disponibilité.

• Maintenir les colonnes et diagonales occupées au lieu de rescanner l’échiquier.
• Pré-calculer les voisins accessibles d’une case de labyrinthe.
• Maintenir les chiffres disponibles pour chaque unité d’un Sudoku.
• Trier les éléments d’un problème de somme afin d’obtenir des bornes plus fortes.
• Exploiter les symétries pour ne visiter qu’un représentant de chaque classe équivalente.

Ordre des choix

L’ordre des candidats n’affecte pas la correction lorsque toutes les branches restent explorables, mais il peut déterminer si une solution est trouvée rapidement ou après une exploration très longue.

Mémorisation des états

Deux chemins différents peuvent conduire au même état abstrait. Recalculer cet état répète inutilement le même sous-problème. Une table de mémorisation associe alors une représentation canonique de l’état à son résultat.

La clé doit contenir toutes les informations influençant les décisions futures. Mémoriser uniquement la position dans un labyrinthe est correct si aucune autre ressource n’existe ; ce serait incorrect si le joueur possède des clés, une énergie ou des portes déjà ouvertes.

Branch and bound

Pour un problème d’optimisation, le retour sur trace peut maintenir la meilleure solution trouvée. Une borne estime la meilleure valeur encore théoriquement atteignable depuis un état. Si cette borne ne peut pas améliorer le meilleur résultat courant, la branche est abandonnée.

Coût des optimisations

Une vérification plus forte réduit le nombre de nœuds mais demande davantage de calcul par nœud. L’optimisation pertinente minimise le coût total, et non uniquement le nombre de branches.

Analyse de la complexité

La complexité du retour sur trace s’exprime souvent en fonction du nombre de nœuds explorés. Dans le pire cas, l’élagage peut être inefficace et l’algorithme visite l’ensemble de l’espace de recherche.

La mémoire récursive est généralement O(d), où d représente la profondeur, à laquelle s’ajoutent les structures de l’état. Lorsqu’une copie complète de l’état est créée à chaque appel, le coût mémoire peut devenir O(d × s).

Méthode de conception d’un algorithme de retour sur trace

1. Définir précisément une solution complète et les contraintes qu’elle doit satisfaire.

2. Choisir une représentation compacte de la solution partielle.

3. Identifier les décisions disponibles à chaque niveau.

4. Écrire le cas de succès et les cas d’échec immédiat.

5. Définir l’application et l’annulation exactes d’un choix.

6. Construire un test d’admissibilité aussi précoce que possible.

7. Choisir un ordre de candidats pertinent sans compromettre l’exhaustivité.

8. Ajouter progressivement des bornes, symétries ou mémorisations sûres.

9. Tester sur des cas vides, impossibles, uniques et possédant plusieurs solutions.

10. Mesurer le nombre de nœuds explorés en plus du temps d’exécution.

Applications guidées

Application 1 — Générer les mots binaires sans deux 1 consécutifs

La solution partielle est un préfixe. Le chiffre 0 est toujours admissible. Le chiffre 1 est admissible uniquement si le préfixe est vide ou si son dernier chiffre vaut 0.

Application 2 — Coloration d’un graphe

Chaque sommet doit recevoir une couleur différente de celles de ses voisins. Le retour sur trace choisit un sommet non coloré, essaie les couleurs autorisées et annule la couleur en cas d’échec.

Application 3 — Affectation de salles

Pour chaque cours, il faut choisir une salle compatible avec la capacité et l’horaire. L’heuristique consiste à traiter d’abord le cours possédant le moins de salles compatibles. Une salle déjà utilisée au même horaire est retirée des candidats.

Application 4 — Itinéraire avec contraintes

Un voyageur doit atteindre une destination avec une quantité limitée de carburant et sans revisiter certaines villes. L’état inclut la ville courante, le carburant restant et les villes visitées. La mémorisation doit utiliser l’ensemble de ces informations, et pas seulement la ville.

Travaux dirigés

TD 1 — Identifier les composants d’une recherche

Pour chacun des problèmes suivants, préciser l’état, les candidats, le cas de succès, les impasses et l’annulation : permutations, N reines, labyrinthe et somme de sous-ensembles.

TD 2 — Trace d’une permutation

Tracer les appels de l’algorithme de permutations pour [A, B, C]. Indiquer les valeurs du préfixe et du tableau utilisé avant et après chaque annulation.

TD 3 — Arbre des sous-ensembles

Construire l’arbre de recherche pour T = [3, 5, 6] et cible = 8. Marquer les branches qui atteignent la cible et celles qui se terminent sans solution.

TD 4 — N reines

Pour N = 4, représenter les colonnes choisies pour la première solution trouvée lorsque les colonnes sont essayées de gauche à droite. Montrer les retours sur trace nécessaires.

TD 5 — Labyrinthe

Expliquer pourquoi une case visitée doit être marquée. Donner un exemple de boucle infinie obtenue si cette marque est oubliée.

TD 6 — Sudoku

Comparer le choix de la première case vide avec l’heuristique MRV. Expliquer sur une grille partielle pourquoi MRV peut détecter une contradiction plus tôt.

TD 7 — Correction de l’annulation

L’algorithme place une valeur dans un tableau et ajoute cette valeur à un ensemble utilisé, mais lors du retour il efface seulement le tableau. Identifier l’erreur et ses conséquences.

TD 8 — Élagage sûr ou dangereux

Classer chaque règle : sûre, sûre sous condition ou incorrecte. a) arrêter si somme > cible ; b) ignorer les symétries des N reines ; c) abandonner un Sudoku si une case n’a aucun candidat ; d) ne jamais revenir sur une case de labyrinthe déjà visitée.

TD 9 — Complexité

Donner la taille maximale de l’espace de recherche pour n décisions binaires, une permutation de n éléments et une affectation de n variables possédant chacune k valeurs.

TD 10 — Concevoir une recherche

Concevoir un algorithme générant toutes les combinaisons de k éléments parmi n. Préciser les bornes permettant d’abandonner une branche lorsqu’il ne reste pas assez d’éléments.

Corrigés indicatifs des travaux dirigés

Correction du TD 1

Correction du TD 2

L’ordre des solutions est ABC, ACB, BAC, BCA, CAB, CBA si les candidats sont parcourus dans l’ordre du tableau. Après l’affichage de ABC, C est désélectionné, puis B est désélectionné ; le candidat C est ensuite choisi en deuxième position. Chaque retour restaure exactement la disponibilité du candidat annulé.

Correction du TD 3

Correction du TD 4

Une solution est [1, 3, 0, 2] en indices commençant à 0. En essayant d’abord la colonne 0 pour la première ligne, les lignes suivantes finissent dans une impasse ; la première reine est retirée, puis la colonne 1 est essayée. La restauration concerne la colonne et les deux diagonales.

Correction du TD 5

Sans marque de visite, deux cases voisines A et B peuvent s’appeler mutuellement : A explore B, puis B réexplore A, ce qui répète indéfiniment les appels. La marque de visite empêche de revenir sur la même case dans le chemin courant.

Correction du TD 6

La première case vide peut avoir quatre candidats et créer quatre branches. Une autre case peut n’avoir qu’un seul candidat, ou aucun. MRV choisit cette seconde case : la valeur forcée est appliquée, ou l’impasse est détectée sans créer de branches inutiles.

Correction du TD 7

L’ensemble utilisé doit être restauré en retirant la valeur. Sinon, cette valeur reste interdite dans les branches sœurs. L’algorithme perd alors des solutions valides et peut conclure à tort qu’aucune solution n’existe.

Correction du TD 8

Correction du TD 9

• Décisions binaires : 2^n feuilles.
• Permutation : n! feuilles.
• n variables avec k valeurs : k^n affectations complètes.
• Ces bornes brutes peuvent être fortement réduites par les contraintes.

Correction du TD 10

La borne Longueur(T) - manque garantit qu’après le choix de i, il restera suffisamment d’éléments pour atteindre une combinaison de taille k.

Travail pratique — Laboratoire de retour sur trace

Objectif

Développer une petite bibliothèque de résolution par retour sur trace et mesurer l’influence des optimisations. Le langage peut être Python, C ou Java, mais l’analyse doit être formulée indépendamment du langage.

Travail demandé

1. Implémenter le schéma générique avec instrumentation du nombre de nœuds explorés.

2. Implémenter les permutations et vérifier que n! solutions sont obtenues pour des valeurs distinctes.

3. Résoudre le problème des N reines et compter les solutions pour plusieurs valeurs de N.

4. Résoudre un labyrinthe en affichant le chemin trouvé et les cases abandonnées.

5. Implémenter le Sudoku 4 × 4, puis comparer première case vide et MRV.

6. Résoudre la somme de sous-ensembles avec et sans bornes.

7. Mesurer le temps, le nombre d’appels et la profondeur maximale.

8. Rédiger une conclusion expliquant quelle optimisation apporte le meilleur gain selon le problème.

Instrumentation conseillée

Jeux d’essai minimaux

Grille d’évaluation proposée

Erreurs fréquentes et bonnes pratiques

Synthèse du chapitre

• Le retour sur trace explore en profondeur un arbre de décisions.
• Une solution est construite progressivement à partir de choix admissibles.
• Chaque choix doit pouvoir être annulé afin de restaurer exactement l’état précédent.
• Une impasse déclenche le retour vers le dernier nœud possédant un candidat non exploré.
• L’élagage correct supprime les branches incapables de produire une solution pertinente.
• L’ordre des choix, la propagation et la mémorisation peuvent réduire fortement le temps moyen.
• Le pire cas reste souvent exponentiel ou factoriel.
• La qualité de la représentation de l’état conditionne la correction et les performances.

Glossaire

Auto-évaluation