¿Por qué no se puede utilizar DFS para encontrar rutas más cortas en gráficos no ponderados?

16

Entiendo que usar DFS "tal cual" no encontrará una ruta más corta en un gráfico no ponderado.

Pero, ¿por qué ajustar DFS para permitirle encontrar caminos más cortos en gráficos no ponderados es una perspectiva tan desesperada? Todos los textos sobre el tema simplemente afirman que no se puede hacer. No estoy convencido (sin haberlo probado yo mismo).

¿Conoces alguna modificación que permita a DFS encontrar las rutas más cortas en gráficos no ponderados? Si no, ¿qué tiene el algoritmo que lo hace tan difícil?

El gato no divertido
fuente
1
El algoritmo de búsqueda de ruta más común en gráficos no ponderados es A *, con la ligera modificación de que los lazos se rompen más cerca del final. Esto le dará un algoritmo similar a DFS, ya que primero probará la ruta más directa y solo burbujeará hacia afuera si es necesario.
BlueRaja - Danny Pflughoeft
1
Intente usar DFS en algunos gráficos (bien elegidos); Si realmente no funciona, debería encontrar problemas. Por cierto, su pregunta se lee como si funcionara en gráficos ponderados.
Raphael
Si, puedes hacerlo. Aquí está la solución
Anmol Middha

Respuestas:

12

El único elemento de búsqueda de profundidad que modifica es el orden en que se investigan los niños. La versión normal procede en orden arbitrario, es decir, en el orden en que se almacenan los elementos secundarios.

La única alternativa factible (hacia los caminos más cortos) que se me ocurre es un enfoque codicioso, que es mirar a los niños en orden de distancia desde el nodo actual (de pequeño a grande). Es fácil construir un contraejemplo para esta regla:

ejemplo contrario para la regla codiciosa
[ fuente ]

Ahora, eso no es una prueba de que no exista una estrategia para elegir el próximo hijo a investigar, lo que hará que DFS encuentre los caminos más cortos.

Sin embargo, sin importar la regla, puede construir gráficos que tengan DFS comprometido con un desvío largo en el primer nodo, tal como lo hice para la regla codiciosa. Bordes Asignar y los pesos de tal manera que los elige de reglas para visitar primera, y asignar un mayor peso que el de . Por lo tanto, es plausible que DFS nunca pueda encontrar rutas más cortas (en gráficos generales).( s , a ) a ( a , b ) ( s , t )(s,t)(s,a)a(a,b)(s,t)

Tenga en cuenta que, dado que puede expresar cada gráfico ponderado (entero positivo) como gráfico no ponderado, simplemente reemplace los bordes con costo con una cadena con nodos , los mismos ejemplos tratan con DFS en gráficos no ponderados. Aquí, la situación es aún más sombría: sin pesas, ¿qué puede usar DFS para determinar el próximo niño a visitar?c - 1cc1


  1. Mientras la regla sea determinista. Si no es así, claramente no siempre puede encontrar los caminos más cortos.
Rafael
fuente
Corríjame si me equivoco, pero ¿significa esto que DFS puede encontrar la ruta más corta en cualquier gráfico, pero tomará un tiempo exponencial al hacerlo?
Anmol Singh Jaggi
@AnmolSinghJaggi No. DFS solo encuentra una ruta.
Raphael
10

Breadth -first-search es el algoritmo que encontrará las rutas más cortas en un gráfico no ponderado.

Hay un simple ajuste para pasar de DFS a un algoritmo que encontrará las rutas más cortas en un gráfico no ponderado. Esencialmente, reemplaza la pila utilizada por DFS con una cola. Sin embargo, el algoritmo resultante ya no se llama DFS. En su lugar, habrá implementado la búsqueda de amplitud primero.

El párrafo anterior da una intuición correcta, pero simplifica demasiado la situación un poco. Es fácil escribir código para el cual el simple intercambio proporciona una implementación de búsqueda de amplitud, pero también es fácil escribir código que al principio parece una implementación correcta pero en realidad no lo es. Puede encontrar una pregunta relacionada con CS.SE sobre BFS vs DFS aquí . Puede encontrar un buen pseudocódigo aquí.

Joe
fuente
3

¡¡¡Usted puede!!!

Marque los nodos como visitados mientras avanza y desmarque mientras regresa, mientras regresa cuando encuentre que otra (s) rama (s) se repiten.

Guarde el costo / ruta para todas las búsquedas posibles donde encontró el nodo objetivo, compare todos los costos / ruta y elija el más corto.

El gran problema (y quiero decir GRANDE) con este enfoque es que visitaría el mismo nodo varias veces, lo que hace que dfs sea una mala elección obvia para el algoritmo de ruta más corta.

usuario2407394
fuente
1
st
1
@ user2407394 ¿Realmente implementó esta variación de DFS una vez y la ejecutó correctamente para un gráfico moderadamente grande? Dudaría en llamar a esta variación como DFS. Yo lo llamaría una búsqueda exhaustiva de primer camino.
John L.
He implementado este tipo de enfoque, funciona muy lento. Estoy pensando en agregar mnemonización para mejorar el rendimiento.
Mic
@ user2407394 parece que funcionaría, pero ¿cómo verifica cuándo detenerse ya que no habría una lista de 'visitados' si los desmarca?
Joe Black
0

BFS tiene una buena propiedad de que verificará todos los bordes desde la raíz y mantendrá la distancia desde la raíz a los otros nodos lo más mínima posible, pero dfs simplemente salta al primer nodo adyacente y va en profundidad. PUEDE modificar DFS para obtener el camino más corto, pero solo terminará en un algoritmo que será de mayor complejidad temporal o terminará haciendo lo mismo que BFS

vikkyhacks
fuente
-3

Es posible encontrar la ruta entre dos vértices con el número mínimo de aristas usando DFS. podemos aplicar un enfoque de nivel

Abereham Wodajia
fuente
2
Por favor, da más detalles. No puedo decir qué algoritmo estás tratando de describir en esta sola oración.
David Richerby
-3

Usted puede

solo recorra el gráfico de manera dfs y verifique

if(distance[dest] > distance[source]+cost[source_to_destination]){
    distance[dest] = distance[source] + cost[source_to_destination]);
}

Aquí está el enlace para la solución completa

Anmol Middha
fuente
1
La respuesta aceptada afirma que esto no es posible, lo que contradice su reclamo. ¿Puede explicar por qué cree que, sin embargo, este enfoque funciona? (o explique por qué este enfoque funciona en general)
Lagarto discreto
¿No es simplemente repetir la respuesta de user2407394 , sólo que con difíciles de entender el código (no se ha definido lo que cualquiera de esas variables significan, y no es obvio, a mí) en lugar de una explicación?
David Richerby
Sí, es la implementación de la respuesta del usuario 2407394. Disculpe las molestias. He agregado comentarios en el código. Puedes verificarlo ahora.
Anmol Middha