c++ - 如何在游览中缝合节点

Question

我想为 TSP 问题实现Clarke-Wright启发式。在最后一个阶段，它需要缝合节点来构建一个循环。我正在寻找一种在 C/C++ 中实现它的有效方法。更多细节和玩具示例如下所述：

我有 n 个数据点（因此最终巡回中存在 n 个节点）。我应用了 Clarke-Wright 算法的第一步，并有一个 nx2 矩阵（每行代表一条边）。我想要一个具有不同节点的 nx1 数组，它代表最终游览中的节点序列。

示例：n=5

（无序边，例如第一行显示节点 1 和 2 在最终巡回中相邻）

A：

（最终巡回演出）B：1 2 3 4 5

score 1 · Accepted Answer

假设中心顶点是0。制作一个向量xor_adj，其中每个顶点映射到其邻居的 XOR（您可以在选择边时逐步构建它）。找到一个v与中心顶点相邻的顶点，并使用此循环提取边。

int u = 0;
while (true) {
    // emit the edge u->v
    if (v == 0) break;
    int w = xor_adj[v] ^ u;
    u = v;
    v = w;
}

1 回答 1