質問: 地点間の移動時間がわかっているときの巡回セールスマン問題の解き方について pythonで実装する方法を考えています。 現在総当たり手法を用いて計算していますが、 それではオーダーが階乗であるため地点数が増えれば対応できなくなります。 現在npyファイルに 地点間の移動時間[秒]を [[定義なし,2.63,6.52,5.34], [2.63,定義なし,5.87,4.32], [6.52,5.87,定義なし,7.87], [5.34,5.87,7.87,定義なし]] のように格納しているファイルを持っています。 地点数は全部で150地点ほどあり、 それぞれ[shop1,shop2,....,shop150]のように IDとして取り込んでいます。 この150店舗のうち指定したN店舗に関して 巡回セールスマン問題を解く方法を考えています。 入力は 指定する店舗>>>>[shop3,shop5,shop8,...,shop50] 制限時間>>>>7200[秒] それぞれの店での滞在時間>>>>360[秒] のようにすると 出力として [所要時間,行先順路] が一覧で出てくるようにしたいです。 この候補は条件を指定した店舗の全部を行くパターンまたは一部を行くパターンでその最短経路を出力できているようにします。 この巡回セールスマン問題を素早く方法として 遺伝的アルゴリズムを提案されましたが、 自分の実装力では実装しきれないのと いまいち今回のパターンにあてはまるソースコードを見つけられず苦戦しています。 参考URL http://blog.livedoor.jp/komq/archives/1012592617.html ご協力いただけると幸いです。
回答: そもそも巡回セールスマン問題は NP困難であって、はなから時間のかかるシロモノです。 それだけに高速化の為の手法は多く考案されており、遺伝的アルゴリズムに頼らずとも(数学的手法で)いくつもあります。 また、必ずしも厳密な最適解にこだわらないのであれば、多項式時間で近似できるアルゴリズムも研究されています。 ただ、一つ問題があって、たいていの高速なアルゴリズムでは前提条件として「いかなる2点であっても、直接結んだ場合は第3点を経由するより早く到達できる」が成立している必要があります。が、これ現実に考えるとそうとも言えないのですね。 ※道北から道南へ移動する場合とか、道内を列車移動するより羽田経由の飛行機移動×2の方が早い場合があるとか... ここなんか python でデモしてますからよいかもですね。いろいろなアルゴリズムで試されています。 http://www.geocities.jp/m_hiroi/light/pyalgo62.html