algorithm - 是否有计算距离排列的算法？

Question

这与旅行商问题有关。首先需要生成所有排列，然后附加目的地(与原点相同)。 IE。:1)A B C Dabdc....

2)ABCDA阿布卡....一个

我有所有的距离，只需要一个算法来总结它们。我想知道是否有我可以使用的算法(最好是 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},
};

请注意，这将是您问题的对称矩阵。