¿El camino más corto para viajar a cada punto de un conjunto de puntos exactamente una vez, y volver al punto de partida?

Question

¿Existe un algoritmo de tiempo polinómico que encuentre esto?

Sólo me interesa.

Gracias de antemano

edit: En este caso se te da un conjunto de coordenadas cartesianas que representan la distancia física entre ellas.

Answer 1

Según Wikipedia, el Problema del viajante de comercio euclidiano es NP-completo, lo que implica que no existe ningún algoritmo polinómico conocido para encontrar la solución óptima. Sin embargo, la métrica euclidiana simplifica las cosas, facilitando la búsqueda de buenas soluciones aproximadas, como se describe en el artículo de Wikipedia sobre TSP.