algorithm - 选择哪个节点作为最近邻算法的起始节点

Question

我正在使用最近邻算法来解决旅行商问题。它非常快，但并不准确。我在某处读到了我可以做出的两项改进。第一种不是从一个随机点开始，而是从每个节点开始运行最近邻算法。（所以如果有N个节点，最近邻居运行N次）然后比较并选择总距离最小的路线。这似乎要精确得多。但是太慢了。

另一种方法不是随机选择起始节点，而是选择一个特殊的节点。然后仍然只运行一次最近的邻居以获得结果。这不会像上面的方法那样准确，但肯定要快得多，因为该算法像以前一样只运行一次。但不幸的是，我不记得我在哪里读到那篇文章以及选择这个起始节点的标准。

我猜我应该得到每个节点到其他节点之间的总距离，然后应该选择具有最大值的节点作为起始节点。（用我的话来说，这是选择一个离图表“最远”的节点，同时也避免选择靠近图表中心的节点）我认为这样我得到的路线应该非常接近最佳最短路线。

我想对了吗？

编辑：我正在处理具有欧几里得距离的度量 TSP。

score 1 · Accepted Answer

听起来你可能应该只运行 K-NN 算法，其中几个起始节点说 O(log N)，这只会花费 O(K*N*log(N))。选择最佳路线，然后使用路线改进启发式算法，2 选择或 2.5 选择，限制移动次数或仅限制时间。

这应该可以实现时间与准确性的最佳平衡，除非您开始研究基于k-opt 或 v-opt的算法。虽然，听起来你没有时间陪他们。

score 0 · Accepted Answer

您还可以在每次做最近邻居时进行缓存。如果你做一个 K 最近的邻居会更好。这就是它的工作方式：

2 回答 2