Algoritmo de búsqueda de gráficos

Question

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

Cada borde en el gráfico es un borde "hacia arriba" o un borde "hacia abajo".

Una ruta válida puede ir por un número indefinido de "arriba" seguido por 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 un "arriba" B "hasta" C "hacia abajo" E "hacia abajo" F una ruta no válida podría ser un "arriba" B "hacia abajo" C "hasta" D

¿Cuál es un buen algoritmo para encontrar la ruta válida más corta entre dos nodos? ¿Qué hay de encontrar todos los caminos más cortos de igual longitud?

Answer 1

Suponiendo que no tiene ninguna heurística, una variación de dijkstra's algorithm debería bastar bastante bien. Cada vez que considere una nueva ventaja, almacene información sobre sus "antepasados". Luego, verifica el invariante (solo un cambio de dirección) y retrocede si se infringe.

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

Como hemos utilizado el algoritmo de dijkstra, ya se ha solucionado la búsqueda de varias rutas más cortas.

Answer 2

Tal vez pueda transformar su gráfico en un gráfico dirigido normal y luego usar algoritmos existentes.

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

Primero resuelva para comenzar en el gráfico uno y termine en el gráfico dos y luego al revés, luego marque la solución más corta.

Answer 3

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

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

Answer 4

A* con un costo especialmente diseñado (puntuación G) y la función heurística (puntuación H) puede manejarlo.

Por el costo, puede realizar un seguimiento del número de cambios de dirección en la ruta y agregar un costo infinito en el segundo cambio (es decir, cortar la búsqueda de esas ramas).

La heurística toma un poco más de reflexión, especialmente cuando se quiere mantener la heurística admisible (nunca sobrestima la distancia mínima al objetivo) y monótona. (La única forma de garantizar A * encuentra una solución óptima.)

¿Tal vez hay más información sobre el dominio disponible para crear la heurística? (es decir, x, y las coordenadas de los nodos en el gráfico?)

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

Answer 5

Si usted tiene una función de búsqueda gráfica estándar, por ejemplo Graph.shortest(from, to) en una biblioteca, puede recorrer 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 es necesario recordar la ruta/caminos mínimos y que por lo sucede que la función de su nivel de calidad que los datos devuelve, también se 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) 

donde myMin debe comparar dos [fst, nxt, C, AC, BD] tuplas y dejar el que tiene menor distancia, o ambos, y asumiendo reduce es una función inteligente.

Esto tiene un poco de 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 sobrecarga la velocidad, imho.