En este artículo, voy a comparar los dos algoritmos comúnmente utilizados para la base de la inteligencia artificial y las redes neuronales, a saber, depth-first-search y breadth-first-search. Si no has entendido estos dos algoritmos, revisa mis otros artículos para una instrucción de 5 minutos y podrás entenderlos.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
En primer lugar, ambos son algoritmos de búsqueda no informados, lo que significa que operan por fuerza bruta y no tienen información adicional sobre el estado o el espacio de búsqueda además de cómo atravesar el árbol. Si has leído mis artículos anteriores sobre DFS o BFS, sabes que ninguno de ellos mira el peso de cada paso durante el proceso de búsqueda.
- Tiempo de ejecución: Ambos algoritmos operan en O(n) ya que, en el peor de los casos, necesitarán visitar todos los nodos del espacio de búsqueda.
- Cuando DFS>BFS: Si el nodo que buscamos es muy profundo o hay varios nodos meta que están bastante abajo, debemos utilizar DFS. En este caso, BFS tiene que visitar todos los nodos superiores antes de visitar los nodos profundos, lo que lleva demasiado tiempo.
- cuando BFS>DFS: BFS se puede utilizar para encontrar el camino más corto de un solo origen en un grafo no ponderado, porque en BFS, llegamos a un vértice con un número mínimo de aristas desde un vértice origen. Por otro lado, en DFS, podríamos atravesar más aristas para llegar a un vértice de destino desde un origen.
- tipo de búsqueda: ambas son búsquedas no informadas
- comparación de memoria: BFS ocupará más memoria porque tiene que retroceder más que DFS en general.
- Estructura de datos: DFS utiliza una pila, que contiene los nodos desde la raíz hasta el nodo que se está buscando. BFS utiliza una cola, que contiene nodos en la parte delantera de la búsqueda.