|
Retour en arrière :une technique de résolution systématique des problèmes
Le backtracking est une technique algorithmique puissante utilisée pour résoudre des problèmes impliquant la recherche d’une solution parmi un grand nombre de possibilités. Il fonctionne en construisant progressivement des solutions candidates et en abandonnant (« retour en arrière ») un candidat dès qu'il détermine que le candidat ne peut pas conduire à une solution valable. Considérez-le comme une manière intelligente et structurée d’effectuer une recherche approfondie dans un arbre de décision.
Idées clés :
* Construction incrémentielle : Le retour en arrière construit des solutions étape par étape, en ajoutant une pièce à la fois.
* Élagage (satisfaction des contraintes) : A chaque étape, il vérifie si la solution partielle actuelle satisfait aux contraintes du problème. Si ce n’est pas le cas, il abandonne immédiatement cette voie et revient au point de décision précédent. Cette étape d’élagage réduit considérablement l’espace de recherche.
* Récursion (souvent) : Le retour en arrière est souvent mis en œuvre à l'aide de fonctions récursives, où chaque appel récursif représente un choix ou une étape dans le processus de création de solution.
* Arbre de décision : Vous pouvez visualiser le processus de recherche sous la forme d'un arbre de décision, dans lequel chaque nœud représente un état (solution partielle) et les bords représentent des choix ou des actions. Backtracking explore cet arbre d’une manière approfondie.
Comment ça marche (algorithme général) :
1. Commencez avec une solution vide (ou partiellement initialisée).
2. Faire un choix (explorer une branche) : Sélectionnez une valeur ou une action possible pour étendre la solution actuelle.
3. Vérifier la validité :
* Si la solution est valide (satisfait aux contraintes) :
* La solution est-elle complète ?
* Oui : Renvoyez la solution.
* Non : Appelez récursivement la fonction de retour en arrière pour faire un autre choix et continuer à créer la solution.
* Si la solution n'est pas valide (viole les contraintes) :
* Retour en arrière : Annulez le dernier choix et essayez-en un autre. Si tous les choix ont été essayés à ce niveau, revenez au niveau précédent.
4. Aucune solution : Si tous les choix possibles ont été épuisés sans trouver de solution valable, indiquez qu’aucune solution n’existe.
Analogie :résoudre un labyrinthe
Imaginez que vous résolvez un labyrinthe. Vous commencez à l'entrée et essayez différents chemins.
* Avancer : Vous faites un « choix » en empruntant un chemin.
* Bon chemin (valide) : Si le chemin semble mener vers la sortie, vous continuez.
* Impasse (invalide) : Si vous atteignez une impasse, vous « faites marche arrière » en revenant sur vos pas jusqu'à la dernière intersection (point de décision) et essayez un chemin différent.
* Résolu : Si vous atteignez la sortie, vous avez trouvé une solution.
Cas d'utilisation courants en programmation :
* Problèmes de satisfaction de contraintes (CSP) : Problèmes dont le but est de trouver un ensemble de valeurs pour des variables qui satisfont un ensemble de contraintes.
* Problème N-Queens : Placer N reines d'échecs sur un échiquier NxN afin qu'aucune reine ne se menace.
* Résolveur de Sudoku : Remplir une grille 9x9 avec des chiffres afin que chaque ligne, colonne et sous-grille 3x3 contienne tous les chiffres de 1 à 9.
* Coloration de la carte : Attribuer des couleurs aux régions d'une carte afin qu'aucune région adjacente n'ait la même couleur.
* Problèmes d'optimisation combinatoire : Trouver la meilleure solution parmi un large éventail de combinaisons possibles.
* Problème du vendeur itinérant (TSP) : Trouver l'itinéraire le plus court possible qui visite chaque ville d'une liste et revient à la ville de départ (le retour en arrière peut être utilisé pour les petites instances, mais d'autres algorithmes sont plus efficaces pour les instances plus grandes).
* Problème de sac à dos : Déterminer le sous-ensemble d’articles le plus précieux pouvant tenir dans un sac à dos avec une capacité de poids limitée.
* Problème de somme de sous-ensemble : Trouver un sous-ensemble d'un ensemble de nombres dont la somme correspond à une valeur cible donnée.
* Analyse syntaxique et syntaxique :
* Grammaires sans contexte : Le retour en arrière peut être utilisé dans les analyseurs pour essayer différentes dérivations d'une phrase jusqu'à ce qu'un arbre d'analyse valide soit trouvé.
Exemple :problème des N-Reines (simplifié)
Illustrons le problème N-Queens avec N=4 (un tableau 4x4).
```python
def is_safe (tableau, ligne, col) :
"""Vérifie si placer une reine au tableau[ligne][col] est sûr."""
# Vérifiez la même colonne
pour moi dans la plage (ligne):
si board[i][col] ==1 :
retourner Faux
# Vérifiez la diagonale supérieure gauche
pour i, j dans zip(range(row - 1, -1, -1), range(col - 1, -1, -1)) :
si board[i][j] ==1 :
retourner Faux
# Vérifiez la diagonale supérieure droite
pour i, j dans zip(range(row - 1, -1, -1), range(col + 1, 4)) :
si board[i][j] ==1 :
retourner Faux
retourner vrai
def solve_n_queens_util (tableau, ligne) :
"""Fonction d'assistance récursive pour résoudre le problème des N-Queens."""
si row ==4 :# Toutes les reines sont placées avec succès
retourner vrai
pour le col dans la plage (4) :
if is_safe(board, row, col) :
board[row][col] =1 # Placer la reine
if solve_n_queens_util(board, row + 1):# Placer récursivement la prochaine reine
retourner vrai
board[row][col] =0 # Backtrack :supprimez la reine si cela ne mène pas à une solution
return False # Aucune solution trouvée pour cette ligne
def solve_n_queens() :
"""Résout le problème des N-Reines pour N=4."""
board =[[0 for _ in range(4)] for _ in range(4)] # Initialiser un tableau vide
sinon solve_n_queens_util(board, 0) :
print("La solution n'existe pas")
retour
# Imprimer la solution
pour une rangée dans un tableau :
imprimer (ligne)
résoudre_n_queens()
```
Explication du Code :
1. `is_safe(board, row, col)` : Vérifie s'il est sûr de placer une reine à `board[row][col]`. Il vérifie les conflits dans les mêmes colonnes et diagonales.
2. `solve_n_queens_util(board, row)` :
* Cas de base : `if row ==4 :` Si nous avons atteint la dernière ligne (toutes les reines placées), nous avons une solution, alors retournez `True`.
* Itération : Parcourez chaque colonne de la ligne actuelle (« for col in range(4) »).
* Vérifier la sécurité : `if is_safe(board, row, col) :` S'il est sûr de placer une reine dans cette colonne :
* Placer la Reine : `board[ligne][col] =1`
* Appel récursif : `if solve_n_queens_util(board, row + 1) :` Essayez récursivement de placer la reine suivante dans la ligne suivante. Si cet appel récursif renvoie « True », cela signifie qu'une solution a été trouvée à partir de ce point, nous renvoyons donc également « True ».
* Retour en arrière : `board[row][col] =0` Si l'appel récursif renvoie `False` (aucune solution n'a été trouvée), nous *annulons* le placement de la reine (retour en arrière) et essayons la colonne suivante dans la ligne actuelle.
* Aucune solution dans cette ligne : `return False` Si nous avons essayé toutes les colonnes de la ligne actuelle sans trouver de solution, cela signifie qu'il n'y a pas de placement valide des reines, nous renvoyons donc `False`.
3. `solve_n_queens()` :
* Initialise la carte.
* Appelle `solve_n_queens_util` pour démarrer le processus de retour en arrière.
* Imprime la solution si elle est trouvée.
Avantages du retour en arrière :
* Recherche systématique : Garantie de trouver une solution si elle existe (recherche exhaustive).
* Taille : Évite d'explorer des branches inutiles de l'espace de recherche, ce qui le rend plus efficace qu'une approche par force brute.
* Simplicité conceptuelle : L’idée de base est relativement facile à comprendre.
Inconvénients du retour en arrière :
* Complexité temporelle : Peut toujours avoir une complexité temporelle élevée (exponentielle dans le pire des cas) pour les instances de problèmes importants, car cela peut explorer de nombreuses impasses.
* Complexité spatiale : Peut nécessiter une mémoire importante, notamment pour une récursion profonde.
Considérations clés pour l'application du backtracking :
* Contraintes : Définir clairement les contraintes du problème.
* Choix d'action : Réfléchissez attentivement à la manière de faire des choix à chaque étape.
* Stratégie d'élagage : Développez une stratégie d’élagage efficace pour éliminer les candidats invalides le plus tôt possible. Ceci est crucial pour la performance.
* Structure du problème : Le retour en arrière fonctionne mieux pour les problèmes dont la validité des solutions partielles peut être facilement évaluée.
En résumé, le backtracking est une technique polyvalente de résolution de problèmes qui peut être appliquée à un large éventail de problèmes. En explorant systématiquement les solutions possibles et en élaguant l’espace de recherche, il offre une approche puissante pour trouver des solutions qui satisfont à des contraintes spécifiques. Même si, dans le pire des cas, la complexité temporelle peut être élevée, une satisfaction minutieuse des contraintes et un élagage efficace peuvent améliorer considérablement ses performances.
|
