permutation - TSP でのダブル ブリッジ移動

Question

TSPでダブルブリッジムーブを実装したい。3 つのランダムな位置を選択し、順列を 4 つの部分に分割し、これらの部分を別の順序で再接続する必要があることはわかっていますが、二重ブリッジによる TSP 問題で使用できるすべての可能な組み合わせを取得したいですか?

都市の数を n とすると、二重橋の可能な組み合わせはすべて n 個になるでしょうか?

Answer 1

順列全体を約 4 等分に分割し、それらを再接続して新しい解を見つけようとすると、n 個の都市に対して近傍解の近似数は [(n-2)/4]^3 になる可能性があります。ここで、[x] は x 以上の最小の整数値を表します。