Dans ce didacticiel, vous apprendrez ce qu'est un algorithme de retour arrière. Vous trouverez également un exemple d'approche de retour en arrière.
Un algorithme de retour en arrière est un algorithme de résolution de problèmes qui utilise une approche de force brute pour trouver la sortie souhaitée.
L'approche de la force brute essaie toutes les solutions possibles et choisit les solutions souhaitées / les meilleures.
Le terme retour en arrière suggère que si la solution actuelle ne convient pas, revenez en arrière et essayez d'autres solutions. Ainsi, la récursivité est utilisée dans cette approche.
Cette approche est utilisée pour résoudre des problèmes qui ont plusieurs solutions. Si vous voulez une solution optimale, vous devez opter pour une programmation dynamique.
Arbre de l'espace d'état
Un arbre d'états d'espace est un arbre représentant tous les états possibles (solution ou non) du problème de la racine comme état initial à la feuille comme état terminal.
Arbre de l'espace d'état
Algorithme de retour en arrière
Backtrack (x) si x n'est pas une solution retourne false si x est une nouvelle solution ajouter à la liste des solutions backtrack (développer x)
Exemple d'approche de retour en arrière
Problème: Vous voulez trouver toutes les manières possibles de disposer 2 garçons et 1 fille sur 3 bancs. Contrainte: la fille ne doit pas être sur le banc du milieu.
Solution: il y en a 3 au total! = 6 possibilités. Nous allons essayer toutes les possibilités et trouver les solutions possibles. Nous essayons récursivement toutes les possibilités.
Toutes les possibilités sont:
Toutes les possibilités
L'arborescence de l'espace d'états suivante montre les solutions possibles.
Arbre d'état avec toutes les solutions
Applications d'algorithme de retour en arrière
- Pour trouver tous les chemins hamiltoniens présents dans un graphique.
- Pour résoudre le problème de N Queen.
- Problème de résolution de labyrinthe.
- Le problème de la tournée du chevalier.
