2

我正在尝试解决这个问题http://coj.uci.cu/24h/problem.xhtml?abb=1368。

经过大量研究并花费大量时间，我能够为 TSP 实现分支定界算法，该算法得到一条通过所有点并返回开始的路径。

我在想从那条路径中删除最长的边我会得到答案，但是当我完成我的算法时，我发现这并非在所有情况下都是正确的，阅读这个问题：Minimal Distance Hamiltonian Path Javascript

我找到了一些答案，说添加一个与其他点的距离为零的虚拟点，然后删除它可以解决问题，但我不知道具体情况。我已经添加了那个虚拟点，现在不是得到 26.01，而是 16.23 作为答案。我还没有删除虚拟点，因为我不明白“添加虚拟点的全部意义”。

你能指导我解决这个问题吗？还是采用另一种方法而不是 TSP 更好？

4

1 回答 1

1

虚拟点允许您在任意大的距离处连接两端。在 TSP 中，两端也必须彼此非常靠近以最小化总距离。在您的路径问题中，此要求不存在，因此 TSP 最优值对您的问题无效的约束是主观的，因此可能不是您的路径问题的最优值。

如果您引入一个虚拟点（或将其视为一条捷径，一个虫洞），您的两端可能会相距很远，而不会影响您的距离。

于 2012-11-05T08:10:52.310 回答