TSPにおいて2opt法を用いて解きます。
NN法で出力した経路順で2opt法を適応します。
(実行結果)
->13->4->3->10->11->2->1->5->7->8->12->9->14->6->
path length= 3.795572
8->7->5->1->2->11->10->3->4->13->0->6->14->9->12->
path length= 3.795572
上の順列がNN法で,下が2opt法です。
このノードの座標をプロットしても,NN法でプロットした図と変わりませんでした。
2opt法のソースコードを以下に示します。
void two_opt(int p[], double d[N][N], int n)
{
int i, j, k, dif, temp;
for (i = 1; i < n+1; i++) {
for (j = i+2; j <i + n-1 ; j++) {
dif = ( d[p[i%n]][p[(i+1)%n]] + d[p[j%n]][p[(j+1)%n]] )
- (d[p[i%n]][p[j%n]] + d[p[(i+1)%n]][p[(j+1)%n]]);
if (dif > 0) {
for (k = 0; k <(j-i)/2; k++) {
temp = p[(i+1+k)%n];
p[(i+1+k)%n] = p[(j-k)%n];
p[(j-k)%n] = temp;
} return;
}
}
}
}
どなたか教えていただければ幸いです。