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

Question

这与旅行商问题有关。首先需要生成所有排列，然后附加目的地（与原点相同）。即：1）abcd abdc ....

2) abcda abdca ....a

我有所有的距离，只需要一个算法来总结它们。我想知道是否有一种算法（最好是 C）我可以使用它，或者某处是否有现成的解决方案。

Answer 1

这有点微不足道。

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

distance保存两个节点之间距离的二维数组（如果你愿意的话，矩阵）在哪里。group 应该是数组或向量或按顺序移动的节点。

如果您还需要获取每个排列，请使用 next_permutation。

以下是距离可能是多少的简短示例：

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

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