Sé que esta es una pregunta bastante frecuente (cucharadita en general), pero me he quedado perplejo por un tiempo. Estoy buscando encontrar la distancia mínima del camino hamiltoniano dado un conjunto de coordenadas x, y. Los puntos de inicio y finalización son completamente arbitrarios, pero NO deben alternar, por lo que el tsp estándar está desactivado (aunque supuestamente agregar un punto ficticio a una distancia de 0 a todos los demás nodos y luego eliminarlo más tarde funciona, no tengo idea de cómo lo haría ).

Hay muchos enlaces a documentos de matemáticas y similares que discuten algoritmos para resolver problemas similares, pero prefiero trabajar con código que con ecuaciones complejas y prefiero no reinventar la rueda.

Sin duda, hay una implementación bastante sencilla en un lenguaje principal java, c #, c ++, ruby, javascript, php, etc. que puede resolver una versión de ~ 20 nodos de mi problema.

Editar También estoy buscando lo más preciso posible, ¡obviamente no puede ser tan exacto como 20! son muchas permutaciones, pero igual o mejor que lo que un humano podría hacer en un par de minutos sería perfecto.

Edit2: También para aclarar, estoy trabajando con coordenadas 2D estándar en un gráfico no ponderado. La distancia A-> B == B-> A

Edit3: Para eliminar la confusión, aquí hay un ejemplo visual con solo unos pocos puntos para mostrar cómo tsp puede ser subóptimo (este caso es una solución fácil pero con más nodos puede ser más extremo).

TSP Menos segmento más largo (línea roja)

Salida desead