Dans cette histoire, je vais comparer les deux algorithmes couramment utilisés pour la fondation de l’intelligence artificielle et des réseaux neuronaux, à savoir la recherche en profondeur et la recherche en largeur. Si vous n’avez pas compris ces deux algorithmes, consultez mes autres articles pour une instruction de 5 minutes et vous serez en mesure de les comprendre.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
Premièrement, ce sont tous les deux des algorithmes de recherche non informés, ce qui signifie qu’ils fonctionnent par force brute et ne disposent pas d’informations supplémentaires sur l’état ou l’espace de recherche en plus de la façon de traverser l’arbre. Si vous avez lu mes articles précédents sur DFS ou BFS, vous savez qu’aucun d’entre eux ne regardera le poids de chaque étape pendant le processus de recherche.
- Runtime : Les deux algorithmes fonctionnent en O(n) car dans le pire des cas, ils devront visiter chaque nœud de l’espace de recherche.
- quand DFS>BFS : Si le nœud que nous recherchons est très profond ou s’il y a plusieurs nœuds de but qui sont assez profonds, nous devrions utiliser DFS. Dans ce cas, BFS doit visiter chaque nœud au-dessus avant de visiter les nœuds profonds, ce qui prend trop de temps.
- quand BFS>DFS : BFS peut être utilisé pour trouver le plus court chemin à source unique dans un graphe non pondéré, car dans BFS, nous atteignons un sommet avec un nombre minimum d’arêtes à partir d’un sommet source. D’autre part, dans DFS, nous pourrions traverser plus d’arêtes pour atteindre un sommet de destination à partir d’une source.
- type de recherche : les deux sont des recherches non informées
- comparaison de mémoire : BFS prendra plus de mémoire parce qu’il doit revenir en arrière plus que DFS en général.
- structure de données : DFS utilise une pile, qui contient les nœuds de la racine au nœud recherché. BFS utilise une file d’attente, qui contient les nœuds à l’avant de la recherche.
.