Quand est-il pratique d’utiliser DFS (Depth-First Search) vs BFS (Breadth First Search)?

Je comprends les différences entre DFS et BFS, mais je suis intéressé de savoir quand il est plus pratique d’utiliser l’un sur l’autre?

Quelqu’un pourrait-il donner des exemples de la façon dont DFS l’emporterait sur BFS et vice versa?

Cela dépend fortement de la structure de l’arbre de recherche et du nombre et de l’emplacement des solutions (éléments recherchés).

  • Si vous savez qu’une solution n’est pas loin de la racine de l’arborescence, une première recherche en largeur (BFS) pourrait être préférable.
  • Si l’arborescence est très profonde et que les solutions sont rares, la première recherche en profondeur peut prendre beaucoup de temps, mais le BFS peut être plus rapide.

  • Si l’arborescence est très large, un BFS peut nécessiter trop de mémoire.

  • Si les solutions sont fréquentes mais situées au plus profond de l’arbre, BFS pourrait ne pas être pratique.

  • Si l’arbre de recherche est très profond, vous devrez de toute façon limiter la profondeur de recherche pour la recherche en profondeur (DFS), par exemple avec un approfondissement itératif.

Mais ce ne sont que des règles de base; vous aurez probablement besoin d’expérimenter.

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 comme quelque chose comme Level Order Tree Traversal où nous allons utiliser QUEUE avec une approche ITERATIVE (la plupart du temps, RECURSION se retrouvera avec DFS). Les nombres représentent l’ordre dans lequel les nœuds sont accessibles dans un BFS:

entrer la description de l'image ici

Dans une première recherche en profondeur, vous commencez à la racine et suivez l’une des twigs de l’arborescence autant que possible jusqu’à ce que vous trouviez le nœud que vous recherchez ou que vous frappiez un nœud feuille (un nœud sans enfants). Si vous touchez un nœud feuille, vous continuez la recherche sur l’ancêtre le plus proche avec des enfants inexplorés.

Un exemple de DFS

Voici un exemple de ce à quoi ressemblerait un DFS. Je pense que la traversée de l’ordre postérieur dans l’arbre binary démarrera tout d’abord à partir du niveau Feuille. Les nombres représentent l’ordre dans lequel les nœuds sont accessibles dans un DFS:

entrer la description de l'image ici

Différences entre DFS et BFS

En comparant BFS et DFS, le gros avantage de DFS est qu’il nécessite beaucoup moins de mémoire que BFS, car il n’est pas nécessaire de stocker tous les pointeurs enfants à chaque niveau. Selon les données et ce que vous recherchez, DFS ou BFS peuvent être avantageux.

Par exemple, si on cherchait quelqu’un sur l’arbre qui est encore en vie dans un arbre généalogique, on pourrait supposer que cette personne serait au fond de l’arbre. Cela signifie qu’un BFS prend beaucoup de temps pour atteindre ce dernier niveau. Un DFS, cependant, trouverait l’objective plus rapidement. Mais si l’on cherchait un membre de sa famille décédé il y a très longtemps, cette personne serait alors plus proche du sumt de l’arbre. Ensuite, un BFS serait généralement plus rapide qu’un DFS. Ainsi, les avantages de chacun varient en fonction des données et de ce que vous recherchez.

Un autre exemple est Facebook; Suggestion sur les amis des amis. Nous avons besoin d’amis immédiats pour suggérer où nous pouvons utiliser BFS. Peut-être trouver le plus court chemin ou détecter le cycle (en utilisant la récursivité), nous pouvons utiliser DFS.

Profondeur première recherche

Les premières recherches sont souvent utilisées dans les simulations de jeux (et les situations de jeu dans le monde réel). Dans un jeu typique, vous pouvez choisir parmi plusieurs actions possibles. Chaque choix conduit à d’autres choix, chacun d’entre eux conduisant à de nouveaux choix, et ainsi de suite, dans un graphique de possibilités en forme d’arbre qui ne cesse de s’étendre.

entrer la description de l'image ici

Par exemple, dans les jeux comme les échecs, tic-tac-toe quand vous décidez de ce que vous voulez faire, vous pouvez imaginer mentalement un coup, puis les réponses possibles de votre adversaire, puis vos réponses, etc. Vous pouvez décider quoi faire en voyant quel mouvement mène au meilleur résultat.

Seuls quelques chemins dans un arbre de jeu mènent à votre victoire. Certains mènent à une victoire de votre adversaire, lorsque vous atteignez une telle fin, vous devez sauvegarder ou revenir en arrière sur un nœud précédent et essayer un chemin différent. De cette façon, vous explorez l’arbre jusqu’à ce que vous trouviez un chemin avec une conclusion réussie. Ensuite, vous faites le premier pas le long de ce chemin.


Recherche en largeur

La recherche en largeur a une propriété intéressante: elle commence par trouver tous les sumts situés à une extrémité du sharepoint départ, puis tous les sumts situés à deux bords, etc. Ceci est utile si vous essayez de trouver le plus court chemin du sumt de départ à un sumt donné. Vous démarrez un BFS, et lorsque vous trouvez le sumt spécifié, vous savez que le chemin que vous avez tracé jusqu’à présent est le plus court chemin vers le noeud. S’il y avait un chemin plus court, le BFS l’aurait déjà trouvé.

La recherche en largeur peut être utilisée pour trouver les nœuds voisins dans les réseaux peer-to-peer tels que BitTorrent, les systèmes GPS pour trouver les emplacements à proximité, les sites de réseaux sociaux pour trouver des personnes à la distance spécifiée et des choses comme ça.

Bread First First Search est généralement la meilleure approche lorsque la profondeur de l’arborescence peut varier, et que vous n’avez besoin que de rechercher une partie de l’arborescence pour trouver une solution. Par exemple, trouver le chemin le plus court d’une valeur initiale à une valeur finale est un bon endroit pour utiliser BFS.

Depth First Search est généralement utilisé lorsque vous devez rechercher l’arbre entier. Il est plus facile à mettre en œuvre (en utilisant la récursivité) que BFS, et nécessite moins d’état: Bien que BFS exige que vous stockiez la «frontière» entière, DFS vous oblige à stocker uniquement la liste des nœuds parents de l’élément actuel.

DFS est plus efficace en termes d’espace que BFS, mais peut atteindre des profondeurs inutiles.

Leurs noms sont révélateurs: s’il y a une grande ampleur (c.-à-d. Un facteur de twigment important), mais une profondeur très limitée (par exemple un nombre limité de «mouvements»), alors DFS peut être plus préférable à BFS.


Sur IDDFS

Il convient de mentionner qu’il existe une variante moins connue qui combine l’efficacité de l’espace de DFS, mais (cummul) la visite de niveau de BFS, est la recherche itérative de profondeur en premier . Cet algorithme revisite certains nœuds, mais ne consortingbue qu’à un facteur constant de différence asymptotique.

Un avantage important de BFS est qu’il peut être utilisé pour trouver le plus court chemin entre deux nœuds quelconques dans un graphique non pondéré. Alors que nous ne pouvons pas utiliser DFS pour le même .

Lorsque vous abordez cette question en tant que programmeur, l’un des facteurs est le suivant: si vous utilisez la récursivité, la recherche en profondeur est plus simple à mettre en œuvre, car vous n’avez pas besoin de conserver une structure de données supplémentaire à explorer.

Voici la recherche en profondeur d’abord d’un graphique non orienté si vous stockez des informations «déjà visitées» dans les nœuds:

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 vous stockez des informations «déjà visitées» 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 cela avec une recherche complète lorsque vous devez maintenir une structure de données distincte pour la liste des nœuds à visiter, peu importe quoi.

Pour BFS, nous pouvons prendre l’exemple de Facebook. Nous recevons des suggestions pour append des amis du profil FB d’autres profils d’amis. Supposons que A-> B, alors que B-> E et B-> F, donc A obtiendra une suggestion pour E et F. Ils doivent utiliser BFS pour lire jusqu’au deuxième niveau. DFS est plus basé sur des scénarios où nous voulons prévoir quelque chose en fonction des données que nous avons de la source à la destination. Comme déjà mentionné à propos des échecs ou du sudoku. Une fois la chose différente, je pense que DFS devrait être utilisé pour le chemin le plus court, car DFS couvrira tout le chemin en premier, puis nous pourrons décider du meilleur. Mais comme BFS utilisera l’approche de greedy, il se peut que ce soit le chemin le plus court, mais le résultat final pourrait être différent. Faites-moi savoir si ma compréhension est fausse.

Certains algorithmes dépendent de propriétés particulières de DFS (ou BFS) pour fonctionner. Par exemple, l’algorithme de Hopcroft et Tarjan pour trouver des composants à 2 connexions tire parti du fait que chaque noeud déjà visité rencontré par DFS se trouve sur le chemin allant du noeud 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 habituellement bfs, cela peut garantir le «plus court». mais DFS seulement peut garantir que nous pouvons venir de ce point peut atteindre ce point, ne peut pas garantir le «plus court».

Dans la mesure où les recherches de profondeur-utilisation utilisent une stack lorsque les nœuds sont traités, le retour en arrière est fourni avec DFS. Étant donné que les recherches portant sur l’ampleur utilisent une queue, et non une stack, pour garder une trace des nœuds traités, BFS ne fournit pas de retour en arrière.

Lorsque la largeur de l’arborescence est très grande et que la profondeur est faible, utilisez DFS car la stack de récursivité ne débordera pas. Utilisez BFS lorsque la largeur est faible et que la profondeur est très grande pour traverser l’arborescence.

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

Lorsqu’elles sont correctement implémentées, les deux solutions doivent visiter les cellules plus éloignées de la cellule actuelle +1. Mais DFS est inefficace et a visité à plusieurs resockets la même cellule résultant de la complexité O (n * n).

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 pour parcourir un graphique, nous le faisons dans un but précis. Lorsqu’il y a un problème pour trouver le plus court chemin dans un graphique non pondéré, ou pour trouver si un graphique est bipartite, nous pouvons utiliser BFS. Pour les problèmes de détection de cycle ou de toute logique nécessitant un retour en arrière, nous pouvons utiliser DFS.

Cette question est un peu ancienne, mais le jeu vidéo moderne “Bit Heroes” en est un bon exemple. Dans un donjon de boss typique, votre but est de vaincre le boss, 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 boss sont loin de votre point d’apparition. Le jeu propose une fonctionnalité de traversée automatique des donjons qui permet à votre personnage de traverser le donjon et de rencontrer les ennemis au fur et à mesure. Ceci est implémenté avec un algorithme de recherche en profondeur, car le but est d’aller aussi loin que possible dans le donjon avant de revenir en arrière.