TSPの近傍

TSPを部分問題として持つマラソン問題を解く際に思ったことを書き残す。

始点、終点が固定されているケース

巡回順の配列seq について次のような遷移を適用。
最初と最後の
ただし、seq[0] = 始点、seq[N-1] = 終点

int a = rand()%(N-3); // 0 <= a <= N-4
int b = rand()%(N-a-3) + a + 2; // a+2 <= b <= N-2
if(cost[a][a+1] + cost[b][b+1] > cost[a][b] + cost[a+1][b+1]){
  int x = a+1;
  int y = b;
  while(x < y){
    swap(seq[x],seq[y]);
    x++;
    y--;
  }
}

始点だけ固定されているケース

上に次の遷移を追加する。

int a = rand()%(N-2); // 0 <= a <= N-3
if(cost[a][a+1] > cost[a][N-1]){
  int x = a+1;
  int y = N-1;
  while(x < y){
    swap(seq[x],seq[y]);
    x++;
    y--;
  }
}

さいごに

もしかしたら良くない遷移かもしれない。
あと同様の遷移でもうまくやって軽くできるはず。