算法或途徑路徑問題，最短路徑與n點n = 12

Question

我有一個2d平面上的n個點，其中n < = 12，我需要包括所有點在內的最短路徑的距離，在他們中的任何一個，但沒有閉路

我一直在嘗試弗洛伊德元帥，旅行推銷員問題和其他算法沒有成功。

問題被認爲是容易讓我的老師，所以我不認爲這將需要阿羅拉近似左右，但我不知道什麼是最好的辦法來解決這個問題，但也許一些動態的算法和像

for i = 0 to n 
    for j = 0 to n 
    if path_distance(i,j) < mininum 
     set minimum 

東西

有幫助嗎？

Answer 1

如果你知道你只有12個點，並且想要找到一次訪問每個節點的最短路徑，那麼你總是可以通過嘗試所有可能的節點排列和計算長度來暴力破解沿着這個排列的路徑。這根本不能很好地擴展，但是如果你對節點數有一個固定的上限，那麼它應該是合理的。

Answer 2

當且僅當n <= 12，我建議the Branch and Bound algorithm，這是蠻力算法的改進版本。

Answer 3

我將只提供一個提示因爲這是家庭作業：打破這類問題時

遞歸是非常有用的。

您可以編寫一個函數，該函數獲取到目前爲止的路徑列表，迄今爲止的最佳/最小距離以及未訪問節點的列表。對於每個未訪問的節點，它會嘗試將其添加到目前爲止的路由，如果該路由仍然短於迄今爲止的最佳/最小距離，那麼它將自行調用新路由和未訪問節點的列表。