今回も巡回セールスマン問題を解きます。

巡回セールスマン問題を2-opt法で解く

2-opt法とは以下のような方法です。

初期解を適当に作る。
一定の回数か、解があまり改善されなくなるまで以下を繰り返す
 巡回路を成す辺を 2 本選び、その辺をつなぎ変えることを考える。
 つなぎ変えることによって巡回路長が短くなるならつなぎ変える。
 短くならないなら何もしない。

都市の座標を管理するためのNodeクラスを定義します。

TwoOptクラスの定義

2-opt法で巡回セールスマン問題を解くクラスを定義します。

以下は2つの辺を選ぶための乱数を生成するメソッドです。

以下は生成された2つの辺を選ぶメソッドです。常に a より b のほうが大きくなるようにします。

一定の回数だけ乱数で2つの辺を選んで、辺を入れ替えたとき短くなるのであれば辺を入れ替える処理を示します。配列の外にアクセスしてしまう場合はスタート地点に戻ってくるように剰余を利用しています。

得られた経路の長さを取得する処理を示します。

解を求める

都市の数 16 で1000回ループさせてみると以下のようになりました。1000回ループでも11回しか更新されていません。

実行にはそんなに時間はかかりませんでした。2500都市 1000回ループでも 0.1 秒かかりません。

(参考)【paizaラーニング】2-opt法によるTSP

巡回セールスマン問題を禁断探索法で解く

禁断探索法は以下のような方法です。

解を適当に作り、暫定解 X とする。
最良解 B を X で初期化する。禁断リストを空で初期化するとともに、禁断リストのサイズの上限 TL を決める

一定の回数、以下を繰り返す
 暫定解 X を少し変更したもの (X の近傍) であり、禁断リストに含まれていない解のうち最も良い解を求め、これを暫定解とする。
 暫定解 X を禁断リストの先頭に加える。禁断リストのサイズが上限を超えた場合は禁断リストに含まれている最も古い解を削除する。
 最良解 B を解として出力する

禁断リストを用いることによって、同じようなところを何度も探索するのを少なくなることが期待できます。

ここでは「X の近傍」を巡回路 X に含まれる2本の辺を繋ぎ変えたものと定義します。そして「禁断リスト」には繋ぎ変えた辺の端点のうち巡回路Xの先頭に最も近い都市 t を入れます。これは、t を端点として持つ辺を繋ぎ変えて解を更新するとしばらくのあいだ、t を端点として持つ辺は繋ぎ変えないことを意味しています。

都市の座標を管理するためのNodeクラスを定義します。

TabuSearchクラスの定義

巡回セールスマン問題を禁断探索法で解くためのTabuSearchクラスを定義します。

禁断探索法で解を求める処理を示します。

解を求める

都市の数 16、禁断リストのサイズの上限 5 で1000回ループさせてみると以下のようになりました。

実行にはそんなに時間はかかりませんが、2-opt法と比べると時間がかかります。200都市 150回ループだと約 1 秒かかります。

(参考)【paizaラーニング】禁断探索法によるTSP