Eu sei que essa é uma pergunta bastante frequente (colher de chá em geral), mas eu já me perco por um tempo. Estou procurando encontrar o caminho hamiltoniano de distância mínima, dado um conjunto de coordenadas x, y. O ponto inicial e final são completamente arbitrários, mas NÃO deve ser alternado, portanto o TSP padrão está fora (embora supostamente adicione um ponto fictício a 0 de distância de todos os outros nós e depois o remova depois funcione, não tenho idéia de como eu faria isso ).

Existem muitos links para trabalhos de matemática e similares, discutindo algoritmos para resolver problemas semelhantes, mas eu prefiro trabalhar com código do que equações complexas e eu realmente prefiro não reinventar a rod

Certamente existe uma implementação bastante direta em uma das principais linguagens java, c #, c ++, ruby, javascript, php, etc, que podem resolver uma versão com ~ 20 nós do meu problem

Editar Também estou procurando o mais preciso possível, obviamente não pode ser completamente preciso como 20! é muitas permutações, mas igual ou melhor do que um humano poderia fazer em alguns minutos seria perfeito.

Edit2: Também para esclarecer, estou trabalhando com coordenadas 2D padrão em um gráfico não ponderado. A distância A-> B == B-> A

Edit3: Para eliminar a confusão, aqui está um exemplo visual com apenas alguns pontos para mostrar como o TSP pode ser abaixo do ideal (esse caso é uma solução fácil, mas com mais nós pode ser mais extremo

TSP menos o segmento mais longo (linha vermelha)

Saída desejada