El algoritmo de Dijsktra aplicado al problema del vendedor ambulante

13

Soy un novato (novato total en la teoría de la complejidad computacional) y tengo una pregunta.

Digamos que tenemos 'Problema de vendedor ambulante', ¿lo resolverá la siguiente aplicación de los Algoritmos de Dijkstra?

Desde un punto de inicio calculamos la distancia más corta entre dos puntos. Vamos al punto Eliminamos el punto de origen. Luego calculamos el siguiente punto de menor distancia desde el punto actual y así sucesivamente ...

Cada paso hacemos el gráfico más pequeño mientras movemos el siguiente punto de menor distancia disponible. Hasta que visitemos todos los puntos.

¿Esto resolverá el problema del vendedor ambulante?

Gilles 'SO- deja de ser malvado'
fuente
3
Tenga en cuenta que TSP es NP-complete y el algoritmo de Dijkstra tiene tiempo de ejecución polinomial. ¿Qué propones sería una solución próxima a trivial de P = NP? pregunta, por lo que es poco probable que su enfoque funcione. ¡Este tipo de razonamiento es solo una mente heurística!
Raphael

Respuestas:

24

El algoritmo de Dijkstra devuelve un árbol de ruta más corta, que contiene la ruta más corta desde un vértice inicial hasta el otro vértice, pero no necesariamente las rutas más cortas entre los otros vértices, o una ruta más corta que visita todos los vértices.

Aquí hay un contraejemplo donde el algoritmo codicioso que describe no funcionará:

contraejemplo

a[a,b,c,d,a]a[a,b,d,c,a]a,b,c,dd,a para volver a la ciudad de inicio.

Joe
fuente
8

Como ya resultó en las otras respuestas, su sugerencia no resuelve eficazmente el problema del vendedor ambulante, permítame indicarle la mejor manera conocida en el campo de la búsqueda heurística (ya que veo el algoritmo de Dijkstra algo relacionado con este campo de inteligencia artificial) .

(u,v)(v,u)

El mejor enfoque (que yo sepa) consiste en ejecutar un algoritmo de búsqueda heurística Profund-First Branch-and-Bound donde la heurística es el costo del Árbol de expansión mínima (MST). Dado que el MST se puede calcular en tiempo polinómico con el algoritmo de Prim o el algoritmo de Kruskal , entonces se puede esperar que devuelva soluciones en un período de tiempo razonable. Para una discusión maravillosa de estos dos algoritmos, le sugiero que eche un vistazo al Manual de diseño de algoritmos

De hecho, permítanme destacar que, dado que se sugirió este enfoque, no se ha visto mucho progreso en el campo para derivar los límites óptimos de este problema, por lo que considero que es una pregunta candente en el campo de la búsqueda combinatoria.

Espero que esto ayude,

Carlos Linares López
fuente
2

No tengo idea de cómo alguien aquí no se dio cuenta de que la aplicación del algoritmo de Dijkstra sería completamente innecesaria en este caso. Puede implementar este algoritmo codicioso simplemente seleccionando el nodo más cercano, que se conoce a priori. El algoritmo de Dijkstra se usa para descubrir rutas, pero solo estás dando un solo paso cada vez. Obviamente, esto no encuentra la solución óptima para el TSP, pero muchos enfoques muy buenos tampoco la encuentran. Todos los buscadores de soluciones óptimas para TSP son muy exigentes computacionalmente.

Luke Schwartzkopff
fuente
1

La respuesta es no, esa no es una buena manera de resolver el problema de TSP. Un buen ejemplo de contador es donde todos los puntos están en una línea, como los siguientes:

--5 ------------------ 3 ----- 1--0 --- 2 ---------- 4

usando el algoritmo de Dijsktra, el vendedor pobre comenzaría en el punto 0, primero iría a 1, luego a 2 y luego a 3 ect. Que no es lo óptimo.

Espero que ayude. Eche un vistazo al primer capítulo del excelente libro de Steven S. Skiena llamado "El diseño del algoritmo", explica este ejemplo con más detalle.

El problema de TSP no es encontrar el camino más corto entre dos puntos, sino hacer una ruta entre todos los puntos que son óptimos. Cuando tenga la ruta óptima, puede usar Dijsktra para encontrar la ruta más corta entre cada punto de la ruta.

Kim.Net
fuente
2
Dijkstra es un algoritmo de ruta más corta de una sola fuente, pero no "haría" que el vendedor comenzara en 0, ni devolvería una ruta. Simplemente devuelve el árbol de ruta más corta, que contiene la ruta más corta a cada vértice desde el vértice de origen dado.
Joe
Tradicionalmente, el problema de TSP [ en.wikipedia.org/wiki/… ] es "Dada una lista de ciudades y sus distancias por pares, la tarea es encontrar la ruta más corta posible que visite cada ciudad exactamente una vez y regrese a la ciudad de origen. " Técnicamente, no es posible satisfacer esos requisitos en un camino; no debe volver a la ciudad de inicio ni repetir ciudades.
Joe
Sin embargo, en un camino, si atenuamos cualquiera de esas restricciones, entonces el problema es trivial.
Joe
Por supuesto, Dijkstra no haría que el vendedor comenzara en 0. Pero el algoritmo propuesto en la pregunta original no especificaba un vértice de inicio; por lo tanto, el algoritmo propuesto podría obligar al vendedor pobre a comenzar en 0. Entonces, esta respuesta es correcta.
JeffE