Recherche de graphique: largeur d'abord, profondeur d'abord

79

Lors de la recherche de graphiques, il existe deux algorithmes simples: width-first et depth-first (généralement effectué en ajoutant tous les nœuds de graphes adjacents à une file d'attente (width-first) ou à une pile (depth-first)).

Maintenant, y a-t-il des avantages de l'un sur l'autre?

Ceux auxquels je pourrais penser:

  • Si vous vous attendez à ce que vos données se trouvent assez loin dans le graphique, deep-first pourrait le trouver plus tôt, car vous allez très rapidement dans les parties les plus profondes du graphique.
  • Inversement, si vous vous attendez à ce que vos données se situent assez loin dans le graphique, width-first peut donner le résultat plus tôt.

Y a-t-il quelque chose qui m'a échappé ou est-ce que cela dépend principalement des préférences personnelles?

malexmave
la source

Réponses:

43

J'aimerais citer une réponse de Stack Overflow by hstoerr qui résume bien le problème:

Cela dépend en grande partie de la structure de l'arbre de recherche et du nombre et de l'emplacement des solutions .
Si vous savez qu'une solution n'est pas loin de la racine de l'arbre, une recherche d'abord large (BFS) pourrait être préférable. Si l'arborescence est très profonde et que les solutions sont rares, la recherche d'abord en profondeur (DFS) peut avoir lieu à tout jamais, mais BFS pourrait être plus rapide. Si l’arborescence est très large, un système de fichiers BFS peut nécessiter trop de mémoire, de sorte qu’il risque de ne pas être pratique. 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 quand même restreindre la profondeur de recherche pour la recherche en profondeur d'abord (par exemple avec un approfondissement itératif).

Mais ce ne sont que des règles empiriques; vous aurez probablement besoin d'expérimenter.

Rafał Dowgird remarque également:

Certains algorithmes dépendent de propriétés particulières de DFS (ou BFS) pour fonctionner. Par exemple, l'algorithme Hopcroft et Tarjan pour rechercher des composants connectés en double tire parti du fait que chaque nœud déjà visité rencontré par DFS se trouve sur le chemin allant de la racine au nœud actuellement exploré.

Gigili
la source
5
Je ne comprends pas pourquoi cette réponse compte 27 votes positifs et c’est exactement la fusion de 2 autres réponses, qui sont d’ailleurs simplement des réflexions générales sur ...
nbro,
37

Un point important dans notre monde multicœur: BFS est beaucoup plus facile à paralléliser. Ceci est intuitivement raisonnable (envoyer des fils à chaque enfant) et il peut être prouvé qu'il en est ainsi. Donc, si vous avez un scénario où vous pouvez utiliser le parallélisme, alors BFS est la voie à suivre.

Suresh
la source
8
Si DFS est par ailleurs avantageux dans le paramètre donné, vous pouvez appliquer BFS jusqu'à ce que vous ayez généré suffisamment de threads et continuer avec DFS. Plus spécifiquement, vous pouvez utiliser DFS et chaque fois que vous descendez et qu’il n’ya pas assez de threads, en créez un pour le prochain frère.
Raphaël
Cette réponse ne mérite pas 20 votes positifs. La question concerne l'utilisation générale des 2 algorithmes et non une utilisation particulière.
2015
31

(J'ai fait de ce site un wiki de communauté. N'hésitez pas à le modifier.)

Si

  • b
  • d
  • hdh

ensuite

  • O(bh)O(h)
  • O(bd)O(bd)
  • O(bd)O(d)

Raisons de choisir

  • DFS
    • il faut quand même voir l'arbre entier
    • d
    • ne vous inquiétez pas si la réponse est la plus proche de la racine
  • BFS
    • la réponse est proche de la racine
    • vous voulez la réponse la plus proche de la racine
    • avoir plusieurs cœurs / processeurs
  • IDDFS
    • vous voulez BFS, vous n'avez pas assez de mémoire, mais un peu plus lent est acceptable

IDDFS = recherche approfondie approfondie d'abord itérative

rgrig
la source
1
C'est une excellente réponse. Je remarque cependant que même si la question concerne les graphiques, cette réponse fait référence aux arbres. Un arbre est un graphique bien sûr, et il se peut que le mot puisse être remplacé ... mais qu'en est-il de hla "hauteur de l'arbre". Est-ce que cela se traduit directement par "la hauteur du graphique"?
user2023370
Une autre raison d'utiliser IDDFS est que, selon la manière dont vous voulez l'utiliser, vous pouvez avoir une réponse après chaque itération (si vous recherchez un maximum ou un minimum, par exemple). Cela signifie que vous pouvez quitter l'algorithme plus tôt si votre réponse est "assez bonne" ou vous pouvez quitter l'utilisateur (par exemple, un moteur d'échecs utilisant IDDFS pour trouver une solution optimale mais étant interrompu par un joueur déplaçant une pièce).
Jedd.ahyoung
Un autre point à ajouter est que le DFS utilise la pile alors que le BFS utilise la file d'attente.
Karthik Balaguru
17

Un scénario (autre que la recherche du chemin le plus court, qui a déjà été mentionné) dans lequel vous devrez peut-être choisir l'un sur l'autre pour obtenir un programme correct serait constitué de graphes infinis:

Si nous considérons par exemple un arbre où chaque nœud a un nombre fini d'enfants, mais que sa hauteur est infinie, DFS pourrait ne jamais trouver le nœud que vous recherchez. Il continuera simplement à visiter le premier enfant de chaque nœud. voit, donc si celui que vous recherchez n'est pas le premier enfant de son parent, il n'y parviendra jamais. BFS est cependant assuré de le trouver en temps fini.

De même, si nous considérons un arbre où chaque noeud a un nombre infini d'enfants, mais que l'arbre a une hauteur finie, BFS pourrait ne pas se terminer. Il ne visitera que les enfants du nœud racine et si le nœud que vous recherchez est l'enfant d'un autre nœud, il ne sera pas atteint. Dans ce cas, DFS est assuré de le trouver en temps fini.

sepp2k
la source
7
Il est à noter que les deux ne donnent que des algorithmes de semi-décision pour des graphes infinis; vous ne pouvez pas décider en temps fini qu'un élément ne soit pas dans l'arbre (évidemment). En ce qui concerne les applications pratiques, notez que des structures de données (conceptuellement) infinies peuvent être définies (voir paragraphe 3.4)!
Raphaël
15

La largeur d'abord et la profondeur d'abord ont certainement le même comportement dans le cas le plus défavorable (le nœud souhaité est le dernier trouvé). Je suppose que cela est également vrai pour tous les cas si vous n’avez pas d’informations sur vos graphiques.

Un bon bonus de la recherche en largeur d'abord est qu'elle trouve les chemins les plus courts (dans le sens du moins d'arêtes) qui peuvent présenter un intérêt ou non.

Si votre rang de nœud moyen (nombre de voisins) est élevé par rapport au nombre de nœuds (c'est-à-dire que le graphique est dense), width-first aura d'énormes files d'attente, tandis que depth-first aura de petites piles. Dans les graphiques clairsemés, la situation est inversée. Par conséquent, si la mémoire est un facteur limitant, il se peut que la forme du graphique à traiter informe votre choix de stratégie de recherche.

Raphaël
la source
La longueur de la file d'attente dans bfs et la hauteur de la pile dans dfs dépendent beaucoup de la mise en œuvre. Si, dans le cas de dfs, vous développez toujours la totalité du voisin sur la pile, cela augmente beaucoup, surtout lorsque le graphique est dense. Pousser uniquement la référence qui indique où continuer lorsque dfs revient de la récursion économise beaucoup d’espace.
Uli
3

Tout ce qui précède est correct, mais il convient de noter que BFS et DFS créent leurs propres arborescences, en fonction de l'ordre utilisé pour les parcourir. Chacun de ces arbres a sa propre propriété, ce qui peut être utile en cas de problème.

Par exemple, toutes les arêtes du graphique d'origine qui ne figurent pas dans l'arborescence BFS sont des arêtes croisées; des arêtes situées entre deux branches de l’arbre BFS. Toutes les arêtes du graphique d'origine qui ne figurent pas dans l'arborescence DFS sont des arrières; des arêtes reliant deux sommets d'une branche de l'arborescence DFS. De telles propriétés peuvent être utiles pour des problèmes tels que des colorants spéciaux, etc.

MMS
la source
1

DFS et BFS arborent tous deux leurs propres propriétés uniques qui peuvent vous donner des informations plus utiles sur le graphique. Par exemple, avec un seul DFS, vous pouvez effectuer les opérations suivantes:

  • Trouver des ponts et des points d'articulation (pour les graphiques non orientés)
  • Détection de cycle
  • Trouver des composants fortement connectés (algorithme de Tarjan)

Avec BFS, vous pouvez trouver les chemins les plus courts entre le nœud source et tout autre nœud du graphique.

Le chapitre sur les algorithmes graphiques dans CLRS résume très bien ces propriétés de DFS et de BFS.

Pincer
la source
-2

Je pense qu'il serait intéressant d'écrire les deux de manière à ce que seul un changement de lignes de code donne un algorithme ou un autre, afin que vous puissiez voir que votre dillema n'est pas si puissant qu'il semble l'être au premier abord. .

Personnellement, j’aime bien l’interprétation de BFS comme une inondation de paysage: les zones de basse altitude seront inondées en premier, puis les zones de haute altitude suivront. Si vous imaginez les altitudes du paysage comme des isolignes, comme nous le voyons dans les livres de géographie, il est facile de voir que BFS remplit toutes les zones sous la même isoline en même temps, comme ce serait le cas avec la physique. Ainsi, interpréter les altitudes comme distance ou coût réduit donne une idée assez intuitive de l’algorithme.

En gardant cela à l'esprit, vous pouvez facilement adapter l'idée de la recherche en largeur d'abord pour trouver facilement l'arbre de recouvrement minimal, le chemin le plus court et de nombreux autres algorithmes de minimisation.

Je n'ai pas encore vu d'interprétation intuitive de DFS (seulement celle standard sur le labyrinthe, mais elle n'est pas aussi puissante que celle de BFS et les inondations), donc pour moi, il semble que BFS semble mieux corréler avec les phénomènes physiques décrits ci-dessus, alors que DFS est plus en corrélation avec les choix de dillema sur des systèmes rationnels (c’est-à-dire que ce sont les personnes ou les ordinateurs qui décident de ce qu’il faut faire pour une partie d’échecs ou pour sortir d’un labyrinthe).

Donc, pour moi, la différence entre les mensonges sur lesquels le phénomène naturel correspond le mieux à son modèle de propagation (transversal) dans la vie réelle.

utilisateur5193682
la source
2
Bienvenue sur le site! Cependant, je ne vois pas vraiment comment cela répond à la question. Cela semble être vos sentiments généraux et vos intuitions sur BFS et DFS, mais la question ne se pose pas à propos des sentiments et des intuitions: elle concerne les avantages et les inconvénients. Votre réponse ne semble pas répondre à cela du tout.
David Richerby
La partie la plus liée à la question concerne l'adaptation de l'algorithme pour trouver des arbres couvrant minimum, le chemin le plus court, etc., et dire que certains phénomènes naturels sont reproductibles par BFS, tandis que les arbres de décision par DFS
utilisateur5193682
1
La question ne demande pas ce qui est lié à BFS et DFS. Il ne s'agit pas de rechercher des arbres couvrant le sol ou des chemins les plus courts, ni de savoir "reproduire des phénomènes naturels".
David Richerby
C'est demander des avantages. Si l'on peut modéliser un phénomène physique alors que l'autre ne le peut pas, c'est un avantage si vous devez modéliser ce phénomène. Je pense que vous en tenir aux concepts standard d'algorithmes manuel lors de l' interprétation du mot « avantage », alors que je ne suis pas
user5193682