哪個節點作爲近鄰算法起始節點選擇

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基於算法。雖然，聽起來不像你有時間。