Todos los demás que comparan esto con el problema del vendedor ambulante probablemente no hayan leído su pregunta con atención. En TSP, el objetivo es encontrar el ciclo más corto que visita 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 mirar la ruta más corta desde 'start' a 'end' 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, ese no es un código real, y si desea la ruta real, tendrá que realizar 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 ya entiende la idea).
Se ejecutará como máximo en unos pocos segundos en cualquier lenguaje razonable :)
[Si tiene n nodos y k nodos 'mustpass', su tiempo de ejecución es O (n 3 ) para la parte Floyd-Warshall, y O (k! N ) para la parte de todas las permutaciones, y 100 ^ 3 + (¡12!) (100) son prácticamente cacahuetes a menos que tenga algunas restricciones realmente restrictivas.]
aactravésb. Puede ser que los caminos más cortos debaayccomparten un borde. En ese caso, el borde se repetiría dos veces. Uno de los dos caminos debería ser peor que el óptimo para no generar ciclos.INF, la línea sed[i][j] = min(d[i][j], d[i][k] + d[k][j])convierte end[i][j] = min(INF, INF + INF)y todas las celdas siempre permanecen iguales aINF. Debe agregar un paso para llenar esta matriz con las longitudes de los bordes del gráfico.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 de profundidad primero debería indicarle la ruta más corta a través del subgrafo resultante que toca todos los nodos de inicio. .debepasses ... fin
fuente
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, final, debe pasar). 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 búsqueda de rutas que puede utilizar para encontrar la ruta más corta aquí.
Sin embargo, una vez que tenga este nuevo gráfico, tendrá exactamente el problema del vendedor ambulante (bueno, casi ... No es necesario volver al punto de partida). Se aplicará cualquiera de las publicaciones relativas a esto, mencionadas anteriormente.
fuente
En realidad, el problema que publicaste es similar al del vendedor ambulante, pero creo que se acerca más a 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í.
De hecho, recomendaría A * pathfinding como técnica a considerar. Esto se configura al decidir qué nodos tienen acceso a qué otros nodos directamente y cuál es el "costo" de cada salto desde un nodo en particular. En este caso, parece que cada "salto" podría tener el mismo costo, ya que sus nodos parecen estar relativamente cerca. 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 que utilice la búsqueda de caminos no estaría de más.
Solo una alternativa a considerar. Se parece notablemente al problema del viajante de comercio, y esos son buenos papeles para leer, pero mire más de cerca y verá que solo es demasiado complicado. ^ _ ^ Esto viene de la mente de un programador de videojuegos que se ha ocupado de este tipo de cosas antes.
fuente
Andrew Top tiene la idea correcta:
1) Algoritmo de Djikstra 2) Alguna heurística de TSP.
Recomiendo la heurística de Lin-Kernighan: es una de las más conocidas para 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 hacer un cortocircuito en ellos (observe el grado de vértices a lo largo de su ruta).
En realidad, no estoy seguro de qué tan buena será esta solución en relación con la óptima. Probablemente existan algunos casos patológicos relacionados con los 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 el de Kruskal, por ejemplo.
fuente
Este no es un problema de TSP ni 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 a la fuerza bruta después de compilar una lista de las rutas más cortas entre todos los nodos obligatorios a través del algoritmo de Dijkstra. Puede haber una mejor manera de hacerlo, pero una simple sería simplemente trabajar un árbol binario al revés. Imagina una lista de nodos [inicio, a, b, c, final]. Sume las distancias simples [inicio-> a-> b-> c-> final] esta es su nueva distancia objetivo a batir. Ahora intente [start-> a-> c-> b-> end] y si eso es mejor, establezca eso como el objetivo (y recuerde que vino de ese patrón de nodos). Trabajar al revés sobre las permutaciones:
Uno de ellos 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 ayb puede contener c o incluso el punto final. No es necesario que te importe )
fuente
Teniendo en cuenta que la cantidad de nodos y bordes es relativamente finita, probablemente pueda calcular todos los caminos posibles y tomar el más corto.
Generalmente esto se conoce como el problema del viajante de comercio y tiene un tiempo de ejecución polinomial no determinista, independientemente del algoritmo que utilice.
http://en.wikipedia.org/wiki/Traveling_salesman_problem
fuente
La pregunta habla de un pase obligatorio en CUALQUIER orden . He estado tratando de buscar una solución sobre el orden definido de los nodos obligatorios. Encontré mi respuesta, pero como ninguna pregunta en StackOverflow tenía una pregunta similar, la estoy publicando aquí para que la mayoría de las personas se beneficien de ella.
Si se define el orden o el paso obligado, puede ejecutar el algoritmo de dijkstra varias veces. Por ejemplo supongamos que usted tiene que empezar de
spaso a travésk1,k2yk3(en orden respectivo) y parada ene. Entonces, lo que podría hacer es ejecutar el algoritmo de dijkstra entre cada par consecutivo de nodos. El costo y la ruta vendrían dados por:dijkstras(s, k1) + dijkstras(k1, k2) + dijkstras(k2, k3) + dijkstras(k3, 3)fuente
¿Qué tal si se usa la fuerza bruta en la docena de nodos que deben visitarse? Puede cubrir todas las combinaciones posibles de 12 nodos con bastante 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 hasta el circuito, que luego sigue hasta que los ha cubierto, y luego encuentra la ruta desde allí hasta el final.
El camino final está compuesto por:
inicio -> ruta al circuito * -> circuito de nodos de visita obligada -> ruta al final * -> final
Encuentra los caminos que marqué con * así
Haga una búsqueda A * desde el nodo de inicio hasta 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 el circuito en cualquier dirección) terminan con muchas rutas de búsqueda, y puede elegir la que tenga el costo más bajo.
Hay mucho espacio para la optimización almacenando en caché las búsquedas, pero creo que esto generará buenas soluciones.
Sin embargo, no se acerca a buscar una solución óptima, porque eso podría implicar dejar el circuito de visita obligada dentro de la búsqueda.
fuente
Una cosa que no se menciona en ninguna parte es si está bien que el mismo vértice se visite más de una vez en la ruta. La mayoría de las respuestas aquí asumen que está bien para visitar el mismo borde varias veces, pero mi versión dada a la pregunta (un camino no debe visitar el mismo vértice más de una vez!) Es que es no está bien para visitar el mismo vértice dos veces.
Por lo tanto, se seguiría aplicando un enfoque de fuerza bruta, pero tendría que eliminar los vértices ya utilizados cuando intente calcular cada subconjunto de la ruta.
fuente