トップQs
タイムライン
チャット
視点

2-opt

ウィキペディアから

2-opt
Remove ads

組合せ最適化において、2-opt巡回セールスマン問題を解く局所探索法の1つである。

Thumb
2-opt

2-optは、Croesによって1958年に初めて提案されたが[1]、基本的な動作は既にFloodによって提案されていた[2]。背景にある基本的なアイディアは、交わる経路はそうならないように順路を変更できるということである。完全な2-optは、交換可能なすべての組合せを比較する。この手法は、巡回セールスマン問題だけでなく、関連する多くの問題にも適用できる。例えば、配送計画問題(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の内容:
    1. (A → B)
    2. A → B → (C → D → E)
    3. 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
Remove ads

効率的な実装

新しい経路を構築しその距離を計算するのは、非常に高価な処理で、ふつうnを頂点数としてかかる。ただし、交換によって経路長が減少するかはで分かる。

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])

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

Remove ads

脚注

関連項目

外部リンク

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads