algorithm - tools - vehicle routing problem google maps
¿Cuál es la diferencia entre Traveling Salesman y finding Shortest Path? (4)
Con el problema de ruta más corta considera caminos entre dos nodos. Con el TSP, considera las rutas entre todos los nodos. Esto hace que este último sea mucho más difícil.
Considere dos caminos entre los nodos A y B. Uno sobre D el otro de C. Deje que el que está sobre C sea el camino más largo. En el problema de la Ruta más corta, esta ruta puede descartarse inmediatamente. En el TSP es perfectamente posible que este camino sea parte de la solución general, ya que tendrá que visitar C y visitarlo más tarde puede ser aún más costoso.
Por lo tanto, no puede descomponer el TSP en sub-problemas similares pero más pequeños.
La única diferencia que se me ocurrió para la pregunta es que en el Problema de Vendedor Viajero (TSP) necesito encontrar una permutación mínima de todos los vértices en el gráfico y en el problema de Trayectos más cortos no hay necesidad de considerar todos los vértices que podamos buscar en el espacio de estados para las rutas de longitud de ruta mínima puede alguien sugerir más diferencias.
En TSP, debe visitar todos los nodos y también volver a su punto de partida. Esto complica el problema inmensamente.
Ya ha llamado la diferencia esencial: el TSP es encontrar una ruta que contiene una permutación de cada nodo en el gráfico , mientras que en el problema de ruta más corta, cualquier ruta más corta dada puede, y a menudo lo hace, contener un subconjunto apropiado de los nodos en el gráfico.
Otras diferencias incluyen:
- La solución TSP requiere que su respuesta sea un ciclo.
- La solución TSP necesariamente repetirá un nodo en su camino, mientras que una ruta más corta no lo hará (a menos que uno esté buscando el camino más corto desde un nodo hacia sí mismo).
- TSP es un problema NP-completo y el camino más corto es conocido como tiempo polinomial.
Si está buscando una declaración precisa de la diferencia, yo diría que solo necesita reemplazar su idea de la "permuación" con el término más técnico y preciso "ciclo simple que visita cada nodo en el gráfico", o mejor, "ciclo de Hamilton". ":
El TSP requiere que uno encuentre el ciclo simple que cubre cada nodo en el gráfico con el menor peso (alternativamente, el ciclo de Hamilton con el menor peso). El problema de la ruta más corta requiere que uno encuentre la ruta entre dos nodos dados con el menor peso. Los caminos más cortos no necesitan ser hamiltonianos, ni deben ser ciclos.
La ruta más corta es solo tener origen y destino. Necesitamos encontrar la ruta más corta entre ellos, obviamente la salida debe ser en árbol en tiempo polinomial.
Encontrar el camino más corto: -
Gráficos sin dirección: el algoritmo de Dijkstra con la lista O (V ^ 2)
Gráficos dirigidos con pesos arbitrarios sin ciclos negativos: algoritmo Bellman-Ford Complejidad del tiempo O (VE )
El algoritmo de Floyd-Warshall se usa para encontrar los caminos más cortos entre todos los pares
El TSP (Problema del viajero viajero ) no es como que hemos cubierto todos los nodos desde el origen y finalmente hemos llegado a la fuente con un costo mínimo. Eventualmente debe haber un ciclo. TSP es un problema NP-completo
Árbitro:
https://en.wikipedia.org/wiki/Shortest_path_problem
https://en.wikipedia.org/wiki/Travelling_salesman_problem
http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/