查找離開路線集的最小距離

Question

假設我有一組斷開的公路路線，如this example。每條路線有Start和Finish個點，這可能是相同的（如果路線是圓形的）。路線可以是「打開」（不同的開始/結束）或「關閉」（相同的開始/結束）。對於封閉路線，可以將確切的進入/退出點定義爲開始/結束點。

還定義了「全局」START和FINISH點。

如何從「全局」START開始，通過從開始到完成（或從完成到開始）的每條路線，以及在「全局性」中完成旅程，查找訪問所有路線所需的最低「成本」（距離或持續時間） 「完成？

我對Dijkstra算法很熟悉，但我不確定它是否可以在這種情況下使用。

每兩點之間的距離和/或持續時間是已知的（可以計算）。我猜測集合中每條路線的距離/持續時間並不重要，因爲我們需要找出所有「互連」路線的最低「成本」，從一條路線的末端到下一條路線的開始需要走路。

每條路線的方向並不重要，可以從「開始」到「結束」，也可以從「完成」開始到「開始」。

Answer 1

如果我遇到問題，您嘗試互連一組（起始，結束）對，從全局開始節點開始到結束於全局結束節點，以使這些對之間的互連具有最小距離。本地起點和終點（感興趣的路線）之間的聯繫已根據您的描述給出，因此不相關。

正如在評論中已經指出的那樣，這個問題是NP-hard，因此不能通過多項式時間算法解決（除非P = NP）。

正如上面的評論所表明的，如果本地（開始，結束）對的數量相當小，您可以簡單地嘗試所有這些對的排列，並按照各個排列給定的順序連接它們，每次使用dijkstra（或更高級的p2p算法）。不幸的是，正如之前所說的，這對你的例子中的13對來說是過度殺傷性的。

你可以嘗試的方法是通過考慮（貪婪地）僅考慮從最後一個終點（它可以通過dijkstra的一次運行來確定）的下一個X最近的起始點來啓發式地減少排列的數量。對於X = 2和13對，這會使您下降到2^12 = 4098個排列。對於X = 3，這將是3^11 * 2 = 354294.考慮到更多的排列，較高的X越好，解決方案越長，計算時間越長。