Pregunta ¿Cuál es la diferencia entre Traveling Salesman y finding Shortest Path?


La única diferencia que se me ocurre para la pregunta es que en el problema del vendedor ambulante (TSP) Necesito encontrar un permutación mínima de todos los vértices en el gráfico y en el problema de Rutas más cortas no hay necesidad de considerar todos los vértices que podemos buscar en el espacio de estados para las rutas de longitud de ruta mínima. Cualquiera puede sugerir más diferencias.


32
2017-10-14 05:28


origen


Respuestas:


Ya ha llamado la diferencia esencial: el TSP es encontrar un camino que contiene una permutación de cada nodo en el gráfico, mientras que en el problema de ruta más corta, cualquier camino más corto dado puede, y a menudo lo hace, contener un apropiado subconjunto 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 cubriendo 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.


36
2017-10-14 05:36



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.


7
2017-10-14 05:48



En TSP, debe visitar todos los nodos y también volver a su punto de partida. Esto complica el problema inmensamente.


1
2017-10-14 05:30



Camino más corto 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 de Bellman-Ford Complejidad del tiempo O (VE)

  • Algoritmo de Floyd-Warshall se usa para encontrar los caminos más cortos entre todos los pares

TSP (problema del viajero que viaja)) no es como que hemos cubierto todos los nodos de la fuente y, finalmente, hemos llegado a la fuente a 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/


1
2017-09-03 14:37