セールスマンのことをいい加減に考えるコンピュータ

今日、記事を読んでたら、その中に気になるキーワードがあった。
それで調べてたのだが、そこで驚愕の事実を知ることになった。
巡回セールスマン問題という問題があるのだが、
実は現在開発してるあるソフトウエアの将来の目標は、これにさらに厳しい制約を課したものを実現しないといけないと。
まだ、その部分の実装に至ってた無かったので今まで気にしてなかったが、困った。
なぜならば、巡回セールスマン問題はコンピュータにとっての指折りの難題だから。


さて、どういう問題かというと…
大阪の事務所を出て、神戸・徳島・和歌山・奈良・京都・彦根にいる顧客のところに1回ずつ行って、大阪に帰ってくるとき、
もっともコストのかからないルートを求めよ。という問題です。
多分大阪→奈良→京都→彦根→神戸→徳島→和歌山→大阪と回るのが正解だと思います。
JR速いしね。安いかは知らんけど…
どちらにせよ、パラメーターがないのに言い切るのは間違えだと思うけどね。
ところがこれを厳密に計算しようと思うと、6P6=6!=720通り、それぞれの結果を比較しないといけない。
今回は5箇所なので120回計算すれば済みます。
けど、ここに、姫路・堺・舞鶴・敦賀の4都市を追加するだけで10!=3628800回と絶望的な回数になる。
なので、最適解を求めることはあきらめましょうということです。


じゃあどうするのかという話だが、まずこれをランダムに並べてみる。
大阪→奈良→神戸→彦根→和歌山→京都→徳島→大阪と並べましょうか。
これの要素の入れ替えで、できるだけコストの低いものを作りましょうと。
その入れ替えの方法に2-opt法、Or-opt法というのがあって、この2つぐらいを使えばいいでしょうと。
実際はさらにいろいろあるのですが、まぁこれは追々研究すればいいでしょう。
まず、2-opt法だが、これは2本の矢印を入れ替える方法。
和歌山→京都と徳島→大阪の矢印を入れ替えて、和歌山→徳島、京都→大阪にする。
これに合わせて、京都→徳島の順序を逆転させる。
これで、大阪→奈良→神戸→彦根→和歌山→徳島→京都→大阪となり、少しは改善される。
Or-opt法だが、これは3本の矢印を入れ替える方法、
奈良→神戸、彦根→和歌山、徳島→京都を入れ替えて、
奈良→和歌山、彦根→京都、徳島→神戸に変更する。
これに合わせて順番の入れ替えなどを行うと、
大阪→奈良→和歌山→徳島→神戸→彦根→京都→大阪
となり改善される。
初めのぐちゃぐちゃのルートに比べればこれでもかなりましです。
実際はしらみつぶしに2-opt法、Or-opt法を適用するので、もっといいです。
それでも階乗よりかはかなりましでして、計算時間は多項式で表すことができると。
多項式より指数関数、指数関数より階乗の方が増加が早いよと。
ただ、この方法では初めの並びによっては、最適解とならないことがあります。
なので、最初の並びはランダムに作成して、何度か計算して最適なものを答えとするのがいいです。
今回はどうか知らんけど。
Ibaraki Laboratory
ここにあるソースコードを参考にしたわけですが、まぁわかればそれほど難しくないアルゴリズムです。
その成果はいかほどかというと、Topページのぐちゃぐちゃが整理されるJavaアプレットを見ればわかるでしょう。
僕が実行したときは距離が42541が3989まで整理されたわけです。かなりよくなりましたね。


さて、プログラムの作成を進めて、このアルゴリズムととりあえず実装してみました。
わかればサクサク実装できますね。
実際にプログラムにやらせてたけど、最適解だとなんぼなのかは調べてません。
この2つのアルゴリズムだけでどれぐらい効果があるのかというと、
488移動が178移動、470移動が170移動で、2回実行した結果、170移動になるルートがもっともコストが安そうだと。
ただ、これよりコストが安いルートはあるかもしれないのでなんともいえません。
ちなみに回るのは33箇所。
さほど多くはないけど、33!=8.68×1036なので、最適解を求めないのは正解ですね。
まぁ他にもいろいろあるのですが、基本は、2-opt法、Or-opt法ですね。
実行のたびにどれぐらいよくなっていくかというのも調べて、何度計算すれば幸せになれるかとか考えてみようと思う。
しかしなぁ…巡回セールスマン問題を解くだけじゃやりたいことは完璧じゃないんだけどね。
まぁそれでも、移動数を少なくした方が有利なので、とりあえずこれをよくしていきましょうか。