我对求解（小）网格图的TSP很感兴趣任何类型的图书馆都能帮到我，但这似乎比预期的要难我尝试了一些我发现的解算器（包括协和式飞机），但是当三角不平等不成立时，它们似乎都有问题。
例如，我希望解算器为以下图形（具有单位边权重）输出巡更（0、1、2、1、4、3）：
0-1-2
| |
3-4
在这个特殊的例子中，我告诉协和飞机，Edge（2，4）的重量是1000，协和飞机很快就完成了旅行（0，1，2，4，3），费用是1004美元。这显然不是我要找的。
理想情况下，Java中会有一些简单（可能是蛮力）的实现，但任何有效的实现都会真正起作用有人能告诉我一些代码吗？或者我真的需要自己去实现它吗？
编辑：同样重要的是，我得到一个精确的解决方案，而不是一些近似值。
伊迪丝2：的确，这似乎不是tsp。我试图找到的是一个访问所有顶点的最短闭合行走。
最佳答案
你的困难不是三角不平等。困难在于你期望的解决方案不是一个有效的TSP旅行。
tsp寻找一个Hamiltonian cycle；也就是说，一个恰好访问每个顶点一次的循环。您的解决方案，(0, 1, 2, 1, 4, 3)，访问顶点1两次。
如果这是你正在寻找的解决方案，那么你试图解决的问题不是旅行推销员问题。