¿Cuándo es práctico utilizar la búsqueda en profundidad (DFS) frente a la búsqueda en profundidad (BFS)?
Entiendo las diferencias entre el DFS y el BFS, pero me interesa saber cuándo es más práctico utilizar uno que otro.
¿Podría alguien dar algún ejemplo de cómo DFS superaría a BFS y viceversa?
310
3
Eso depende en gran medida de la estructura del árbol de búsqueda y del número y la ubicación de las soluciones (también conocidas como elementos buscados).
Si se sabe que una solución no está lejos de la raíz del árbol, una búsqueda de amplitud (BFS) puede ser mejor.
Si el árbol es muy profundo y las soluciones son escasas, la búsqueda en profundidad (DFS) podría llevar mucho tiempo, pero la BFS podría ser más rápida.
Si el árbol es muy ancho, una BFS podría necesitar demasiada memoria, por lo que puede ser totalmente inviable.
Si las soluciones son frecuentes pero se encuentran en lo más profundo del árbol, BFS podría ser poco práctico.
Si el árbol de búsqueda es muy profundo, tendrá que restringir la profundidad de búsqueda de búsqueda para la búsqueda en profundidad (DFS), de todos modos (por ejemplo con profundización iterativa).
Pero estas son sólo reglas generales; probablemente tendrá que experimentar.
La búsqueda de amplitud es generalmente el mejor enfoque cuando la profundidad del árbol puede variar, y sólo se necesita buscar una parte del árbol para una solución. Por ejemplo, encontrar el camino más corto desde un valor inicial hasta un valor final es un buen lugar para utilizar BFS.
La búsqueda en profundidad se utiliza normalmente cuando se necesita buscar en todo el árbol. Es más fácil de implementar (usando recursión) que BFS, y requiere menos estado: Mientras que BFS requiere que se almacene toda la "frontera", DFS sólo requiere que se almacene la lista de nodos padre del elemento actual.
El DFS es más eficiente en cuanto a espacio que el BFS, pero puede llegar a profundidades innecesarias.
Sus nombres son reveladores: si hay una gran amplitud (es decir, un gran factor de ramificación), pero una profundidad muy limitada (por ejemplo, un número limitado de "movimientos"), entonces DFS puede ser más preferible a BFS.
En IDDFS
Hay que mencionar que hay una variante menos conocida que combina la eficiencia espacial de DFS, pero (acumulativamente) la visita de orden de nivel de BFS, es el iterative deepening depth-first search. Este algoritmo vuelve a visitar algunos nodos, pero sólo aporta un factor constante de diferencia asintótica.