哪个节点作为近邻算法起始节点选择

Question

http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm

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

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

我猜我应该得到的其他节点的每个节点之间的总距离，则具有最大的值的节点应选择为出发点。 （在我的话，这是选择的“最远”，从图形中的节点，同时也避免选择节点那附近的图形的中心）我觉得这样我得到的路线应该是相当接近最优最短的路线。

我想对吗？

编辑：我处理与欧氏距离度量TSP。

Answer 1

您也可以缓存，每次你做一个近邻。甚至更好，如果你做K最近的邻居。这是如何工作的：

1. 对于每个节点找到K个最近邻居。将其存储在缓存中。
2. 无论何时您需要执行最近的邻居，请先检查缓存。否则，执行最近邻居并将其添加到缓存中。

Answer 2

这听起来像是你应该运行带有几个起始节点的K-NN算法，说O（log N），这只会花费O（K * N * log（N））。选择最佳游览，然后使用游览改进启发式方法，或者选择2 opt或2.5，限制移动次数或仅限时间限制。

这应该允许的时间与准确度的最佳平衡，除非也许你开始看k-opt or v-opt基于算法。虽然，听起来不像你有时间。