|
L’algorithme de backtracking explore efficacement un espace de recherche en essayant systématiquement différentes combinaisons et en abandonnant les chemins dont il est garanti qu’ils ne mèneront pas à une solution. Il fonctionne sur le principe de la *recherche en profondeur* avec un ajout crucial :élagage .
Voici un aperçu de son fonctionnement :
1. Représentation de l'espace d'état : Le problème est représenté sous forme d’arbre ou de graphique où chaque nœud représente une solution partielle. Le nœud racine représente l'état initial et les branches représentent les choix ou les décisions prises à chaque étape. Les feuilles représentent soit des solutions complètes, soit des impasses.
2. Exploration récursive (recherche en profondeur) : L'algorithme commence au nœud racine et explore une branche à la fois, en allant aussi profondément que possible (profondeur d'abord). Cela signifie qu’il fait une série de choix jusqu’à ce qu’il trouve une solution ou se retrouve dans une impasse.
3. Vérification des contraintes/Promesse : À chaque nœud, une vérification est effectuée pour voir si la solution partielle actuelle est toujours « prometteuse », ce qui signifie qu'il est possible de l'étendre en une solution complète. C'est là que l'efficacité entre en jeu. Si la solution partielle actuelle viole les contraintes du problème (par exemple, dans un puzzle Sudoku, placer un nombre qui se trouve déjà dans la ligne, la colonne ou le bloc 3x3), l'algorithme sait qu'il n'a pas besoin d'explorer davantage cette branche. C'est la taille étape.
4. Retour en arrière : Si un nœud n'est pas jugé prometteur, ou si un nœud feuille représente une tentative infructueuse de recherche de solution, l'algorithme "revient" au nœud précédent (son parent) et essaie une branche différente (un choix différent). Cela implique d’annuler les choix faits le long de cette branche et d’explorer des possibilités alternatives.
5. Solution trouvée : Lorsqu'un nœud feuille représente une solution complète et valide, l'algorithme a trouvé une solution et peut soit s'arrêter (si trouver une solution est suffisante), soit continuer à rechercher d'autres solutions en revenant en arrière et en explorant d'autres branches.
Exemple :problème des N-Reines
Envisageons de placer N reines d'échecs sur un échiquier N×N de telle sorte qu'aucune reine ne se menace.
* Espace d'état : Chaque nœud de l'arbre représente un placement partiel de reines sur le plateau.
* Choix : A chaque niveau de l'arbre, un choix est fait quant à l'endroit où placer la prochaine reine dans la colonne.
* Contrainte : La contrainte est qu'il n'y a pas deux reines sur la même ligne, colonne ou diagonale.
* Taille : Si le placement d'une reine viole la contrainte, cette branche est élaguée. L’algorithme n’explore pas plus loin dans cette branche.
* Retour en arrière : Si un placement entraîne une violation, l'algorithme revient à la colonne précédente, supprime la reine et essaie une position différente dans cette colonne.
En résumé : L'efficacité du backtracking découle de sa capacité à éviter d'explorer des parties inutiles de l'espace de recherche en éliminant intelligemment les branches qui sont garanties de ne pas conduire à une solution. Cela réduit considérablement le temps de calcul par rapport aux méthodes de recherche exhaustives qui tenteraient chaque combinaison. L'efficacité dépend de la manière dont le contrôle « prometteur » est conçu pour identifier et éliminer les chemins non viables dès le début de la recherche.
|
