2-opt法のアルゴリズム、与えられたツアー

Question

の近傍には、私は本当に2-opt法のアルゴリズムを使用して、指定されたツアーの隣人を見つける方法を理解することはできません。

は、我々はT = 0-1-2-4を持っていると仮定します-3-0

定義：Tの近傍は、すべての の集合として定義され、T（2交換）内の2つの非隣接エッジを変更することによって到達することができます。

だから我々は、これらの隣接していないエッジがあります。

（0,1）と（2,4）

（0,1）と（4,3）

（1,2）私たちは5人の隣人を見つけなければならないと（4,3）

（1,2）と（3,0）

（2,4）と（3,0）

私たちはそれらの2つのインターチェンジの動きをどのようにして生み出すことができますか？

ありがとうございます。

Answer 1

隣接していないエッジのペアを見つけるのに適しています。次に、各ペアについて、新しいエッジを付けて新しいツアーを形成する方法があります。たとえば、（0,1）と（2,4）を削除すると、次のように置き換えることができるエッジのペアが3つあります。

（0,1）および（2,4）：これはオリジナルツアー

（0,4）と（1,2）と同じ：これは代わりに、1件のツアー二subtours

（0,2）及び（1,4）を作成します。これは一般的に、エッジ（i、j）と（k、l）を削除すると、コストが削減されると仮定して、それらを（i、k）と（j、l）に置き換えます。これはツアーの半分の方向を変えることに注意してください。

あなたの定義によれば、Tの近隣は、このようにして達成できるすべての新しいツアーのセットです。