Quand est-il pratique d'utiliser la Recherche approfondie-première recherche (SSM) par opposition à la recherche étendue-première recherche (BFS)?

belle explication de http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

un exemple DE BFS

voici un exemple de ce à quoi ressemblerait un BFS. C'est quelque chose comme la traversée de L'arbre D'ordre de niveau où nous utiliserons la file D'attente avec une approche itérative (la plupart du temps la récursion finira avec DFS). Les nombres représentent l'ordre dans lequel les noeuds sont BFS:

dans une première recherche en profondeur, vous commencez à la racine, et suivez une des branches de l'arbre autant que possible jusqu'à ce que soit le noeud que vous recherchez est trouvé ou vous frappez un noeud de feuille ( un noeud sans enfants). Si vous touchez un noeud de feuille, alors vous continuez la recherche à l'ancêtre le plus proche avec des enfants inexplorés.

exemple de DFS

voici un exemple de ce à quoi ressemblerait un DFS. Je pense que le post-ordre transversal dans l'arbre binaire va commencer à travailler du niveau de la feuille d'abord. Les nombres représentent l'ordre dans lequel les noeuds sont accédés dans un DFS:

différences entre DFS et BFS

en comparant BFS et DFS, le grand avantage de DFS est qu'il a des besoins de mémoire beaucoup plus faibles que BFS, parce qu'il n'est pas nécessaire de stocker tous les pointeurs enfant à chaque niveau. Selon les données et ce que vous recherchez, la DSV ou la BFS pourraient être avantageuses.

par exemple, compte tenu d'un arbre généalogique, si l'on cherche quelqu'un sur l'arbre qui est encore en vie, on peut supposer que cette personne se trouve au pied de l'arbre. Cela signifie qu'un BFS prendrait beaucoup de temps pour atteindre ce dernier niveau. A DFS, cependant, trouver le but plus rapidement. Mais, si quelqu'un cherchait un membre de sa famille qui est mort il y a très longtemps, alors cette personne serait plus près du sommet de l'arbre. Ensuite, un BFS serait généralement plus rapide qu'un DFS. Ainsi, les avantages de varier en fonction des données et de ce que vous cherchez.

un autre exemple Est Facebook; Suggestion sur les amis des amis. Nous avons besoin d'amis immédiats pour la suggestion où nous pouvons utiliser BFS. Peut-être trouver le chemin le plus court ou détecter le cycle (en utilisant la récursion) nous pouvons utilisez DFS.

profondeur-première recherche

profondeur-premières recherches sont souvent utilisées dans des simulations de jeux (et des situations de jeu dans le monde réel). Dans un match, vous pouvez choisir parmi plusieurs actions possibles. Chaque choix conduit à d'autres choix, chacun d'eux débouchant sur d'autres choix, et ainsi de suite dans un graphique de possibilités en forme d'arbre en expansion constante.

par exemple dans les jeux comme les échecs, tic-tac-toe quand vous décidez ce mouvement à faire, vous pouvez imaginer mentalement un mouvement, puis les réponses possibles de votre adversaire, puis vos réponses, et ainsi de suite. Vous pouvez décider quoi faire en voyant qui se déplacent conduit au meilleur résultat.

seulement quelques chemins dans un arbre de jeu mènent à votre victoire. Certains d'entraîner une victoire par votre adversaire, lorsque vous arrivez à une telle fin, vous devez sauvegarder, ou revenir en arrière, à un nœud précédent et essayer un autre chemin. De cette façon, vous explorez l'arbre jusqu'à ce que vous trouver un chemin avec une conclusion réussie. Ensuite, vous faites le premier pas sur ce chemin.

Largeur-première recherche

la recherche de largeur-d'abord a une propriété intéressante: elle trouve d'abord tous les sommets qui sont un bord à partir du point de départ, puis tous les sommets qui sont deux bords à partir, et ainsi de suite. Ceci est utile si vous essayez de trouver le chemin le plus court depuis le sommet d'un vertex. Vous lancez un BFS, et quand vous trouvez le vertex spécifié, vous savez que le chemin que vous avez tracé jusqu'à présent est le chemin le plus court vers le noeud. S'il y avait un chemin plus court, le BFS l'aurait déjà trouvé.

largeur-la première recherche peut être utilisée pour trouver les noeuds voisins dans les réseaux de pair à pair comme BitTorrent, les systèmes GPS pour trouver des emplacements à proximité, les sites de réseaux sociaux pour trouver des personnes dans la distance spécifiée et des choses comme ça.

largeur la première recherche est généralement la meilleure approche lorsque la profondeur de l'arbre peut varier, et il suffit de chercher une partie de l'arbre pour trouver une solution. Par exemple, trouver le chemin le plus court entre une valeur de départ et une valeur finale est un bon endroit pour utiliser BFS.

profondeur la première recherche est couramment utilisée lorsque vous avez besoin de chercher dans l'arbre entier. Il est plus facile à mettre en œuvre (en utilisant la récursion) que BFS, et nécessite moins d'État: tandis que BFS exige que vous stockez l'ensemble de "frontière", DFS vous demande seulement de stocker la liste des nœuds parents de l'élément courant.

DFS est de plus d'espace en moins que la BFS, mais peut aller inutilement à des profondeurs.

leurs noms sont révélateurs: s'il y a une grande largeur (c'est-à-dire un grand facteur de ramification), mais une profondeur très limitée (c'est-à-dire un nombre limité de" mouvements"), alors la DFS peut être plus préférable à la BFS.

On IDDFS

il convient de mentionner qu'il ya une variante moins connue qui combine l'efficacité de l'espace de DFS, mais (cumulativement) l'ordre de niveau de la visite DE BFS, est le profondeur itérative d'approfondissement-première recherche . Cet algorithme revoit certains noeuds, mais il ne contribue qu'à un facteur constant de différence asymptotique.

un avantage important de BFS serait qu'il peut être utilisé pour trouver le chemin le plus court entre deux noeuds dans un graphe non pondéré. Alors que, nous ne pouvons pas utiliser DFS pour le même .

lorsque vous abordez cette question en tant que programmeur, un facteur ressort: si vous utilisez la récursion, alors la recherche en profondeur est plus simple à mettre en œuvre, parce que vous n'avez pas besoin de maintenir une structure de données supplémentaire contenant les noeuds encore à explorer.

voici la profondeur-première recherche d'un graphique non orienté si vous stockez des informations "déjà visitées" dans les noeuds:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

si stockant" déjà visité" de l'information dans une structure de données distincte:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(origin, set())

comparez ceci avec la largeur-première recherche où vous devez maintenir une structure de données séparée pour la liste des noeuds encore à visiter, peu importe quoi.

pour BFS, nous pouvons considérer L'exemple de Facebook. Nous recevons la suggestion d'ajouter des amis du profil fb d'autres amis du profil. Supposons A- > B, alors que B - > E et B->F, donc a aura des suggestions pour E et F. Ils doivent utiliser BFS pour lire jusqu'au deuxième niveau. La DSV est davantage basée sur des scénarios où nous voulons prévoir quelque chose à partir des données que nous avons de la source à la destination. Comme déjà mentionné sur les échecs ou sudoku. Une fois que j'ai une chose différente ici est, je crois que DFS devrait être utilisé pour le chemin le plus court parce que DFS couvrira tout le chemin d'abord puis nous pouvons décider du meilleur. Mais comme BFS va utiliser l'approche de greedy donc pourrait être il ressemble à son chemin le plus court, mais le résultat final pourrait différer. Dites-moi si ma compréhension est erronée.

certains algorithmes dépendent des propriétés particulières de DFS (ou BFS) pour fonctionner. Par exemple, L'algorithme de Hopcroft et Tarjan pour trouver les composants connectés en 2 profite du fait que chaque noeud déjà visité rencontré par DFS est sur le chemin de la racine au noeud actuellement exploré.

selon les propriétés de DFS et BFS. Par exemple,lorsque nous voulons trouver le chemin le plus court. nous utilisons généralement bfs, il peut garantir le "plus court". mais dfs seul peut garantir que nous pouvons venir de ce point peut atteindre ce point ,ne peut pas garantir le "plus court".

parce que les recherches en profondeur utilisent D'abord une pile au fur et à mesure que les noeuds sont traités, le retraçage est fourni avec DFS. Étant donné que les recherches en largeur D'abord utilisent une file d'attente, et non une pile, pour garder la trace des noeuds qui sont traités, le retracage n'est pas fourni avec BFS.

lorsque la largeur de l'arbre est très grande et que la profondeur est faible, utiliser DFS car la pile de récursions ne débordera pas.Utilisez BFS lorsque la largeur est faible et la profondeur très grande pour traverser l'arbre.

ceci est un bon exemple pour démontrer que BFS est meilleur que DFS dans certains cas. https://leetcode.com/problems/01-matrix /

lorsqu'elles sont correctement mises en œuvre, les deux solutions devraient visiter les cellules qui ont une plus grande distance que la cellule actuelle +1. Mais la DSV est inefficace et a visité à plusieurs reprises la même cellule résultant o(n*n) complexité.

par exemple,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,

cela dépend de la situation dans laquelle il est utilisé. Chaque fois que nous avons un problème de traverser un graphe, nous le faisons dans un certain but. Quand il y a un problème de trouver le chemin le plus court dans un graphe non pondéré, ou de trouver si un graphe est bipartite, nous pouvons utiliser BFS. Pour les problèmes de détection de cycle ou toute logique nécessitant un retour en arrière, nous pouvons utiliser DFS.

cette question est un peu vieille, mais un bon exemple est du jeu vidéo moderne"Bit Heroes". Dans un donjon patron typique, votre but est de vaincre le patron, après quoi vous avez la possibilité de quitter ce donjon particulier ou de continuer à l'Explorer pour le butin. Mais en général, les patrons sont loin de ton point de départ. Le jeu offre un donjon automatique-traversal caractéristique qui essentiellement prend votre personnage à travers le donjon, de rencontrer des ennemis comme il va. Ceci est mis en œuvre avec un algorithme de recherche en profondeur, car le but est d'aller aussi profondément dans le donjon que possible avant de retracer.