Me gustaría agregar a la excelente respuesta de Sastry Aditya que BFS y DFS pueden tener diferentes complejidades espaciales en la práctica.
- BFS expande todos los hijos de un vértice y los mantiene en la memoria. Luego, pasa al siguiente nivel del primer hijo y expande sus hijos y también los mantiene en la memoria. Por lo tanto, BFS mantiene la franja de un salto de todos los vértices visitados en la memoria, lo que puede conducir a un uso elevado de la memoria.
- DFS expande iterativamente solo un hijo hasta que ya no puede continuar y retrocede a partir de entonces. Aunque la complejidad del espacio en el peor de los casos es la misma que BFS, es decir, [matemática] O (n) [/ matemática], puede haber un ahorro significativo de espacio en la práctica:
Con factor de ramificación [matemática] b [/ matemática] y profundidad máxima [matemática] m [/ matemática] , DFS requiere el almacenamiento de solo nodos [matemática] bm + 1 [/ matemática] que son [matemática] O (bm) [/ matemática] en comparación con [matemática] O (b ^ (d + 1)) [/ math] de la BFS. [1]
Por otro lado, si la profundidad de su gráfico es (casi) infinita, como en los árboles de búsqueda de ajedrez, el uso de DFS simple resulta en la exploración de un solo camino. La profundización iterativa de la profundidad máxima sería una solución rápida para esto.
- ¿Desarrolla algoritmos comerciales después de volver a probar los datos históricos? ¿O debería buscar a través de datos históricos patrones utilizando un algoritmo?
- ¿Te gusta la categoría de algoritmos de 'programación dinámica'?
- ¿Cuál es el orden cronológico de los algoritmos de reconocimiento facial?
- ¿El aprendizaje automático funciona modificando algoritmos o modificando datos y variables?
- ¿Cómo resolver la pregunta 1 de ZIO2015? ¿Es un enfoque de programación dinámica?
Notas al pie
[1] Blog T de Muhamad Hesham
