Algoritmo de búsqueda de gráficos

Question

Estoy buscando un algoritmo gráfico con algunas propiedades inusuales.

Cada borde del gráfico es un borde "arriba" o un borde "abajo".

Un camino válido puede recorrer un número indefinido de "arriba" seguido de un número indefinido de "abajo", o viceversa.Sin embargo, no puede cambiar de dirección más de una vez.

Por ejemplo, una ruta válida podría ser una "hacia arriba" b "hacia arriba" c "hacia abajo" e "hacia abajo" f un camino inválido podría ser un "hacia arriba" b "hacia abajo" c "up" D

¿Cuál es un buen algoritmo para encontrar el camino válido más corto entre dos nodos?¿Qué tal encontrar todos los caminos más cortos de igual longitud?

Answer 1

Suponiendo que no tenga ninguna heurística, una variación de algoritmo de dijkstra debería bastar bastante bien.Cada vez que considere una nueva ventaja, almacene información sobre sus "antepasados".Luego, verifique la invariante (solo un cambio de dirección) y retroceda si se viola.

Los ancestros aquí son todos los bordes que se atravesaron para llegar al nodo actual, a lo largo del camino más corto.Una buena forma de almacenar la información de los antepasados ​​sería como un par de números.Si U está arriba y D está abajo, los ancestros de una arista en particular podrían ser UUUDDDD, cual seria la pareja 3, 4.No necesitarás un tercer número debido a la invariante.

Dado que hemos utilizado el algoritmo de Dijkstra, ya hemos solucionado el problema de encontrar múltiples caminos más cortos.

Answer 2

Tal vez puedas transformar tu gráfico en un gráfico dirigido normal y luego usar los algoritmos existentes.

Una forma sería dividir el gráfico en dos gráficos, uno con todos los bordes superiores y otro con todos los bordes inferiores y con bordes dirigidos entre todos los nodos del gráfico uno y el nodo correspondiente del gráfico dos.

Primero resuelva comenzando en el gráfico uno y terminando en el gráfico dos y luego al revés, luego verifique la solución más corta.

Answer 3

Uno pensaría que tu estándar BFS debería funcionar aquí.Siempre que agregue un nodo a la lista abierta, puede envolverlo en una estructura que indique qué dirección está usando (arriba o abajo) y una bandera booleana que indique si ya ha cambiado de dirección.Estos se pueden utilizar para determinar qué bordes salientes de ese nodo son válidos.

Para encontrar todos los caminos más cortos de igual longitud, incluya el número de aristas recorridas hasta el momento en su estructura.Cuando encuentre su primera ruta más corta, tome nota de la longitud de la ruta y deje de agregar nodos a la lista abierta.Continúe repasando los nodos restantes de la lista hasta que haya verificado todas las rutas de la longitud actual, luego deténgase.

Answer 4

A* con una función de costo (puntuación G) y heurística (puntuación H) especialmente diseñada puede manejarlo.

Para el costo, podría realizar un seguimiento del número de cambios de dirección en el camino y agregar un costo infinito en el segundo cambio (es decir,cortar la búsqueda de esas ramas).

La heurística requiere un poco más de reflexión, especialmente cuando se quiere mantener la heurística admisible (nunca sobreestima la distancia mínima a la meta) y monótona.(La única forma de garantizar que A* encuentre una solución óptima).

¿Quizás haya más información sobre el dominio disponible para crear la heurística?(es decir.¿Coordenadas x,y de los nodos en el gráfico?)

Por supuesto, dependiendo del tamaño del gráfico que desee resolver, primero puede probar algoritmos más simples como la búsqueda en amplitud o el algoritmo de Dijkstra:Básicamente, todos los algoritmos de búsqueda servirán, y para cada uno necesitará una función de costo (o similar) de todos modos.

Answer 5

Si tiene una función de búsqueda de gráficos estándar, digamos Graph.shortest(from, to) en una biblioteca, puede realizar un bucle y minimizar, en C#/pseudocódigo:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

Si necesita recordar la(s) ruta(s) mínima(s) y sucede que su función estándar le devuelve los datos, también puede pronunciar

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

dónde myMin debería comparar dos [fst, nxt, C, AC, BD] tuplas y dejar la que tiene menor distancia, o ambas y asumiendo reduce Es una función inteligente.

Esto tiene cierta sobrecarga de memoria si nuestros gráficos son grandes y no usan memoria en absoluto (lo cual es posible si se generan dinámicamente), pero en realidad no hay sobrecarga de velocidad, en mi humilde opinión.