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

概要

巡回セールスマン問題(TSP:Traveling Salesman Problem) は、都市の集合と各2都市間の移動コストが与えられたとき、 全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストを最小化する、組み合わせ最適化問題です。 以前、大学の講義で自由に課題を設定してレポートを書く際に実装したのですが、割と苦労したので公開しておきます。

2-opt法

2-opt 法は逐次改善法の一種であり、逐次改善法とは、ある巡回路を基として、 それより更にコストの小さい巡回路を探す方法です。 2-opt 法のアルゴリズムは、次のように表されます。

  1. 入力した巡回路に対し、適当な二つの辺を選択し、それらを入れ替えた結果のコストを計算する。 そのコストが入れ替える前より小さくなれば、入れ替えを採用し、巡回路を改善する。
  2. 1.を、巡回路の改善ができなくなるまで繰り返す。

逐次改善法は既存の巡回路を改善していくことで最適解に近づけていくものなので、 事前に初期解として何らかの巡回路を与えておかなければなりません。 適当に巡回路を定めても良いのですが、ここでは構築法(与えられた都市間のコストから、巡回路を構築していく方法) であるNearest Neighbor法、Convex Hull Insertion法の2つを実装しました。

Nearest Neighbor法

Nearest Neighbor法のアルゴリズムは、次のように表されます。

  1. 適当な都市を選び、出発点とする。
  2. まだ訪れていない都市のうち、現在いる都市から最も近い都市を選び、その都市との経路を巡回路に加え、その都市に移動する。
  3. 2.を、まだ訪れていない都市がなくなるまで繰り返す。なくなったら、最後に訪れた都市と出発点とをつなぐ経路を巡回路に加えて終了する。

Convex Hull Insertion法

凸包を初期部分巡回路とし、それ以外の都市を最近挿入法により加えながら巡回路を構築する方法です。アルゴリズムは以下で表されます。

  1. 都市を頂点とする凸包の境界上の都市を初期巡回路とする。
  2. 巡回路上の連続した都市を{i,j}とし、巡回路以外の各都市{\theta_{12}}に対して、追加コスト {c_{ik}+c_{kj}-c_{ij}} を計算し、この値を最小とする都市{i,j}を求める。求めた組み合わせ について、追加コスト比 {c_{ik}+c_{kj}/c_{ij}} を計算し、この値を最小とする都市{k}を巡回路 に追加する。
  3. 全ての都市を通過する巡回路ができるまで2.を繰り返す。

グラハムスキャン法

ややこしい話になりますが、CHI法で巡回路を構築する前に、さらに初期段階として 都市の点集合の凸包を求める必要があります。 凸包を求めるアルゴリズムには、分割統治法、逐次添加法などが存在しますが、 ここではグラハムスキャン法というアルゴリズムを採用します。

  1. 都市の集合のうち、y座標が最小のもの(複数ある場合は、そのうちx座標最小の もの)を基準点とし、基準点に対する角度の順に、残りの点に番号をつける。
  2. 番号順に点を見ていき、一つ前の点H、現在の点I、次点の角度Jの角度∠HIJ を 計算する。角度がマイナスになる場合、凸包にはならないため、点I を削除する。 そして、その次の点Kとの角度∠HJK を計算し、同様の操作を繰り返す。
    1. の操作を、全ての点との角度を計算するまで行う。

コード

長くなったので、GitHubに上げてあります。 「Nearest Neighbour法のみ」、「CHI 法のみ」、「Nearest Neighbour 法+2-opt 法」、「CHI 法+2-opt 法」の いずれかについて計算し、matplotlabで結果を表示できるようにしてあります。 なおTSPの問題となるデータは、TSPLIBというサイトから頂いてきます(同サイトで最適解の確認もできます)。 f:id:Kanchi0914:20180613180627p:plain

参考文献

坂上知英, 吉澤慎, 太田義勝,大山口通夫:巡回セールスマン問題の近似アルゴリズムに ついて. Research reports of the Faculty of Engineering, Mie University, 25, pp.81-96,(2000)
星野貴弘, 浜松芳夫:巡回セールスマン問題に対するヒューリスティック解法. 研究報告 高度交通システム(ITS), 2011(3), pp.1-4, 2011
関根渓:INTRODUCTION TO ALGORITHMS,http://www-ikn.ist.hokudai.ac.jp/ksekine/slides/convexhull.pdf

クリップボードのテキスト内の改行を削除するツール(Python + PyInstaller)

最近のGoogle翻訳の精度は本当に凄くて、英語の文献をしょっちゅうコピペしながら読んでいます。 ただ、Google Chrome拡張機能から翻訳する場合は大丈夫なのですが、Adobeのリーダーなどからコピーした文を貼り付けると改行コードが残り、 そのままペーストすると翻訳の邪魔になってしまいます。

というわけで、ワンアクションでクリップボード内のテキストに含まれる改行を削除するツールを作りました。

環境、使用したもの

  • Windows 10
  • Python 3.5.3
  • pyperclip 1.6.2
  • PyInstaller 3.3.1
  • ランチャー、またはショートカット変更ツール

実装

やることは非常に簡単です。

① クリップボード内のテキストを取得後、改行を削除したのちにクリップボードに返すコードを用意
② ①を.exeファイルに変換、ランチャーに登録

まず必要なパッケージであるpyperclip, PyInstallerをインストールします。両方ともpipで入れられます。

pip install pyperclip pyinstaller

①のコードはpyperclipを使って数行で書けます。

import pyperclip

a = pyperclip.paste()
b = a.split()
c = ''

for text in b:
    c = c + text + ' '

pyperclip.copy(c)

pyperclip.paste()クリップボードからテキストを取得、pyperclip.copy()クリップボードにコピーします。 なおsplit関数で引数を指定しないと空白も削除されてしまい、それだと英文の場合困るので単語ごとに空白を入れています。

書いたコードをsample.pyとして保存した場合、コマンドラインから下記を実行することで .exeファイルが作れます。

pyinstaller -F -w sample.py

引数はそれぞれ、生成するファイルを一つにまとめること、実行したときにウィンドウを生成しないことを意味しています。

生成したらあとは実行するだけなのですが、ランチャーに登録しておくと便利です。 私はOrchisというランチャーを使っており、Shiftキー2回連打でマウスの横にアプリが表示されるので、 実際に使うときは「コピー→ランチャー起動→クリックして改行を削除」という流れになります。

f:id:Kanchi0914:20180610050529p:plain

また、キーボードショートカットから特定のアプリを起動できるソフトを使えば、 好きなショートカットキーを押すだけで同じことができます。 そのようなソフトにはX Button Makerなどがあります。

余談

似たようなことができるツールがないか探したところ、普通にありました。 www.vector.co.jp