A之間路由和B

Question

i'm站之間缺少明顯透過樹木森林...

我知道旅行商問題，但沒有任何其他算法/問題哪個好適合我的需求/描述？我需要藉助這種數學描述來描述我的問題。

我有多達五點已知的起點和終點。所以我只需要計算最短的方式來訪問這兩者之間的所有三點。 Dijkstra和類似的算法試圖找到兩點之間的最短路徑，所以在這裏他們可能不會訪問所有點之間的所有點。還是有一種算法找到最短路線並訪問兩點之間的所有點？

Answer 1

你正在超越它。通過三個中間節點只有六條（3 * 2 * 1）可能的路徑。只是檢查他們。

對於較大的情況下，你可以減少你的問題的TSP如下：

如果s的出發點和t是最後一個節點，添加s和t和無限之間的零重量邊緣 - s與其他節點之間以及t與其他每個節點之間的重要邊緣。

這個問題是NP-hard，但是研究得非常好。有許多精確和近似的算法可供您探索。