algorithm - resueltos - ¿Cuándo es práctico utilizar la búsqueda en profundidad(DFS) frente a la búsqueda en profundidad(BFS)?
que es bfs (15)
Búsqueda en profundidad primero
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 lleva a más elecciones, cada una de las cuales conduce a más elecciones, y así sucesivamente a un gráfico de posibilidades en forma de árbol en constante expansión.
Por ejemplo, en juegos como el Ajedrez, el tic-tac-toe, cuando estás decidiendo qué movimiento realizar, puedes imaginar mentalmente un movimiento, luego las posibles respuestas de tu oponente, tus respuestas, etc. Puede decidir qué hacer al ver qué movimiento lleva al mejor resultado.
Sólo algunos caminos en un árbol de juego llevan a tu victoria. Algunos llevan a una victoria de su oponente, cuando llega a ese final, debe retroceder, o retroceder, a un nodo anterior e intentar una ruta diferente. De esta manera, explora el árbol hasta encontrar un camino con una conclusión exitosa. Entonces haces el primer movimiento por este camino.
Búsqueda de amplitud
La búsqueda de amplitud primero tiene una propiedad interesante: primero encuentra todos los vértices que están a un borde del punto de inicio, luego todos los vértices que están a dos bordes de distancia, y así sucesivamente. Esto es útil si está tratando de encontrar la ruta más corta desde el vértice inicial a un vértice dado. 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 al nodo. Si hubiera un camino más corto, el BFS ya lo habría encontrado.
La búsqueda en profundidad se puede usar para encontrar los 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í.
Entiendo las diferencias entre DFS y BFS, pero me interesa saber cuándo es más práctico usar uno sobre el otro.
¿Alguien podría dar algunos ejemplos de cómo DFS triunfaría sobre BFS y viceversa?
Algunos algoritmos dependen de las propiedades particulares de DFS (o BFS) para funcionar. Por ejemplo, el algoritmo de Hopcroft y Tarjan para encontrar componentes conectados 2 aprovecha el hecho de que cada nodo ya visitado encontrado por DFS está en la ruta desde la raíz hasta el nodo actualmente explorado.
Cuando aborda esta pregunta como un programador, se destaca un factor: si está utilizando la recursión, entonces la búsqueda en profundidad es más sencilla de implementar, ya que no es necesario mantener una estructura de datos adicional que contenga los nodos aún por explorar.
Aquí está la búsqueda en profundidad de un gráfico no orientado si está almacenando información "ya visitada" en los nodos:
def dfs(origin): # DFS from origin:
origin.visited = True # Mark the origin as visited
for neighbor in origin.neighbors: # Loop over the neighbors
if not neighbor.visited: dfs(next) # Visit each neighbor if not already visited
Si almacena información "ya visitada" en una estructura de datos separada:
def dfs(node, visited): # DFS from origin, with already-visited set:
visited.add(node) # Mark the origin as visited
for neighbor in node.neighbors: # Loop over the neighbors
if not neighbor in visited: # If the neighbor hasn''t been visited yet,
dfs(node, visited) # then visit the neighbor
dfs(origin, set())
Compare esto con la búsqueda de amplitud en la que necesita mantener una estructura de datos separada para la lista de nodos que aún no ha visitado, sin importar qué.
Cuando el ancho del árbol es muy grande y la profundidad es baja, use DFS ya que la pila de recursión no se desbordará. Use BFS cuando el ancho sea bajo y la profundidad sea muy grande para atravesar el árbol.
DFS es más eficiente en espacio que BFS, pero puede ir 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 el DFS puede ser más preferible a BFS.
En IDDFS
Debe mencionarse que hay una variante menos conocida que combina la eficiencia de espacio de DFS, pero (acumulativamente) la visita de orden de nivel de BFS, es la búsqueda iterativa de profundización en profundidad . Este algoritmo vuelve a visitar algunos nodos, pero solo contribuye con un factor constante de diferencia asintótica.
Debido a que las búsquedas en profundidad primero utilizan una pila a medida que se procesan los nodos, se proporciona el seguimiento en DFS. Debido a que las búsquedas de Breadth-First utilizan una cola, no una pila, para realizar un seguimiento de los nodos que se procesan, no se proporciona el seguimiento en BFS.
Depende de la situación en la que se usa. Cuando tenemos un problema de atravesar una gráfica, lo hacemos con algún propósito. Cuando hay un problema de encontrar la ruta más corta en un gráfico no ponderado, o encontrar si un gráfico es bipartito, podemos usar BFS. Para problemas de detección de ciclos o cualquier lógica que requiera un seguimiento, podemos usar DFS.
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 primera búsqueda de amplitud (BFS) podría ser mejor.
Si el árbol es muy profundo y las soluciones son poco frecuentes, la primera búsqueda en profundidad (DFS) puede llevar mucho tiempo, pero BFS podría ser más rápido.
Si el árbol es muy ancho, un BFS puede necesitar demasiada memoria, por lo que puede ser completamente impráctico.
Si las soluciones son frecuentes pero están ubicadas en lo profundo del árbol, BFS podría ser 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 estas son solo reglas de oro; Probablemente necesites experimentar.
Esta pregunta es algo antigua, pero un gran ejemplo es el moderno videojuego "Bit Heroes". En una mazmorra típica, tu objetivo es derrotar al jefe, después de lo cual tienes la opción de abandonar esa mazmorra en particular o continuar explorándola en busca de botín. Pero en general, los jefes están lejos de tu punto de generación. El juego ofrece una función automática de recorrido de mazmorras que básicamente lleva a tu personaje a través de la mazmorra, encontrando enemigos a medida que avanza. Esto se implementa con un algoritmo de búsqueda primero en profundidad, ya que el objetivo es ir lo más profundo posible en la mazmorra antes de retroceder.
Este es un buen ejemplo para demostrar que BFS es mejor que DFS en ciertos casos. https://leetcode.com/problems/01-matrix/
Cuando se implementa correctamente, ambas soluciones deben visitar celdas que tengan una distancia mayor que la celda actual +1. Pero DFS es ineficiente y visitó repetidamente la misma celda, lo que resultó en una complejidad O (n * n).
Por ejemplo,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,
Explicación agradable de programmerinterview.com/index.php/data-structures/dfs-vs-bfs
Un ejemplo de BFS
Aquí hay un ejemplo de cómo se vería un BFS. Esto es algo así como el paso del árbol de orden de nivel en el que usaremos QUEUE con un enfoque ITERATIVO (en su mayoría, RECURSION 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 en profundidad, comienza en la raíz y sigue una de las ramas del árbol lo más lejos posible hasta que se encuentre el nodo que estás buscando o golpees un nodo de hoja (un nodo sin hijos). Si golpeas un nodo de hoja, entonces continúas la búsqueda en el antepasado más cercano con hijos inexplorados.
Un ejemplo de DFS
Aquí hay un ejemplo de cómo se vería un DFS. Creo que el recorrido posterior a la orden en el árbol binario comenzará a trabajar desde el nivel de Hoja primero. 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 más bajos que BFS, porque no es necesario almacenar todos los punteros secundarios en cada nivel. Dependiendo de los datos y lo que esté buscando, DFS o BFS podrían ser ventajosos.
Por ejemplo, dado un árbol genealógico si uno está buscando a alguien en el árbol que aún está vivo, 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ápido. Pero, si uno buscaba a un miembro de la familia que murió hace mucho tiempo, entonces esa persona estaría más cerca de la parte superior del árbol. Entonces, un BFS normalmente sería más rápido que un DFS. Por lo tanto, las ventajas de cualquiera varían según los datos y lo que está buscando.
Un ejemplo más es Facebook; Sugerencia sobre amigos de amigos. Necesitamos amigos inmediatos para sugerir dónde podemos usar BFS. Puede ser encontrar la ruta más corta o detectar el ciclo (usando la recursión) que podemos usar DFS.
La búsqueda en primer lugar es generalmente el mejor enfoque cuando la profundidad del árbol puede variar, y solo necesita buscar una solución en la parte del árbol. Por ejemplo, encontrar el camino más corto desde un valor de inicio hasta un valor final es un buen lugar para usar BFS.
La búsqueda en profundidad en primer lugar se usa comúnmente cuando necesitas buscar en todo el árbol. Es más fácil de implementar (usando recursión) que BFS, y requiere menos estado: mientras BFS requiere que almacene toda la "frontera", DFS solo requiere que almacene la lista de nodos principales del elemento actual.
Para BFS, podemos considerar el ejemplo de Facebook. Recibimos sugerencias para agregar amigos del perfil de FB de otro perfil de otros amigos. Supongamos que A-> B, mientras que B-> E y B-> F, entonces A obtendrá una sugerencia para E y F. Deben estar usando BFS para leer hasta el segundo nivel. DFS se basa más en los escenarios en los que queremos pronosticar algo en función de los datos que tenemos desde el origen hasta el destino. Como ya se mencionó sobre el ajedrez o el sudoku. Una cosa que tengo diferente aquí es, creo que DFS debería usarse para la ruta más corta porque DFS cubrirá toda la ruta primero y luego podemos decidir cuál es la mejor. Pero como BFS utilizará el enfoque de Greedy, podría parecer que es el camino más corto, pero el resultado final puede diferir. Déjame saber si mi entendimiento es incorrecto.
Según las propiedades de DFS y BFS. Por ejemplo, cuando queremos encontrar el camino más corto. Usualmente usamos bfs, puede garantizar el ''más corto''. pero dfs solo puede garantizar que podemos llegar desde este punto, podemos lograr ese punto, no podemos garantizar el ''más corto''.
Una ventaja importante de BFS sería que se puede usar para encontrar la ruta más corta entre dos nodos en un gráfico no ponderado. Mientras que, no podemos usar DFS para el mismo .