El algoritmo de Dijsktra aplicado al problema del vendedor ambulante

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?

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á:

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

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,

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.

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.