我有一個2d平面上的n個點,其中n < = 12,我需要包括所有點在內的最短路徑的距離,在他們中的任何一個,但沒有閉路算法或途徑路徑問題,最短路徑與n點n = 12
我一直在嘗試弗洛伊德元帥,旅行推銷員問題和其他算法沒有成功。
問題被認爲是容易讓我的老師,所以我不認爲這將需要阿羅拉近似左右,但我不知道什麼是最好的辦法來解決這個問題,但也許一些動態的算法和像
for i = 0 to n
for j = 0 to n
if path_distance(i,j) < mininum
set minimum
東西
有幫助嗎?
您是否被允許多次重訪積分?或者你必須一次訪問每個點,而且只需要訪問一次? – templatetypedef 2011-03-03 01:18:53
訪問每個點一次,並且只是一次 – Daniel 2011-03-03 01:31:33
這是一個O(n!)問題,而不是您嘗試的O(n^2)問題。十億條可能的路徑。先在一張紙上做。 – 2011-03-03 02:00:44