読者です 読者をやめる 読者になる 読者になる

新米コンサルの日常

僕の日常の非日常を適当に書いていきます。

ポケモンスタンプラリー2014を最適ルートで回ってみた (コーディング編)

python アルゴリズム スタンプラリー ポケモン 巡回セールスマン問題

ポケモンスタンプラリー2014を最適ルートで回ってみた (問題提起編) - 新米コンサルの日常のつづき

 

 

おさらい

  • ポケモンスタンプラリーとは、30駅を9:30~16:00で回るスタンプラリー
  • これを最短最速で回ろうとすると、巡回セールスマン問題になる
  • 巡回セールスマン問題は有限時間で解くのが困難 (NP困難)
  • 実際、今回のルートについて全ての通りを数え上げると30!/2通りになる

 

 

問題定義

計算と、実証の簡単のために、問題を少し矮小化して、

「実行日(平日)の9:30~16:00で最も多くの駅を回るルートを見つける。」

とします。

どうしてこれが計算の簡単に役立つかというと、16:00以降どこに行くべきか、を意識に入れないで済むからです。

「10駅回ったところで16:15になりました。その後の最短ルートも探しますか?」

と言われたら、計算時間の無駄だからやめろって言いますよね。

実際、このおかげで、20!程度まで計算量を削減出来ました。

 

 

データの取得

自動乗り換え計算の方法を考えると、まず、最短経路の計算手段について

毎回きっちり調べるのか / 蓄えたデータを利用するのか

という小問題があります。

前者は厳密ですが時間がかかる、後者は近似的ですが時間がかかりません。

そこでまず、ランダムに作った30駅のルートを「毎回きっちり調べる」で計算してみたところ、ゆうに4秒程度かかりました。

一方、「蓄えたデータ利用」で計算すると、0.5秒かからず、数分の誤差の近似解を出すことができたので、今回はこちらを採用しました。

そもそも、4秒というのは今回膨大な処理を行うことを考えると、非常に大きい時間(!)で、私が生きている間に計算を終わらせることが出きそうにないので現実的ではありません。

ちなみにデータソースはYahoo!乗換検索をスクレイピングしたものです。APIを叩く方がいいんじゃないか、のような意見があると思うのですが、

のでスクレイピングをしました。

ちなみにGoogle経路検索APIは公共交通機関を(まだ)サポートしていません。

 

 

つくってみた

ルートを作成する方法を3通り作りました。

  1. ランダム作成
  2. 貪欲法で作成
  3. (エセ)分枝限定法で作成

それぞれについて説明します。

(ちなみにスタンプ、乗り換え時間を考慮していません。)

 

 

ランダム作成

f:id:t11378rs:20140811172923j:plain

こんな感じ。体感ですが平均8駅くらいしか回れません。(6:55と言うのは所要時間)

何も考えずに回るとこうなるよ、って話ですね。

ちなみに一番下の時間が、処理にかかった時間なのですが、データベースの読み込みに18秒ちょいかかるので、実質2秒で作って(表示して)るっぽいですね。

 

 

貪欲法

貪欲法って名前きくと尻込みするかもしれませんが、要するに、

一番行きやすい駅に行くのを繰り返す

ってことです。その結果がこれ ↓

f:id:t11378rs:20140811173259j:plain

いい感じですよね!

処理にかかる時間もランダムとほとんど変わらないのに、これだけ結果が向上するのはとても嬉しい。

しかし、これは厳密解ではありません。

良い近似解(ヒューリスティクス)と言えますが、決して、最良とは限らないのです。

実際、特に終盤になると顕著ですが、大きな移動が増えます。

前半にとりあえず近いところを… という試行を繰り返したツケを結局後半に払うわけですね。

 

 

(エセ)分枝限定法

分枝限定法って名前きくと尻込みするかもしれません。

大いに尻込みしてください。僕は尻込みしました。

要するに、問題を小さく分けて、解かなくていい問題を省こうね、って事らしいのです。

が、尻込みしました。厳密な実装は断念です。

なので、結局これは総当りです。とはいえ、タイムオーバーしたものなど、解かなくていい問題は解いないあたり分枝限定法と言えなくもない気が、しなくもなくもなくもない。

で、計算”途中”がこちら ↓

f:id:t11378rs:20140811174215j:plain

終わんねえよ…

計算量圧縮しきれませんでした。

ちなみにこれを3時間ほど回した結果、メモリにSSD容量食いつくされて色々クラッシュしました。

あかん。

 

 

結局、

近似解である、貪欲法ルートを今回の「最適ルート」としました。

残念ながらポケモンスタンプラリー全駅制覇の夢は断念です…

また、作業ディレクトリまるごとGitHubに上げたので、気になる人は見てください。

(spider.py, main.py, calc_route.pyくらいです。大事なのは)

t11378rs/tsp_poke · GitHub

 

 

次回、「回ってみた編」です。

ポケモンスタンプラリー2014を最適ルートで回ってみた (回ってみた編) - 新米コンサルの日常