Algoritmo: ruta más corta entre todos los puntos

Question

Supongamos que tengo 10 puntos. Sé la distancia entre cada punto.

Necesito encontrar la ruta más corta posible pasando por todos los puntos.

He intentado un par de algoritmos (Dijkstra, Floyd Warshall, ...) y todos me dan el camino más corto entre el principio y el final, pero no hacen una ruta con todos los puntos.

Las permutaciones funcionan bien, pero son demasiado costosas en recursos.

¿Qué algoritmos me pueden recomendar que investigue este problema? ¿O hay una forma documentada de hacerlo con los algoritmos mencionados anteriormente?

Answer 1

Eche un vistazo a travelling salesman problem.

Es posible que desee examinar algunos de los heuristic solutions. Es posible que no le puedan dar resultados 100% exactos, pero a menudo pueden encontrar soluciones lo suficientemente buenas (2 a 3% de distancia de las soluciones óptimas) en un tiempo razonable.

Answer 2

Esto es obviamente Travelling Salesman problem. Específicamente para N=10, puede probar el algoritmo ingenuo O(N!), o usar Dynamic Programming, puede reducir esto a O(n^2 2^n), negociando espacio.

Más allá de eso, ya que este es un problema NP-difícil, solo se puede esperar una aproximación o heurística, dadas las advertencias habituales.

Answer 3

Como han mencionado otros, esta es una instancia del TSP. Creo que Concord, desarrollado en Georgia Tech es el actual solucionador de vanguardia. Puede manejar más de 10,000 puntos en pocos segundos. También tiene una API con la que es fácil trabajar.

Answer 4

creo que esto es lo que está buscando, en realidad:

Floyd Warshall

En informática, el algoritmo de Floyd-Warshall (a veces conocido como el WFI Algoritmo [aclaración necesaria], Algoritmo de Roy-Floyd o solo algoritmo de Floyd) es un algoritmo de análisis de gráficos para encontrar las rutas más cortas en un gráfico ponderado (con pesos de borde positivo o negativo). Un sola ejecución del algoritmo se encuentran las longitudes (resumió pesos) de los caminos más cortos entre todos los pares de vértices aunque no devuelve los detalles de los caminos mismos

En la subsección "Ruta de la reconstrucción" se explica la estructura de datos que necesitará para almacenar las "rutas" (en realidad solo almacena el siguiente nodo al que ir y luego reconstruye trivialmente cualquier ruta que se requiera).