2-optのソースを表示

[[File:2-opt wiki.svg|thumb|2-opt]]
[[組合せ最適化]]において、'''2-opt''' は[[巡回セールスマン問題]]を解く[[局所探索法]]の1つである。

2-optは、Croesによって1958年に初めて提案されたが<ref>{{Citation
| author = G. A. Croes
| title = A Method for Solving Traveling-Salesman Problems
| journal = Operations Research
| year = 1958
| volume = 6
| number = 6
| pages = 791-812
| doi = 10.1287/opre.6.6.791}}</ref>、基本的な動作は既にFloodによって提案されていた<ref>{{Citation
| author = Merrill M. Flood
| title = The Traveling-Salesman Problem
| journal = Operations Research
| year = 1956
| volume = 4
| number = 1
| pages = 61-75
| doi = 10.1287/opre.4.1.61}}</ref>。背景にある基本的なアイディアは、交わる経路はそうならないように順路を変更できるということである。完全な2-optは、交換可能なすべての組合せを比較する。この手法は、巡回セールスマン問題だけでなく、関連する多くの問題にも適用できる。例えば、{{仮リンク|vehicle routing problem|en|Vehicle routing problem}}(VRP)やその容量付き版などが挙げられるが、これらに適用するにはアルゴリズムを少し修正する必要がある。

== 擬似コード ==
図で表すと、交換は次のように行う。

  - A   B -             - A - B -
      ×         ==>
  - C   D -             - C - D -

擬似コードでは、経路を更新するルーチンは次のようになる。

 '''procedure''' 2optSwap(route, v1, v2) {
     1. route[0]からroute[v1]までを順番にnew_routeに追加する。
     2. new_route[v1+1]をroute[v2]とし、逆順にnew_routeに追加する。
     3. route[v2+1]から末尾までを順番にnew_routeに追加する。
     '''return''' new_route;
 }

以下は、2optSwapの動作例である。

* 経路(変数 route): A → B → E → D → C → F → G → H → A
* v1=1, v2=4 (開始インデックスを0とする)
* ステップ毎のnew_routeの内容:
*# '''(A → B)'''
*# A → B → '''(C → D → E)'''
*# A → B → C → D → E → '''(F → G → H → A)'''

2optSwapをサブモジュールとして、完全な2-optは次のように書ける。

 '''repeat until''' 改善が見られない {
     best_distance = calculateTotalDistance(existing_route)
     start_again:
     '''for''' (i = 0; i <= 交換可能なノード数 - 1; i++) {
         '''for''' (j = i + 1; j <= 交換可能なノード数; j++) {
             new_route = 2optSwap(existing_route, i, j)
             new_distance = calculateTotalDistance(new_route)
             '''if''' (new_distance < best_distance) {
                 existing_route = new_route
                 best_distance = new_distance
                 goto start_again
             }
         }
     }
 }

始点や終点にある特定のノードは、順番を逆にすると無効な経路になるため、交換の候補から外すべきである。例えば、Aに戻る経路を次のように表しているとする。

    A → B → C → D → A

route[0]とroute[2]を交換すると、new_routeは次のようになり、正しい経路情報ではなくなる。

    C → B → A → D → A

== 効率的な実装 ==
新しい経路を構築しその距離を計算するのは、非常に高価な処理で、ふつう{{mvar|n}}を頂点数として<math>O(n)</math>かかる。ただし、交換によって経路長が減少するかは<math>O(1)</math>で分かる。

 lengthDelta = - dist(route[v1], route[v1+1]) - dist(route[v2], route[v2+1]) + dist(route[v1+1], route[v2+1]) + dist(route[v1], route[v2])

もし<code>lengthDelta</code>が負であれば、交換後の新しい距離が短くなることを意味するので、そのときのみ2-optの交換を行うことで、計算コストを大幅に抑えられる。

== 関連項目 ==
* {{仮リンク|3-opt|en|3-opt}}
* [[局所探索法]]
* {{仮リンク|リン・カーニハン・アルゴリズム|en|Lin–Kernighan_heuristic}}

== 参考文献 ==
{{Reflist}}

== 外部リンク ==
* [https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf The Traveling Salesman Problem: A Case Study in Local Optimization]
* [http://www-e.uni-magdeburg.de/mertens/TSP/node3.html Improving Solutions: 2-opt Exchanges]

[[Category:ヒューリスティック・アルゴリズム]]
[[Category:巡回セールスマン問題]]