Búsqueda de gráficos: amplitud primero versus profundidad primero

Al buscar gráficos, hay dos algoritmos sencillos: primero en amplitud y profundidad-primero (generalmente se realiza mediante la adición de todos los nodos del gráfico adjactent a una cola (en amplitud) o pila (profundidad-primero)).

Ahora, ¿hay alguna ventaja de uno sobre otro?

Los que se me ocurren:

• Si espera que sus datos estén bastante lejos dentro del gráfico, primero la profundidad puede encontrarlos antes, ya que va a las partes más profundas del gráfico muy rápido.
• Por el contrario, si espera que sus datos estén bastante arriba en el gráfico, la amplitud primero puede dar el resultado antes.

¿Hay algo que me haya perdido o se debe principalmente a preferencias personales?

Me gustaría citar una respuesta de Stack Overflow de hstoerr que cubre muy bien el problema:

Eso depende en gran medida de la estructura del árbol de búsqueda y del número y ubicación de las soluciones .
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 raras, la búsqueda profunda en primer lugar (DFS) podría basarse para siempre, pero BFS podría ser más rápido. Si el árbol es muy ancho, un BFS podría necesitar mucha más memoria, por lo que podría no ser práctico. Si las soluciones son frecuentes pero se encuentran en lo profundo del árbol, BFS podría no ser práctico. Si el árbol de búsqueda es muy profundo, deberá restringir la profundidad de búsqueda para la primera búsqueda de profundidad (DFS), de todos modos (por ejemplo, con profundización iterativa).

Pero estas son solo reglas generales; probablemente necesites experimentar.

Rafał Dowgird también comenta:

Algunos algoritmos dependen de las propiedades particulares de DFS (o BFS) para funcionar. Por ejemplo, el algoritmo Hopcroft y Tarjan para encontrar componentes conectados a 2 aprovecha el hecho de que cada nodo ya visitado por DFS se encuentra en la ruta desde la raíz hasta el nodo explorado actualmente.

Un punto que es importante en nuestro mundo multinúcleo: BFS es mucho más fácil de paralelizar. Esto es intuitivamente razonable (enviar subprocesos para cada niño) y también se puede demostrar que es así. Entonces, si tiene un escenario en el que puede hacer uso del paralelismo, entonces BFS es el camino a seguir.

(Hice de este un wiki de la comunidad. Por favor, edítelo)

Si

• $b$ es el factor de ramificación
• $d$ es la profundidad donde está la solución
• d ≤ $h$ es la altura del árbol (entonces, )$d\le h$

Entonces

• DFS toma tiempo y espacioO ( h $O(b^h)$$O(h)$
• BFS toma tiempo y espacioO ( b d$O(b^d)$$O(b^d)$
• IDDFS toma tiempo y espacioO ( d $O(b^d)$$O(d)$

Razones para elegir

• DFS
  • debe ver todo el árbol de todos modos
  • sabes , el nivel de la respuesta$d$
  • no me importa si la respuesta está más cerca de la raíz
• BFS
  • la respuesta está cerca de la raíz
  • quieres la respuesta más cercana a la raíz
  • tener múltiples núcleos / procesadores
• IDDFS
  • quieres BFS, no tienes suficiente memoria, pero un poco más lento es aceptable

IDDFS = profundización iterativa búsqueda en profundidad primero

Un escenario (además de encontrar el camino más corto, que ya se ha mencionado) en el que puede que tenga que elegir uno sobre el otro para obtener un programa correcto sería gráficos infinitos:

Si consideramos, por ejemplo, un árbol donde cada nodo tiene un número finito de hijos, pero la altura del árbol es infinita, es posible que DFS nunca encuentre el nodo que está buscando, simplemente seguirá visitando al primer hijo de cada nodo ve, así que si el que estás buscando no es el primer hijo de su padre, nunca llegará allí. Sin embargo, BFS está garantizado para encontrarlo en un tiempo finito.

De manera similar, si consideramos un árbol donde cada nodo tiene un número infinito de hijos, pero el árbol tiene una altura finita, BFS podría no terminar. Solo visitará a los hijos del nodo raíz y si el nodo que está buscando es hijo de otro nodo, no será alcanzado. En este caso, se garantiza que DFS lo encontrará en un tiempo finito.

La amplitud primero y la profundidad primero ciertamente tienen el mismo comportamiento en el peor de los casos (el nodo deseado es el último encontrado). Sospecho que esto también es cierto para el caso promedio si no tiene información sobre sus gráficos.

Una buena ventaja de la búsqueda de amplitud es que encuentra caminos más cortos (en el sentido de la menor cantidad de aristas) que pueden ser interesantes o no.

Si su rango promedio de nodos (número de vecinos) es alto en relación con el número de nodos (es decir, el gráfico es denso), la amplitud tendrá colas enormes, mientras que la profundidad tendrá pilas pequeñas. En gráficos dispersos, la situación se invierte. Por lo tanto, si la memoria es un factor limitante, la forma del gráfico en cuestión puede tener que informar su elección de estrategia de búsqueda.

Todo lo anterior es correcto, pero cabe destacar que BFS y DFS crean sus propios árboles, en función del orden que utilizan para atravesar el árbol. Cada uno de esos árboles tiene su propia propiedad que puede ser útil en algún tipo de problema.

Por ejemplo, todos los bordes en el gráfico original que no están en el árbol BFS son bordes cruzados; bordes que se encuentran entre dos ramas del árbol BFS. Todos los bordes en el gráfico original que no están en el árbol DFS son bordes posteriores; bordes que conectan dos vértices en una rama del árbol DFS. Dichas propiedades pueden ser útiles para problemas como coloraciones especiales, etc.

El árbol DFS y BFS tienen sus propias propiedades únicas que pueden brindarle información más útil sobre el gráfico. Por ejemplo, con un solo DFS puede hacer lo siguiente:

• Encuentra puentes y puntos de articulación (para gráficos no dirigidos)
• Detección de ciclos
• Encuentra componentes fuertemente conectados (algoritmo de Tarjan)

Con BFS, puede encontrar las rutas más cortas entre el nodo de origen y cualquier otro nodo en el gráfico.

El capítulo Algoritmos de gráficos en CLRS resume muy bien estas propiedades de DFS y BFS.

Creo que sería interesante escribir ambos de una manera que solo cambiando algunas líneas de código le daría un algoritmo u otro, para que vea que su dillema no es tan fuerte como parece ser al principio .

Personalmente, me gusta la interpretación de BFS como una inundación de un paisaje: las áreas de baja altitud se inundarán primero, y solo entonces las áreas de alta altitud seguirán. Si imagina las altitudes del paisaje como isolinas como vemos en los libros de geografía, es fácil ver que BFS llena todas las áreas bajo la misma isolínea al mismo tiempo, tal como sería con la física. Por lo tanto, interpretar las altitudes como distancia o costo escalado da una idea bastante intuitiva del algoritmo.

Con esto en mente, puede adaptar fácilmente la idea detrás de la búsqueda de amplitud para encontrar fácilmente el árbol de expansión mínimo, la ruta más corta y también muchos otros algoritmos de minimización.

Todavía no vi ninguna interpretación intuitiva de DFS (solo la estándar sobre el laberinto, pero no es tan poderosa como la BFS y las inundaciones), por lo que para mí parece que BFS parece correlacionarse mejor con los fenómenos físicos como se describió anteriormente, mientras que DFS se correlaciona mejor con las opciones de dillema en sistemas racionales (es decir, personas o computadoras que deciden qué movimiento hacer en un juego de ajedrez o salir de un laberinto).

Entonces, para mí, la diferencia entre mentiras es qué fenómeno natural se adapta mejor a su modelo de propagación (transversal) en la vida real.