algorithm - tag - etiqueta de titulo en html
¿Para qué sirve la búsqueda de amplitud? (10)
Por lo general, cuando he tenido que recorrer un gráfico, siempre he usado la búsqueda de profundidad en primer lugar debido a la menor complejidad del espacio. Honestamente, nunca he visto una situación que requiera una búsqueda amplia, aunque mi experiencia es bastante limitada.
¿Cuándo tiene sentido usar una búsqueda de amplitud?
ACTUALIZACIÓN : Supongo que mi respuesta here muestra una situación en la que he usado un BFS (porque pensé que era un DFS). Todavía tengo curiosidad por saber por qué fue útil en este caso.
¿Cuándo tiene sentido usar una búsqueda de amplitud?
Por ejemplo, cuando necesita encontrar la ruta más corta en un gráfico, DFS simplemente no puede hacer eso. Existen algunas otras aplicaciones, pero, en general, DFS y BFS son el mismo algoritmo que trabaja en diferentes estructuras de datos (BFS usa la cola y el DFS funciona con la pila).
BFS a veces es realmente útil. Supongamos que tiene un árbol que representa digamos WBS. Es posible que desee presentarle a su usuario solo 1 nivel.
Cuando desee llegar a un nodo, recorra el menor número posible de bordes, es decir, cuando desee encontrar la ruta más corta en un gráfico no ponderado.
Además, la complejidad espacial de una primera búsqueda en profundidad puede ser mayor que la de una primera búsqueda de amplitud cuando, por ejemplo, cada nodo tiene solo un nodo hijo, es decir, cuando el gráfico es profundo pero no muy amplio.
Cuando necesita obtener el camino más corto a un vértice desde un gráfico sin peso de borde.
El algoritmo de búsqueda de primer orden le gusta mantenerse lo más cerca posible del punto de partida. Algunas de las situaciones en las que puedo pensar son:
- Los sitios web de redes sociales pueden usarlo para encontrar a las personas en la distancia especificada.
- Puede ser útil en redes de torrents / peer-to-peer para buscar computadoras vecinas.
- Los sistemas de navegación GPS pueden usarlo para encontrar ubicaciones cercanas.
En la primera búsqueda en profundidad puede encontrar soluciones "locales": para encontrar realmente una solución global, necesita recorrer todo el gráfico (o utilizar una heurística).
Nadie ha mencionado aún un factor clave en los casos en que la búsqueda de amplitud es útil: visitar un nodo de una manera puede eliminar el requisito de visitar el nodo de otra manera. En algunos casos, uno terminará haciendo el mismo trabajo independientemente del orden en que se visiten los nodos, pero BFS tendrá muchas menos acciones pendientes a la vez que DFS. En otros casos, visitar nodos en una secuencia puede requerir más trabajo que otros; varios algoritmos de ruta más corta se dan como un ejemplo de eso. Si visitar un nodo requiere visitar a sus vecinos a menos que se sepa que el nodo es accesible por una ruta más corta que la actual, visitar los nodos en orden de amplitud típicamente dará como resultado que los nodos tengan asignada la ruta más corta, o algo cercano a ella. en su primera visita Por el contrario, una búsqueda en profundidad haría que muchos nodos fueran visitados por caminos muy largos la primera vez, luego por caminos ligeramente más cortos, luego por caminos ligeramente más cortos, etc., que requerían una cantidad total de trabajo realmente monstruosa.
Por cierto, una buena ilustración gráfica de la diferencia entre los algoritmos primero en profundidad y primero en ancho es un relleno de inundación de área, donde un nodo blanco está lleno de inundaciones pintándolo de negro y llenando de inundación a sus vecinos. Si se intenta rellenar un área cuadrada NxN comenzando en un maíz, una operación de profundidad llenaría el cuadrado en una secuencia en espiral o en zig-zag, con operaciones NxN-1 restantes en la pila. Un relleno de ancho primero se "vierta" desde el punto de inicio y tiene como máximo O (N) operaciones pendientes, independientemente de la forma que se llene. Por cierto, el relleno de inundación en IBM BASICA funcionó de esa manera (no estoy seguro acerca de QBASIC).
Podría usarse para resolver un problema de búsqueda con un número mínimo de pasos. Profundizar primero podría conducir (si no limitado de alguna manera) a una profundidad infinita.
Ejemplo: encontrar el nodo más cercano a la raíz que satisface una condición.
Si su dominio de búsqueda es infinito, depth-first-search no garantiza terminar / encontrar una solución, incluso si existe una solución finita.
También puede ver algoritmos más elaborados, como A *, que es un subtipo especial de amplitud-primera búsqueda.
En general, bfs es óptimo y completo (con un factor de ramificación finito) mientras que dfs no lo es.
Un ejemplo es atravesar el sistema de archivos (con profundidad recursiva limitada).
Según la wikipedia , también es útil para ciertos algoritmos de gráficos (bipartitos, componentes conectados).