算法：所有點之間的最短路徑

Question

假設我有10個點。我知道每個點之間的距離。

我需要找到通過所有點的最短路徑。

我已經嘗試了幾種算法（Dijkstra，Floyd Warshall，...），他們都給我開始和結束之間的最短路徑，但是他們沒有製作一條路線，上面有所有點。

排列工作正常，但它們太耗資源。

什麼算法可以建議我研究這個問題？還是有一種文件化的方式來做到這一點與上述算法？

Answer 1

看一看travelling salesman problem。

你可能想看看一些heuristic solutions。他們可能無法給你100％的確切結果，但他們經常可以在合理的時間內提出足夠好的解決方案（比最佳解決方案少2％到3％）。

Answer 2

這顯然是Travelling Salesman problem。特別是對於N=10，您可以嘗試O(N!)樸素算法或使用Dynamic Programming，您可以通過交易空間將其減少至O(n^2 2^n)。

除此之外，由於這是一個NP難題，因此您只能希望得到一個近似值或啓發式，因爲通常需要注意。

Answer 3

正如其他人所說，這是TSP的一個實例。我認爲在喬治亞理工學院開發的Concord是當前最先進的求解器。它可以在幾秒鐘內處理10,000點以上。它也有一個易於使用的API。

Answer 4

我想這就是你要找的，實際上是：

Floyd Warshall

在計算機科學中，弗洛伊德 - Warshall算法（有時也被稱爲 的WFI算法[澄清需要] Roy-Floyd算法或僅用於Floyd算法）是一種圖表分析算法，用於在加權圖形（具有正或負邊權重）中查找最短路徑。該算法的 單次執行會發現長度（總結 權重）所有對頂點之間的最短路徑雖然 不返回路徑的細節本身

在「路徑重建」小節它解釋了存儲「路徑」所需的數據結構（實際上，您只需存儲下一個要去的節點，然後根據需要輕鬆重建需要的路徑）。