没有三角不等式的TSP求解器

Question

我有兴趣为(小)网格图解决TSP.任何类型的库都可以为我做,但这似乎比预期更难.我尝试了几个我在那里找到的解算器(包括协调器),但是当三角形不等式不成立时,它们似乎都有问题.

例如,我希望求解器为图形输出(0,1,2,1,4,3)(具有单位边缘权重),如下所示:

0-1-2
| |
3-4

在这个特殊情况下,我告诉concorde边缘(2,4)的重量为1000,并且concorde迅速产生了成本1004的巡回赛(0,1,2,4,3).这显然不是我想要的.

理想情况下,Java中会有一些简单的(可能是暴力)实现,但实际上可行的任何东西都可以.任何人都可以指向我一些代码或者我真的必须自己去实现吗？

编辑:同样,重要的是我得到一个精确的解决方案,而不是一些近似.

Edit2:的确,这似乎不是TSP.我想要找到的是一个访问所有顶点的最短的闭路.

Answer 1

你的困难不是三角不等式.困难与您期望的解决方案不是有效的TSP之旅这一事实有关.

TSP寻求汉密尔顿循环 ; 也就是说,一个周期访问每个顶点一次.您的解决方案,(0, 1, 2, 1, 4, 3)访问顶点1两次.

如果这是您正在寻求的解决方案,那么您尝试解决的问题不是旅行商问题.