algorithm - guia - Encuentre la ruta más corta en un gráfico que visita ciertos nodos

qgis manual

Question

Tengo un gráfico no dirigido con aproximadamente 100 nodos y alrededor de 200 bordes. Un nodo está etiquetado como ''inicio'', uno es ''final'', y hay alrededor de una docena etiquetados como ''paso obligado''.

Necesito encontrar el camino más corto a través de este gráfico que comienza en ''inicio'', termina en ''fin'' y pasa a través de todos los nodos ''mustpass'' (en cualquier orden).

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt es el gráfico en cuestión, representa un laberinto de maíz en Lancaster, PA)

Answer 1

¿Qué hay de usar la fuerza bruta en la docena de nodos ''debe visitar''. Puede cubrir todas las combinaciones posibles de 12 nodos con la suficiente facilidad, y esto le deja un circuito óptimo que puede seguir para cubrirlos.

Ahora su problema se simplifica para encontrar rutas óptimas desde el nodo de inicio hasta el circuito, que luego seguirá hasta que las haya cubierto y luego encuentre la ruta desde ese punto hasta el final.

La ruta final se compone de:

start -> path to circuit * -> circuito de visita obligada nodos -> path to end * -> end

Encuentra los caminos que marqué con * como este

Haz una búsqueda A * desde el nodo de inicio hasta cada punto del circuito para cada uno de ellos haz una búsqueda A * desde el nodo siguiente y anterior en el circuito hasta el final (porque puedes seguir el circuito en cualquier dirección). terminará con una gran cantidad de rutas de búsqueda, y puede elegir la que tenga el menor costo.

Hay mucho espacio para la optimización al almacenar en caché las búsquedas, pero creo que esto generará buenas soluciones.

Sin embargo, no se trata de buscar una solución óptima, porque eso podría implicar dejar el circuito de visita obligada dentro de la búsqueda.

Answer 2

Andrew Top tiene la idea correcta:

1) Algoritmo de Djikstra 2) Alguna heurística TSP.

Recomiendo la heurística de Lin-Kernighan: es una de las más conocidas por cualquier problema de NP Complete. La única otra cosa para recordar es que después de expandir el gráfico nuevamente después del paso 2, es posible que tengas bucles en tu camino expandido, por lo que deberías ir cortocircuitando esos (mira el grado de vértices a lo largo de tu camino).

De hecho, no estoy seguro de cuán buena será esta solución en relación con la óptima. Probablemente haya algunos casos patológicos relacionados con el cortocircuito. Después de todo, este problema se ve MUCHO como Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree y definitivamente no puedes aproximarte a Steiner Tree simplemente contratando tu gráfica y ejecutando Kruskal''s por ejemplo.

Answer 3

En realidad, el problema que publicaste es similar al del vendedor ambulante, pero creo que está más cerca de un simple problema de ruta de acceso. En lugar de necesitar visitar cada nodo, simplemente necesita visitar un conjunto particular de nodos en el menor tiempo posible (distancia).

La razón de esto es que, a diferencia del problema del vendedor ambulante, un laberinto de maíz no le permitirá viajar directamente de un punto a otro punto del mapa sin necesidad de atravesar otros nodos para llegar allí.

De hecho, recomendaría A * pathfinding como una técnica a considerar. Usted configura esto al decidir qué nodos tienen acceso directamente a qué otros nodos, y cuál es el "costo" de cada salto de un nodo en particular. En este caso, parece que cada "salto" podría tener el mismo costo, ya que sus nodos parecen estar relativamente poco espaciados. A * puede usar esta información para encontrar la ruta de menor costo entre dos puntos. Ya que necesita ir del punto A al punto B y visitar aproximadamente 12 entremedias, incluso un enfoque de fuerza bruta usando el pathfinding no dolería en absoluto.

Solo una alternativa a considerar. Se parece notablemente al problema del vendedor ambulante, y esos son buenos documentos para leer, pero mire más de cerca y verá que son solo cosas complicadas. ^ _ ^ Esto viene de la mente de un programador de videojuegos que ya ha lidiado con este tipo de cosas.

Answer 4

Este no es un problema de TSP ni NP-hard porque la pregunta original no requiere que los nodos de must-pass se visiten solo una vez. Esto hace que la respuesta sea mucho más simple que la fuerza bruta después de compilar una lista de rutas más cortas entre todos los nodos de paso obligado a través del algoritmo de Dijkstra. Puede haber una mejor manera de hacerlo, pero una simple sería simplemente trabajar un árbol binario hacia atrás. Imagine una lista de nodos [inicio, a, b, c, final]. Sume las distancias simples [inicio-> a-> b-> c-> fin] esta es su nueva distancia objetivo a vencer. Ahora pruebe [start-> a-> c-> b-> end] y, si es mejor, configúrelo como objetivo (y recuerde que proviene de ese patrón de nodos). Trabaja hacia atrás sobre las permutaciones:

• [inicio-> a-> b-> c-> fin]
• [inicio-> a-> c-> b-> final]
• [inicio-> b-> a-> c-> fin]
• [inicio-> b-> c-> a-> final]
• [inicio-> c-> a-> b-> final]
• [inicio-> c-> b-> a-> final]

Uno de ellos será el más corto.

(¿Dónde están los nodos visitados varias veces, si hay alguno? Simplemente están ocultos en el paso de inicialización de la ruta más corta. La ruta más corta entre ayb puede contener c o incluso el punto final. No es necesario que se preocupe )

Answer 5

Estos son dos problemas ... Steven Lowe señaló esto, pero no le dio suficiente respeto a la segunda mitad del problema.

Primero debe descubrir las rutas más cortas entre todos sus nodos críticos (inicio, final, paso obligado). Una vez que se descubren estas rutas, puede construir un gráfico simplificado, donde cada borde en el nuevo gráfico es una ruta de un nodo crítico a otro en el gráfico original. Hay muchos algoritmos de identificación de ruta que puede usar para encontrar la ruta más corta aquí.

Sin embargo, una vez que tenga este nuevo gráfico, tendrá exactamente el problema del vendedor itinerante (bueno, casi ... No es necesario volver a su punto de partida). Se aplicará cualquiera de las publicaciones relacionadas con esto, mencionadas anteriormente.

Answer 6

Hubiera sido agradable decirnos si el algoritmo debería ejecutarse en aproximadamente un segundo, un día, una semana más o menos :) Si una semana está bien y es de una sola vez, puede escribir un software en algunas horas y usarlo como fuerza bruta . Pero si está integrado en una interfaz de usuario y debe calcularse muchas veces al día ... creo que hay otro problema.

Answer 7

Teniendo en cuenta que la cantidad de nodos y bordes es relativamente finita, probablemente puedas calcular todas las rutas posibles y tomar la más corta.

En general, esto se conoce como el problema del vendedor ambulante y tiene un tiempo de ejecución polinomial no determinista, sin importar el algoritmo que utilice.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Answer 8

Una cosa que no se menciona en ninguna parte, es si está bien si se visita el mismo vértice más de una vez en la ruta. La mayoría de las respuestas aquí asumen que está bien visitar el mismo borde varias veces, pero mi respuesta a la pregunta (¡una ruta no debería visitar el mismo vértice más de una vez!) Es que no está bien visitar el mismo vértice dos veces.

Por lo tanto, se seguiría aplicando un enfoque de fuerza bruta, pero tendrías que eliminar los vértices ya utilizados cuando intentes calcular cada subconjunto de la ruta.

Answer 9

ejecute el algoritmo de Djikstra para encontrar las rutas más cortas entre todos los nodos críticos (inicio, final y paso obligado), luego un recorrido en profundidad debería indicarle el camino más corto a través del subgrafo resultante que toca todos los nodos. .paspaspasos ... fin

Answer 10

Todos los que comparan esto con el Problema de Vendedor Viajero probablemente no han leído su pregunta cuidadosamente. En TSP, el objetivo es encontrar el ciclo más corto que visita todos los vértices (un ciclo de Hamilton) - corresponde a tener cada nodo etiquetado como ''mustpass''.

En su caso, dado que solo tiene una docena etiquetada como "paso obligado", ¡y dado que 12! es bastante pequeño (479001600), puedes simplemente probar todas las permutaciones de solo los nodos ''mustpass'', y mirar la ruta más corta desde ''inicio'' hasta ''fin'' que visita los nodos ''mustpass'' en ese orden - simplemente ser la concatenación de las rutas más cortas entre cada dos nodos consecutivos en esa lista.

En otras palabras, primero encuentre la distancia más corta entre cada par de vértices (puede usar el algoritmo de Dijkstra u otros, pero con esos números pequeños (100 nodos), incluso el algoritmo Floyd-Warshall más simple de codificar se ejecutará a tiempo). Luego, una vez que tenga esto en una tabla, pruebe todas las permutaciones de sus nodos ''mustpass'' y el resto.

Algo como esto:

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the ''mustpass'' nodes:
    shortest = min(shortest, d[''start''][a[1]]+d[a[1]][a[2]]+...+d[a[k]][''end''])
print shortest

(Por supuesto que no es un código real, y si quieres el camino real, tendrás que hacer un seguimiento de qué permutación proporciona la distancia más corta, y también cuáles son los caminos más cortos para todos los pares, pero entiendes la idea).

Se ejecutará a lo sumo unos pocos segundos en cualquier lenguaje razonable :)
[Si tiene n nodos y k ''nodos'', su tiempo de ejecución es O (n ³ ) para la parte de Floyd-Warshall, y O (k! N) para la parte de todas las permutaciones, y 100 ^ 3 + (12! ) (100) es prácticamente cacahuetes a menos que tengas algunas restricciones realmente restrictivas.]