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は、2 つのノード間の距離を保持する 2 次元配列 (場合によっては行列) です。group は、配列またはベクトル、または移動する順序のノードである必要があります。

各順列も取得する必要がある場合は、next_permutation を使用します。

距離の簡単な例を次に示します。

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

これは問題の対称行列になることに注意してください。