Algorithme de retour en arrière

Qu'est-ce que l'algorithme de rétroaction ?

Le backtracking est un algorithme qui recherche des combinaisons possibles pour résoudre problèmes de calcul. Elle construit progressivement des candidats et supprime ceux qui ne satisfont pas aux contraintes données. Cette technique est très utile dans les situations où vous devez choisir une solution réalisable parmi plusieurs résultats possibles.

Cet algorithme est considéré comme meilleur et plus efficace que l'approche Brute Force. Contrairement à Bruteforce, qui essaie toutes les solutions possibles, Backtracking se concentre sur la recherche d'une seule solution finale en fonction d'un ensemble de données. contraintes. Il permet également de gagner du temps et de la mémoire en annulant la dernière étape (retour en arrière) et en essayant une autre option après avoir atteint une impasse. De plus, il s'arrête dès qu'une solution valide est trouvée.

Le backtracking est une technique largement utilisée car elle permet de résoudre des problèmes complexes sans consommer de ressources exhaustives. Elle est particulièrement utile pour les problèmes où de nombreuses contraintes doivent être satisfaites, comme le Sudoku, le problème de la reine n et la planification. En naviguant intelligemment parmi les solutions potentielles, le backtracking peut trouver une réponse qui satisfait toutes les conditions. Cela le rend inestimable pour les tâches qui nécessitent à la fois précision et efficacité.

Comment fonctionne l'algorithme de rétroaction ?

Les algorithmes de rétro-suivi sont une technique de résolution de problèmes qui consiste à trouver des solutions valides étape par étape. Si les contraintes d'une étape ne satisfont pas certaines conditions, l'algorithme revient à l'étape précédente.

Il continue ensuite avec d'autres combinaisons possibles qui satisfont les contraintes données. Comme de nombreuses combinaisons possibles existent, il sélectionne l'une des options les plus satisfaisantes et résout le problème de manière séquentielle. Cette technique algorithmique est utile lorsque vous devez résoudre une ou plusieurs options possibles. Le retrait signifie annuler votre choix chaque fois qu'une situation se présente qui ne donne pas de solution valable.

L'algorithme de rétroaction comporte en général les étapes suivantes pour résoudre un problème :

Étape 1) Initialisation : Commencez avec une solution initiale vide/partielle.

Étape 2) Sélection:En fonction de critères et de contraintes spécifiques, sélectionnez une option pour étendre la solution actuelle.

Étape 3) Exploration:Résolvez de manière récursive en considérant le candidat choisi et en avançant dans le processus de résolution du problème.

Étape 4) Vérification des contraintes: Vérifiez si la solution partielle actuelle viole des contraintes à chaque étape. Si c'est le cas, revenez à l'étape précédente et essayez un autre candidat.

Étape 5) Résiliation:Le processus de retour en arrière s'arrête lorsqu'une solution valide est trouvée ou que toutes les combinaisons ont été épuisées.

Étape 6) Retour en arrière: Si l'option actuelle ne résout pas le problème donné, il revient à l'état précédent. Il considère alors la nouvelle option pour résoudre le problème donné.

Étape 7) Répétez:Continuez ces étapes jusqu’à ce que le problème soit résolu ou que toutes les options soient explorées.

Nature récursive de l'algorithme de rétro-suivi

Les algorithmes de rétro-suivi sont de nature récursive. Cela signifie que l'algorithme s'appelle lui-même avec différents paramètres jusqu'à ce qu'il trouve une solution ou ait testé toutes les possibilités :

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Termes courants liés aux problèmes de retour en arrière

Voici quelques termes de base liés à la technique du Backtracking :

Vecteur de solution : Représente les solutions sous forme de n-uplets, comme (X1, X2, …, Xn).
contraintes:Règles limitant les valeurs X, implicites et explicites.
Espace de solutions:Toutes les valeurs X valides satisfaisant des contraintes explicites.
Arbre d'espace d'état: Représente l'espace de solution sous forme d'arbre.
Territoire de l'État:Décrit les chemins dans un arbre d'espace d'état.
État du problème: Nœuds dans l'arbre de recherche représentant des solutions partielles.
États de solution:États formant des tuples de solutions valides dans S.
États de réponse:Satisfaire les contraintes implicites et produire les solutions souhaitées.
Nœud prometteur:Mène aux solutions souhaitées et reste réalisable.
Nœud non prometteur:Mène à des états irréalisables, non explorés plus avant.
Nœud en direct:Généré avec des enfants inexplorés.
Nœud électronique: Nœud actif avec génération d'enfants en cours.
Noeud mort:Aucune extension supplémentaire de tous les enfants générés.
Génération de nœuds en profondeur: Utilise le dernier nœud actif comme prochain nœud E.
Fonction de délimitation: Maximise ou minimise B(x1, x2, …, Xa) pour l'optimisation.
Arbres statiques:Formulation d'arbre indépendante de l'instance du problème.
Arbres dynamiques:La formulation de l'arbre varie en fonction de l'instance du problème.

Quand utiliser un algorithme de rétro-suivi ?

Nous pouvons choisir la technique du Backtracking pour résoudre un problème complexe lorsque :

De nombreux choix existent : Le retour en arrière est adapté si de nombreuses options existent à chaque étape du processus de résolution de problème. Ces options peuvent concerner la sélection d'éléments et les déplacements.
Pas de meilleur choix évident:Lorsqu'il n'y a pas suffisamment d'informations pour déterminer le meilleur choix parmi les options disponibles, un algorithme de rétro-suivi peut être utilisé.
La décision mène à plus de choix : Vous pouvez choisir le technique de retour en arrière pour revoir les choix de manière systématique.
Il faut explorer toutes les solutions possibles:Le backtracking explore systématiquement toutes les solutions en prenant une série de décisions construites les unes sur les autres.

Types de problèmes de retour en arrière

Il existe trois types de problèmes dans les algorithmes de rétro-suivi : les problèmes de décision, les problèmes d'optimisation et les problèmes d'énumération. Découvrons-les plus en détail ci-dessous.

Problème de décision : Dans ce type de problème, l'objectif est de déterminer si une solution réalisable existe. Nous vérifions les réponses « oui » et « non ». Par exemple, le problème des n reines. Il s'agit d'un problème de décision qui examine la probabilité de placer n reines sur un échiquier n × n sans qu'elles s'attaquent les unes aux autres.
Problème d'optimisation:Dans les problèmes d'optimisation, l'objectif est de trouver la meilleure solution possible parmi de nombreuses options. Cela peut impliquer de déterminer les valeurs maximales et minimales d'une certaine fonction ou variable. Par exemple, considérons le problème du sac à dos, où l'objectif est de maximiser la valeur totale des articles contenus dans le sac tout en respectant sa limite de poids.
Problème d'énumération: Son objectif est de trouver toutes les solutions possibles à un problème donné. Nous listons toutes les options valables sans aucune omission. Un exemple serait de générer toutes les combinaisons de lettres possibles à partir d'un ensemble de caractères donné.

Applications du backtracking et exemples

Il existe plusieurs applications du Backtracking. Certaines d'entre elles sont expliquées ci-dessous avec leur pseudo-code.

Sudoku Solver: Ce problème contient une sous-grille 3×3 avec des nombres en double. La technique de retour en arrière montrera que la solution renvoie faux, indiquant la nécessité d'un placement de nombre différent.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

Problème de la N-Reine:L’approche de retour en arrière détermine comment présenter les reines sur un échiquier N × N afin qu’aucune d’entre elles ne se menace.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

Problème de somme de sous-ensemble:Il est utilisé pour trouver le sous-ensemble de nombres d'un ensemble donné qui s'additionne pour atteindre une somme cible particulière.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

Problème du cycle hamiltonien:Le retour en arrière peut être appliqué pour trouver un tour fermé dans un graphique qui visite chaque sommet exactement une fois.
Problème de rat dans le labyrinthe:La technique du backtracking est utilisée pour trouver le chemin d'un rat depuis le point de départ du labyrinthe jusqu'à la sortie.

Avantages et inconvénients de l'algorithme de rétro-suivi

Avantages de l'algorithme de rétro-suivi

Les techniques de rétro-suivi sont utilisées pour résoudre des problèmes complexes. Elles présentent de nombreux avantages, notamment :

La technique du backtracking est efficace pour gérer les contraintes.
Cette méthode est bonne pour résoudre les problèmes d’optimisation.
La technique fonctionne pour différents types de problèmes.
Cette procédure peut aider à examiner toutes les solutions possibles.
Comme il revient en arrière, il économise plus de mémoire que la technique Bruteforce.

Inconvénients de l'algorithme de rétro-suivi

Les techniques de rétro-suivi présentent également certaines limites, notamment en termes de complexité temporelle. Cette technique présente les inconvénients suivants :

Il n’existe pas de solution garantie.
C'est plus lent à cause des nombreuses combinaisons.
Sa complexité temporelle est élevée en raison des nombreuses possibilités.
Il n’est pas adapté aux contraintes de temps réel car trouver la meilleure solution peut prendre beaucoup de temps.
L'efficacité dépend du niveau de complexité du problème.

Différence entre le backtracking et la récursivité

Récursivité	Revenant
S'appelle lui-même jusqu'à ce que le cas de base soit atteint.	Utilise la récursivité pour examiner toutes les possibilités jusqu'à ce que le meilleur résultat réalisable soit trouvé.
Une approche en profondeur.	Approche descendante.
Aucune valeur n'est rejetée.	Les solutions non viables sont rejetées.

Conclusion

Le backtracking est une stratégie algorithmique utile pour résoudre des problèmes complexes en explorant systématiquement les solutions réalisables et en effectuant un retour en arrière si nécessaire. Nous pouvons nous attendre à ce que les techniques de backtracking s'améliorent avec les améliorations de la puissance de calcul et de l'efficacité algorithmique. Ces avancées leur permettront de s'attaquer efficacement à des problèmes plus vastes et plus complexes.

De plus, les modèles d’apprentissage automatique peuvent guider les décisions de retour en arrière en fonction de modèles précédemment appris.

Toutes ces innovations technologiques vont révolutionner les algorithmes de backtracking, en faisant d’eux un outil puissant et polyvalent pour résoudre des problèmes complexes dans divers domaines.