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

Question

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

Necesito encontrar la ruta más corta a través de este gráfico que comience en 'inicio', termine en 'final', y pase por 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

Todos los demás que comparan esto con el Problema del vendedor viajero probablemente no han leído su pregunta con cuidado. En TSP, el objetivo es encontrar el ciclo más corto que visite todos los vértices (un ciclo hamiltoniano); corresponde a tener cada nodo etiquetado como 'mustpass'.

En su caso, dado que solo tiene alrededor de una docena etiquetada como 'mustpass', ¡y dado que 12! es bastante pequeño (479001600), simplemente puede probar todas las permutaciones de solo los nodos 'mustpass' y observar la ruta más corta desde 'start' hasta 'end' que visita los nodos 'mustpass' en ese orden: simplemente ser la concatenación de los caminos más cortos 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 más simple de codificar el algoritmo Floyd-Warshall se ejecutará a tiempo). Luego, una vez que tenga esto en una tabla, intente 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, ese no es un código real, y si desea la ruta real, tendrá que hacer un seguimiento de qué permutación proporciona la distancia más corta y también cuáles son las rutas más cortas de todos los pares, pero se entiende la idea. )

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

Answer 2

ejecute Algoritmo de Djikstra para encontrar las rutas más cortas entre todos los nodos críticos (inicio, fin , y debe pasar), entonces un recorrido transversal primero debe indicarle el camino más corto a través del subgrafo resultante que toca todos los nodos inicio ... debe pasar ... finalizar

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 búsqueda de caminos. En lugar de tener que visitar todos y cada uno de los nodos, simplemente necesita visitar un conjunto particular de nodos en el menor tiempo (distancia) posible.

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 en el mapa sin necesidad de pasar por otros nodos para llegar allí.

En realidad, recomendaría la búsqueda de rutas A * como una técnica a considerar. Usted configura esto al decidir qué nodos tienen acceso a qué otros nodos directamente, y cuál es el "costo". de cada salto de un nodo particular es. En este caso, parece que cada '' salto '' podría tener el mismo costo, ya que sus nodos parecen estar relativamente poco separados. A * puede usar esta información para encontrar la ruta de menor costo entre dos puntos. Dado que necesita ir del punto A al punto B y visitar aproximadamente 12 en el medio, incluso un enfoque de fuerza bruta utilizando la búsqueda de caminos 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 mira más de cerca y verás que son cosas muy complicadas. ^ _ ^ Esto viene de la mente de un programador de videojuegos que se ha ocupado de este tipo de cosas antes.

Answer 4

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

Primero debe descubrir las rutas más cortas entre todos sus nodos críticos (inicio, fin, paso obligatorio). Una vez que se descubren estos caminos, puede construir un gráfico simplificado, donde cada borde en el nuevo gráfico es un camino desde un nodo crítico a otro en el gráfico original. Hay muchos algoritmos de búsqueda de rutas que puede usar para encontrar la ruta más corta aquí.

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

Answer 5

Andrew Top tiene la idea correcta:

1) Algoritmo de Djikstra 2) Algunos TSP heurísticos.

Recomiendo la heurística de Lin-Kernighan: es una de las más conocidas por cualquier problema de NP Complete. Lo único que debe recordar es que después de expandir el gráfico nuevamente después del paso 2, es posible que tenga bucles en su ruta expandida, por lo que debe dar un cortocircuito (ver el grado de vértices a lo largo de su ruta).

No estoy seguro de cuán buena será esta solución en relación con la óptima. Probablemente hay algunos casos patológicos relacionados con cortocircuitos. Después de todo, este problema se parece MUCHO a Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree y definitivamente no puede aproximarse a Steiner Tree simplemente contrayendo su gráfico y ejecutando Kruskal's, por ejemplo.

Answer 6

Esto es no un problema de TSP y no NP-hard porque la pregunta original no requiere que los nodos de paso obligatorio se visiten solo una vez. Esto hace que la respuesta sea mucho, 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 obligatorio 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]. Suma las distancias simples [inicio- > a- > b- > c- > end], esta es tu nueva distancia objetivo para vencer. Ahora intente [inicio- > a- > c- > b- > end] y, si eso es mejor, defínalo como objetivo (y recuerde que proviene de ese patrón de nodos). Trabaja hacia atrás sobre las permutaciones:

• [inicio- > a- > b- > c- > end]
• [inicio- > a- > c- > b- > end]
• [inicio- > b- > a- > c- > end]
• [inicio- > b- > c- > a- > end]
• [inicio- > c- > a- > b- > end]
• [inicio- > c- > b- > a- > end]

Uno de esos será el más corto.

(¿dónde están los nodos "visitados varias veces", si los hay? Simplemente están ocultos en el paso de inicialización de la ruta más corta. La ruta más corta entre a y b puede contener c o incluso el punto final. Usted no necesita preocuparse)

Answer 7

Teniendo en cuenta que la cantidad de nodos y bordes es relativamente finita, probablemente pueda calcular cada ruta posible y tomar la más corta.

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

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

Answer 8

¿Qué tal si usas la fuerza bruta en la docena de nodos 'must visit'? Puede cubrir todas las combinaciones posibles de 12 nodos con la suficiente facilidad, y esto le deja con un circuito óptimo que puede seguir para cubrirlos.

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

La ruta final se compone de:

inicio - > ruta al circuito * - > circuito de visita obligada nodos - > camino al final * - > fin

Encuentra las rutas que marqué con * como esta

Haga una búsqueda A * desde el nodo de inicio a cada punto del circuito para cada uno de estos, haga una búsqueda A * desde el nodo siguiente y anterior en el circuito hasta el final (porque puede seguir la ronda del circuito en cualquier dirección) Con lo que terminas es con muchas rutas de búsqueda, y puedes elegir la que tenga el costo más bajo.

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

Sin embargo, no llega a buscar una solución óptima, ya que eso podría implicar abandonar el circuito de visita obligada dentro de la búsqueda.

Answer 9

Una cosa que no se menciona en ninguna parte, es si está bien que se visite 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 opinión dada la pregunta (¡una ruta no debe 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.