Quand est-il pratique d'utiliser la recherche en profondeur (DFS) ou la recherche en largeur (BFS) ?

Question

Je comprends les différences entre DFS et BFS, mais j'aimerais savoir quand il est plus pratique d'utiliser l'un plutôt que l'autre ?

Quelqu'un pourrait-il donner des exemples de la manière dont la DFS l'emporterait sur la BFS et vice versa ?

Answer 1

Cela dépend fortement de la structure de l'arbre de recherche et du nombre et de l'emplacement des solutions (c'est-à-dire des éléments recherchés).

• Si vous savez qu'une solution n'est pas très éloignée de la racine de l'arbre, une recherche en largeur (BFS) peut être plus efficace.

• Si l'arbre est très profond et que les solutions sont rares, la recherche en profondeur d'abord (DFS) peut prendre un temps extrêmement long, mais BFS peut être plus rapide.

• Si l'arbre est très large, une BFS peut nécessiter trop de mémoire, et donc de sorte qu'il n'est pas du tout pratique.

• Si les solutions sont fréquentes mais situées en profondeur dans l'arbre, BFS peut être utilisé. peu pratique.

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

Mais ce ne sont que des règles empiriques ; vous devrez probablement expérimenter.

Je pense qu'en pratique, vous n'utiliserez généralement pas ces algorithmes dans leur forme pure de toute façon. Il pourrait y avoir des heuristiques qui aident à explorer d'abord les parties prometteuses de l'espace de recherche, ou vous pourriez vouloir modifier votre algorithme de recherche pour pouvoir le paralléliser efficacement.

Answer 2

La recherche en largeur (Breadth First Search) est généralement la meilleure approche lorsque la profondeur de l'arbre peut varier et que vous n'avez besoin de rechercher une solution que dans une partie de l'arbre. Par exemple, la recherche du chemin le plus court d'une valeur de départ à une valeur finale est un bon endroit pour utiliser BFS.

La recherche en profondeur est généralement utilisée lorsque vous devez effectuer une recherche dans l'ensemble de l'arbre. Elle est plus facile à mettre en œuvre (en utilisant la récursion) que la BFS et nécessite moins d'état : Alors que BFS nécessite de stocker toute la "frontière", DFS ne nécessite que de stocker la liste des nœuds parents de l'élément actuel.

Answer 3

Le système DFS est plus efficace en termes d'espace que le système BFS, mais il peut atteindre des profondeurs inutiles.

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

---

Sur IDDFS

Il convient de mentionner qu'il existe une variante moins connue qui combine l'efficacité spatiale de la DFS, mais (cumulativement) la visite d'ordre de niveau de la BFS, c'est le approfondissement itératif recherche en profondeur . Cet algorithme revisite certains nœuds, mais il ne contribue qu'à un facteur constant de différence asymptotique.

Answer 4

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

Voici la recherche en profondeur pour un graphe non orienté si vous stockez les 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(neighbor) # Visit each neighbor if not already visited

Si l'on stocke l'information "déjà visité" dans une structure de données séparée :

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(neighbor, visited)             # then visit the neighbor
dfs(origin, set())

Contrairement à la recherche en largeur, il est nécessaire de maintenir une structure de données distincte pour la liste des nœuds à visiter, quoi qu'il arrive.

Answer 5

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