¿Cuáles son los factores prácticos a considerar al elegir entre búsqueda en profundidad (DFS) y búsqueda en amplitud (BFS)? [cerrado]
Entiendo las diferencias entre DFS y BFS, pero me interesa saber qué factores considerar al elegir DFS versus BFS.
Cosas como evitar DFS para árboles muy profundos, etc.
Eso depende en gran medida de la estructura del árbol de búsqueda y del número y ubicación de las soluciones (también conocidas como elementos buscados).
Si sabe que una solución no está lejos de la raíz del árbol, una búsqueda en amplitud (BFS) podría ser mejor.
Si el árbol es muy profundo y las soluciones son escasas, la búsqueda en profundidad (DFS) puede llevar mucho tiempo, pero BFS podría ser más rápida.
Si el árbol es muy ancho, un BFS podría necesitar demasiada memoria, por lo que podría resultar completamente impráctico.
Si las soluciones son frecuentes pero están ubicadas en lo profundo del árbol, BFS podría resultar poco práctico.
Si el árbol de búsqueda es muy profundo, deberá restringir la profundidad de búsqueda para la primera búsqueda en profundidad (DFS), de todos modos (por ejemplo, con profundización iterativa).
Pero éstas son sólo reglas generales; probablemente necesitarás experimentar.
Creo que, en la práctica, normalmente no utilizarás estos algoritmos en su forma pura. Podría haber heurísticas que ayuden a explorar primero partes prometedoras del espacio de búsqueda, o tal vez desee modificar su algoritmo de búsqueda para poder paralelizarlo de manera eficiente.
Búsqueda en profundidad
Las búsquedas en profundidad se utilizan a menudo en simulaciones de juegos (y situaciones similares a juegos en el mundo real). En un juego típico puedes elegir una de varias acciones posibles. Cada elección conduce a más elecciones, cada una de las cuales conduce a más elecciones, y así sucesivamente hasta formar un gráfico de posibilidades en forma de árbol en constante expansión.
Por ejemplo, en juegos como el ajedrez, el tres en raya, cuando decides qué movimiento hacer, puedes imaginar mentalmente un movimiento, luego las posibles respuestas de tu oponente, luego tus respuestas, etc. Puedes decidir qué hacer viendo qué movimiento conduce al mejor resultado.
Sólo algunos caminos en un árbol de juego te llevan a ganar. Algunos conducen a una victoria de tu oponente; cuando llegas a ese final, debes retroceder hasta un nodo anterior e intentar un camino diferente. De esta forma exploras el árbol hasta encontrar un camino con conclusión exitosa. Entonces das el primer paso en este camino.
Búsqueda en amplitud
La búsqueda en amplitud tiene una propiedad interesante: primero encuentra todos los vértices que están a una arista de distancia del punto inicial, luego todos los vértices que están a dos aristas de distancia, y así sucesivamente. Esto es útil si intentas encontrar el camino más corto desde el vértice inicial hasta un vértice determinado. Inicia un BFS y, cuando encuentra el vértice especificado, sabe que la ruta que ha trazado hasta ahora es la ruta más corta hasta el nodo. Si hubiera un camino más corto, el BFS ya lo habría encontrado.
La búsqueda en amplitud se puede utilizar para encontrar nodos vecinos en redes peer to peer como BitTorrent, sistemas GPS para encontrar ubicaciones cercanas, sitios de redes sociales para encontrar personas en la distancia especificada y cosas así.
Buena explicación de http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/
Un ejemplo de BFS
A continuación se muestra un ejemplo de cómo se vería un BFS. Esto es algo así como el recorrido del árbol de orden de niveles donde usaremos QUEUE con un enfoque ITERATIVO (principalmente RECURSIÓN terminará con DFS). Los números representan el orden en el que se accede a los nodos en un BFS:
En una primera búsqueda profunda, comienza en la raíz y sigue una de las ramas del árbol lo más lejos posible hasta que encuentre el nodo que está buscando o llegue a un nodo hoja (un nodo sin hijos). Si llega a un nodo hoja, continúa la búsqueda en el ancestro más cercano con hijos inexplorados.
Un ejemplo de DFS
A continuación se muestra un ejemplo de cómo se vería un DFS. Creo que el recorrido posterior al orden en el árbol binario comenzará a funcionar primero desde el nivel Hoja. Los números representan el orden en el que se accede a los nodos en un DFS:
Diferencias entre DFS y BFS
Comparando BFS y DFS, la gran ventaja de DFS es que tiene requisitos de memoria mucho menores que BFS, porque no es necesario almacenar todos los punteros secundarios en cada nivel. Dependiendo de los datos y de lo que esté buscando, DFS o BFS podrían resultar ventajosos.
Por ejemplo, dado un árbol genealógico, si uno estuviera buscando a alguien en el árbol que todavía esté vivo, entonces sería seguro asumir que esa persona estaría en la parte inferior del árbol. Esto significa que un BFS tardaría mucho tiempo en alcanzar ese último nivel. Un DFS, sin embargo, encontraría el objetivo más rápidamente. Pero, si uno estuviera buscando a un miembro de la familia que murió hace mucho tiempo, entonces esa persona estaría más cerca de la copa del árbol. Entonces, un BFS normalmente sería más rápido que un DFS. Entonces, las ventajas de cualquiera de los dos varían según los datos y lo que estés buscando.
Un ejemplo más es Facebook; Sugerencia sobre Amigos de Amigos. Necesitamos amigos inmediatos que nos sugieran dónde podemos usar BFS. Puede ser encontrar el camino más corto o detectar el ciclo (usando recursividad), podemos usar DFS.
La búsqueda primero en amplitud es generalmente el mejor enfoque cuando la profundidad del árbol puede variar y solo necesita buscar una solución en una parte del árbol. Por ejemplo, encontrar la ruta más corta desde un valor inicial hasta un valor final es un buen lugar para usar BFS.
La búsqueda en profundidad primero se usa comúnmente cuando necesita buscar en todo el árbol. Es más fácil de implementar (usando recursividad) que BFS y requiere menos estado: mientras que BFS requiere que almacene toda la 'frontera', DFS solo requiere que almacene la lista de nodos principales del elemento actual.
