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

Question

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

2) ABCDA 阿卜杜卡 ....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},
};

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