3

TSP問題にClarke-Wrightヒューリスティックを実装したい。最後のフェーズでは、ノードをスティッチしてサイクルを構築する必要があります。C/C++ で効率的に実装する方法を探しています。詳細とおもちゃの例を以下に示します。

n 個のデータ ポイントがあります (したがって、最終的なツアーには n 個のノードが存在します)。Clarke-Wright アルゴリズムの最初のステップを適用し、nx2 行列を作成しました (各行はエッジを表します)。最終ツアーのノードのシーケンスを表す個別のノードを持つ nx1 配列が必要です。

例: n=5

(順序付けられていないエッジ。たとえば、最初の行は、最終ツアーでノード 1 と 2 が隣接していることを示しています)

A: 

 1   2

 4   3

 3   2

 1   5

 4   5

(ファイナルツアー) B: 1 2 3 4 5

4

1 に答える 1

1

ハブ頂点が であるとしましょう0。各頂点がその近傍の XOR にマップされるベクトルをxor_adj作成します (これは、エッジを選択しながら段階的に作成できます)。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;
}
于 2013-07-26T13:13:28.153 に答える