有計算距離排列的算法嗎？

Question

這與旅行商問題有關。首先需要生成所有排列，然後附加目的地（與原點相同）。即： 1） ABCD ABDC ....

2） ABCDA abdca ....一個

我所有的距離，只需要一個算法來總結起來。我想知道是否有一個算法（C更好），我可以使用這個算法，或者如果有一個現成的解決方案。

Answer 1

這是有點小事。

int sum = 0; 
for (i = 0; i < length-1; i++) 
{ 
    sum += distance[group[i]][group[i+1]]; 
} 

哪裏distance是保持兩個節點之間的距離的二維陣列（矩陣如果你願意）。組應該是一個數組或矢量或節點按順序走過。

如果您還需要獲取每個排列，請使用next_permutation。

這裏有什麼距離可能是一個簡單的例子：

int distance[4][4] = { 
{0,2,1,0}, 
{2,0,1,2}, 
{1,1,0,1}, 
{0,2,1,0}, 
}; 

注意，這將是你的問題的一個對稱矩陣。