GeeksforGeeks

Prérequis :

• Récursivité
• Analyse de complexité

Le retour en arrière est une technique algorithmique permettant de résoudre des problèmes de manière récursive en essayant de construire une solution de manière incrémentielle, une pièce à la fois, en supprimant les solutions qui ne satisfont pas les contraintes du problème à tout moment (par temps, ici, on fait référence au temps écoulé jusqu’à atteindre n’importe quel niveau de l’arbre de recherche).

Selon la définition du wiki,

Le retour en arrière peut être défini comme une technique algorithmique générale qui considère la recherche de toutes les combinaisons possibles afin de résoudre un problème de calcul.

Il existe trois types de problèmes de retour en arrière –

1. Problème de décision – En cela, nous recherchons une solution réalisable.
2. Problème d’optimisation – En cela, nous recherchons la meilleure solution.
3. Problème d’énumération – En cela, nous trouvons toutes les solutions possibles.

Comment déterminer si un problème peut être résolu en utilisant le retour en arrière?

Généralement, tout problème de satisfaction de contraintes qui a des contraintes claires et bien définies sur toute solution objective, qui construit progressivement un candidat à la solution et abandonne un candidat (« backtracks ») dès qu’il détermine que le candidat ne peut pas éventuellement être complété à une solution valide, peut être résolu par un retour en arrière. Cependant, la plupart des problèmes discutés peuvent être résolus en utilisant d’autres algorithmes connus comme la Programmation dynamique ou des Algorithmes Gourmands en complexité temporelle logarithmique, linéaire, linéaire-logarithmique par ordre de taille d’entrée, et donc surpasser l’algorithme de retour en arrière à tous égards (puisque les algorithmes de retour en arrière sont généralement exponentiels dans le temps et l’espace). Cependant, il reste encore quelques problèmes, qui n’ont jusqu’à présent que des algorithmes de retour en arrière pour les résoudre.

Considérez une situation où vous avez trois boîtes devant vous et qu’une seule d’entre elles contient une pièce d’or mais vous ne savez pas laquelle. Donc, pour obtenir la pièce, vous devrez ouvrir toutes les boîtes une par une. Vous allez d’abord cocher la première case, si elle ne contient pas la pièce, vous devrez la fermer et cocher la deuxième case et ainsi de suite jusqu’à ce que vous trouviez la pièce. C’est ce qu’est le retour en arrière, c’est-à-dire résoudre tous les sous-problèmes un par un afin d’atteindre la meilleure solution possible.

Considérons l’exemple ci-dessous pour comprendre plus formellement l’approche de retour en arrière,

Étant donné une instance de tout problème de calcul et des données correspondant à l’instance, toutes les contraintes qui doivent être satisfaites pour résoudre le problème sont représentées par . Un algorithme de retour en arrière fonctionnera alors comme suit :

L’algorithme commence à construire une solution, en commençant par un ensemble de solutions vides . L = {}

1. Ajoutez à le premier coup qui reste (Tous les mouvements possibles sont ajoutés à un par un). Cela crée maintenant une nouvelle sous-arborescence dans l’arborescence de recherche de l’algorithme.
2. Vérifiez si satisfait à chacune des contraintes de .
   • Si oui, alors la sous-arborescence est « éligible » pour ajouter d’autres « enfants ».
   • Sinon, le sous-arbre entier est inutile, donc revient à l’étape 1 en utilisant l’argument .
3. En cas d' »éligibilité » du sous-arbre nouvellement formé , revient à l’étape 1, en utilisant l’argument .
4. Si la vérification de renvoie qu’il s’agit d’une solution pour l’ensemble des données . Sortie et terminez le programme.
   Sinon, retournez qu’aucune solution n’est possible avec le courant et jetez-le donc.

Différence entre Récursivité et retour en arrière:

En récursivité, la fonction s’appelle jusqu’à ce qu’elle atteigne un cas de base. En retour en arrière, nous utilisons la récursivité pour explorer toutes les possibilités jusqu’à ce que nous obtenions le meilleur résultat pour le problème.

Pseudo Code pour le retour en arrière :

1. Solution de retour en arrière récursif.

void findSolutions(n, other params) : if (found a solution) : solutionsFound = solutionsFound + 1; displaySolution(); if (solutionsFound >= solutionTarget) : System.exit(0); return for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); findSolutions(n+1, other params); removeValue(val, n);

2. Trouver si une solution existe ou non

boolean findSolutions(n, other params) : if (found a solution) : displaySolution(); return true; for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); if (findSolutions(n+1, other params)) return true; removeValue(val, n); return false;

Essayons de résoudre un problème de retour en arrière standard, le problème N-Queen.
La N Reine est le problème de placer N reines d’échecs sur un échiquier N×N de sorte qu’aucune reine ne s’attaque l’une à l’autre. Par exemple, voici une solution pour le problème de la reine 4.

La sortie attendue est une matrice binaire qui a 1s pour les blocs où les reines sont placées. Par exemple, voici la matrice de sortie pour la solution 4 reine ci-dessus.

{ 0, 1, 0, 0}{ 0, 0, 0, 1}{ 1, 0, 0, 0}{ 0, 0, 1, 0}

Algorithme de retour en arrière: L’idée est de placer les reines une par une dans différentes colonnes, en commençant par la colonne la plus à gauche. Lorsque nous plaçons une reine dans une colonne, nous vérifions les affrontements avec des reines déjà placées. Dans la colonne actuelle, si nous trouvons une ligne pour laquelle il n’y a pas de conflit, nous marquons cette ligne et cette colonne comme faisant partie de la solution. Si nous ne trouvons pas une telle ligne en raison d’affrontements, nous faisons marche arrière et renvoyons false.

1) Start in the leftmost column2) If all queens are placed return true3) Try all rows in the current column. Do following for every tried row. a) If the queen can be placed safely in this row then mark this as part of the solution and recursively check if placing queen here leads to a solution. b) If placing the queen in leads to a solution then return true. c) If placing queen doesn't lead to a solution then unmark this (Backtrack) and go to step (a) to try other rows.3) If all rows have been tried and nothing worked, return false to trigger backtracking.

Vous pouvez vous référer à l’article sur le retour en arrière | Set 3 (problème de reine N) pour la mise en œuvre complète de l’approche ci-dessus.
Plus de Problèmes de Retour en arrière:

• Backtracking / Set 1 (Problème de la tournée du Chevalier)
• Backtracking /Set 2 (Rat dans un labyrinthe)
• Backtracking /Set 4 (Somme du sous-ensemble)
• Backtracking /Set 5 (Problème de coloration m)
• –> Cliquez ici pour plus