Quelle est la différence entre le retour en arrière et la première recherche en profondeur?

Quelle est la différence entre le retour en arrière et la première recherche en profondeur?

Le backtracking est un algorithme plus général.

La recherche en profondeur d'abord est une forme spécifique de retour arrière liée à la recherche de structures arborescentes. De Wikipedia:

On commence à la racine (en sélectionnant un nœud comme racine dans le cas du graphe) et on explore autant que possible le long de chaque branche avant de revenir en arrière.

Il utilise le retour en arrière dans le cadre de ses moyens de travailler avec un arbre, mais est limité à une structure arborescente.

Le retour en arrière, cependant, peut être utilisé sur n'importe quel type de structure où des parties du domaine peuvent être éliminées - qu'il s'agisse ou non d'un arbre logique. L'exemple Wiki utilise un échiquier et un problème spécifique - vous pouvez regarder un mouvement spécifique et l'éliminer, puis revenir au prochain mouvement possible, l'éliminer, etc.

Je pense que cette réponse à une autre question connexe offre plus d'informations.

Pour moi, la différence entre le retour arrière et DFS est que le retour arrière gère une arborescence implicite et DFS traite une arborescence explicite. Cela semble trivial, mais cela signifie beaucoup. Lorsque l'espace de recherche d'un problème est visité par retour arrière, l'arbre implicite est parcouru et élagué au milieu de celui-ci. Pourtant, pour DFS, l'arbre / graphe qu'il traite est explicitement construit et les cas inacceptables ont déjà été rejetés, c'est-à-dire élagués, avant toute recherche.

Ainsi, le retour arrière est DFS pour l'arborescence implicite, tandis que DFS effectue le retour arrière sans élagage.

Le retour en arrière est généralement implémenté en tant que DFS plus l'élagage de la recherche. Vous parcourez en profondeur l'arborescence de l'espace de recherche en construisant d'abord des solutions partielles en cours de route. Brute-force DFS peut construire tous les résultats de recherche, même ceux qui n'ont pratiquement aucun sens. Cela peut également être très inefficace pour construire toutes les solutions (n! Ou 2 ^ n). Donc, en réalité, comme vous le faites avec DFS, vous devez également élaguer les solutions partielles, qui n'ont pas de sens dans le contexte de la tâche réelle, et vous concentrer sur les solutions partielles, ce qui peut conduire à des solutions optimales valides. Il s'agit de la technique de retour en arrière - vous rejetez les solutions partielles le plus tôt possible, faites un pas en arrière et essayez de trouver à nouveau l'optimum local.

Rien ne s'arrête pour traverser l'arborescence de l'espace de recherche à l'aide de BFS et exécuter une stratégie de retour en arrière en cours de route, mais cela n'a pas de sens en pratique car vous auriez besoin de stocker l'état de recherche couche par couche dans la file d'attente, et la largeur de l'arbre augmente de manière exponentielle jusqu'à la hauteur, nous gaspillerions donc beaucoup d'espace très rapidement. C'est pourquoi les arbres sont généralement parcourus à l'aide de DFS. Dans ce cas, l'état de recherche est stocké dans la pile (pile d'appels ou structure explicite) et il ne peut pas dépasser la hauteur de l'arbre.

Selon Donald Knuth, c'est la même chose. Voici le lien sur son article sur l'algorithme Dancing Links, qui est utilisé pour résoudre des problèmes "non-arborescents" tels que les N-reines et le solveur Sudoku.

Backtracking, également appelé recherche en profondeur d'abord

Habituellement, une recherche en profondeur est un moyen d'itérer dans une structure graphique / arborescente réelle à la recherche d'une valeur, tandis que le retour en arrière consiste à parcourir un espace de problème à la recherche d'une solution. Le backtracking est un algorithme plus général qui ne concerne même pas nécessairement les arbres.

Je dirais que DFS est la forme spéciale de retour en arrière; le retour en arrière est la forme générale de DFS.

Si nous étendons DFS à des problèmes généraux, nous pouvons l'appeler retour arrière. Si nous utilisons le retour en arrière vers des problèmes liés aux arbres / graphiques, nous pouvons l'appeler DFS.

Ils portent la même idée sous l'aspect algorithmique.

À mon humble avis, la plupart des réponses sont soit largement imprécises et / ou sans aucune référence à vérifier. Permettez-moi donc de partager une explication très claire avec une référence .

Premièrement, DFS est un algorithme général de traversée (et de recherche) de graphe. Ainsi, il peut être appliqué à n'importe quel graphe (ou même forêt). Tree est un type spécial de graphique, donc DFS fonctionne également pour l'arbre. Essentiellement, arrêtons de dire que cela ne fonctionne que pour un arbre, ou les goûts.

Basé sur [1], Backtracking est un type spécial de DFS utilisé principalement pour économiser de l'espace (mémoire). La distinction que je suis sur le point de mentionner peut sembler déroutante car dans les algorithmes Graph de ce type, nous sommes tellement habitués à avoir des représentations de liste de contiguïté et à utiliser un modèle itératif pour visiter tous les voisins immédiats ( pour tree, ce sont les enfants immédiats ) d'un nœud , nous ignorons souvent qu'une mauvaise implémentation de get_all_immediate_neighbors peut entraîner une différence dans l'utilisation de la mémoire de l'algorithme sous-jacent.

De plus, si un nœud de graphe a un facteur de branchement b et un diamètre h ( pour un arbre, c'est la hauteur de l'arbre ), si nous stockons tous les voisins immédiats à chaque étape de la visite d'un nœud, les besoins en mémoire seront big-O (bh) . Cependant, si nous ne prenons qu'un seul voisin (immédiat) à la fois et que nous l'étendons, la complexité de la mémoire se réduit à big-O (h) . Alors que le premier type d'implémentation est appelé DFS , le dernier type est appelé Backtracking .

Maintenant, vous voyez, si vous travaillez avec des langages de haut niveau, vous utilisez probablement le Backtracking sous le couvert de DFS. De plus, garder une trace des nœuds visités pour un très grand ensemble de problèmes pourrait être très gourmand en mémoire; appelant à une conception soignée de get_all_immediate_neighbors (ou des algorithmes qui peuvent gérer la revisitation d'un nœud sans entrer dans une boucle infinie).

[1] Stuart Russell et Peter Norvig, Intelligence artificielle: une approche moderne, 3e éd.

Depth first est un algorithme pour parcourir ou rechercher un arbre. Regardez ici . Le retour en arrière est un terme beaucoup plus large qui est utilisé chaque fois qu'un candidat à la solution est formé et ensuite rejeté par retour à un état antérieur. Regardez ici . La première recherche en profondeur utilise le retour en arrière pour rechercher d'abord une branche (solution candidate) et en cas d'échec, rechercher dans l'autre ou les autres branches.

OMI, sur n'importe quel nœud spécifique du retour en arrière, vous essayez d'abord de vous ramifier en profondeur dans chacun de ses enfants, mais avant de vous connecter à l'un des nœuds enfants, vous devez "effacer" l'état de l'enfant précédent (cette étape est équivalente à back marcher jusqu'au nœud parent). En d'autres termes, chaque état des frères et sœurs ne devrait pas avoir d'impact l'un sur l'autre.

Au contraire, pendant l'algorithme DFS normal, vous n'avez généralement pas cette contrainte, vous n'avez pas besoin d'effacer (retour arrière) l'état précédent des frères et sœurs pour construire le nœud frère suivant.

DFS décrit la manière dont vous souhaitez explorer ou parcourir un graphique. Il se concentre sur le concept d'aller le plus loin possible compte tenu du choix.

Le backtracking, bien que généralement implémenté via DFS, se concentre davantage sur le concept d'élagage des sous-espaces de recherche peu prometteurs le plus tôt possible.

Dans une recherche en profondeur d'abord , vous commencez à la racine de l'arbre, puis explorez aussi loin le long de chaque branche, puis vous revenez à chaque nœud parent suivant et parcourez ses enfants.

Le backtracking est un terme généralisé pour commencer à la fin d'un objectif et revenir progressivement en arrière, pour construire progressivement une solution.

Idée - Commencez à partir de n'importe quel point, vérifiez si c'est le point final souhaité, si oui, nous avons trouvé une autre solution pour toutes les prochaines positions possibles et si nous ne pouvons pas aller plus loin, revenez à la position précédente et recherchez d'autres alternatives marquant ce courant chemin ne nous mènera pas à la solution.

Maintenant, le retour en arrière et DFS sont 2 noms différents donnés à la même idée appliquée sur 2 types de données abstraites différents.

Si l'idée est appliquée à la structure de données matricielles, nous l'appelons retour arrière.

Si la même idée est appliquée sur un arbre ou un graphe, nous l'appelons DFS.

Le cliché ici est qu'une matrice pourrait être convertie en un graphique et un graphique pourrait être transformé en une matrice. Donc, nous appliquons réellement l'idée. Si sur un graphe, nous l'appelons DFS et si sur une matrice, nous l'appelons retour arrière.

L'idée dans les deux algorithmes est la même.

Le backtracking n'est qu'une première recherche en profondeur avec des conditions de terminaison spécifiques.

Pensez à vous promener dans un labyrinthe où pour chaque étape vous prenez une décision, cette décision est un appel à la pile d'appels (qui effectue votre première recherche en profondeur) ... si vous atteignez la fin, vous pouvez retourner votre chemin. Cependant, si vous atteignez une impasse, vous souhaitez revenir sur une certaine décision, essentiellement en sortant d'une fonction de votre pile d'appels.

Alors quand je pense au retour en arrière, je me soucie

1. Etat
2. Les décisions
3. Cas de base (conditions de résiliation)

Je l'explique dans ma vidéo sur le retour en arrière ici .

Une analyse du code de retour arrière est présentée ci-dessous. Dans ce code de retour en arrière, je veux toutes les combinaisons qui aboutiront à une certaine somme ou objectif. Par conséquent, j'ai 3 décisions qui font des appels à ma pile d'appels, à chaque décision, je peux soit choisir un numéro dans le cadre de mon chemin pour atteindre le numéro cible, sauter ce numéro, soit le choisir et le reprendre. Et puis si j'atteins une condition de résiliation, mon pas de retour en arrière est juste de revenir . Le retour est l'étape de retour arrière car il sort de cet appel sur la pile d'appels.

class Solution:    

"""

Approach: Backtracking 

State
    -candidates 
    -index 
    -target 

Decisions
    -pick one --> call func changing state: index + 1, target - candidates[index], path + [candidates[index]]
    -pick one again --> call func changing state: index, target - candidates[index], path + [candidates[index]]
    -skip one --> call func changing state: index + 1, target, path

Base Cases (Termination Conditions)
    -if target == 0 and path not in ret
        append path to ret
    -if target < 0: 
        return # backtrack 

"""

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    """
    @desc find all unique combos summing to target
    @args
        @arg1 candidates, list of ints
        @arg2 target, an int
    @ret ret, list of lists 
    """
    if not candidates or min(candidates) > target: return []

    ret = []
    self.dfs(candidates, 0, target, [], ret)
    return ret 

def dfs(self, nums, index, target, path, ret):
    if target == 0 and path not in ret: 
        ret.append(path)
        return #backtracking 
    elif target < 0 or index >= len(nums): 
        return #backtracking 


    # for i in range(index, len(nums)): 
    #     self.dfs(nums, i, target-nums[i], path+[nums[i]], ret)

    pick_one = self.dfs(nums, index + 1, target - nums[index], path + [nums[index]], ret)
    pick_one_again = self.dfs(nums, index, target - nums[index], path + [nums[index]], ret)
    skip_one = self.dfs(nums, index + 1, target, path, ret)