ポケモンスタンプラリー2014を最適ルートで回ってみた (問題提起編)
夏休みといえば、何が思い浮かびますか？
JR東日本ポケモンスタンプラリーとは
- 1997年ほぼ毎年行われているスタンプラリー
- 東京、神奈川、埼玉、千葉の1都3県、合計30駅スタンプ駅がある (2014年)
- 6駅集めると景品がもらえる。30駅全部集めると抽選でなんかもらえる (2014年)
- スタンプ設置時間は9:30~16:00 (2014年)
です。
首都圏に住んでいる方なら、毎夏、電車内で子供がスタンプシートを持っている姿は、風物詩になっているのではないでしょうか。
僕も、小学生の頃、親にせがんで山手線の駅をぐるぐると回ったことを覚えています。
さて、そんなスタンプラリーですが、大学4年生になった今、表題の通り回って来きした。
スタンプラリーは、金はないが時間のある大学生の夏休みには、もってこいの暇つぶしになります。
そもそもスタンプラリー、実は奥が深い。
特に、後述するように、ポケモンスタンプラリーはスタンプラリー界でも屈指の難易度なのです。
実は、スタンプラリーのように、あるポイント群を最短で繋ぐことを求められる問題には名前がついています。
その名も巡回セールスマン問題です。
詳しくは説明しませんが、巡回セールスマン問題はNP困難と呼ばれる問題にカテゴライズされていて、普通に解いていては、生きている間に計算が終わらないのです！
今回のポケモンスタンプラリーはスタンプ駅が30駅もあります。
スタンプラリー界でもこれほど多いものは、あまりありません。
この時、全てのスタンプを押す順番の通りの数を求めると、
30!/2 ≒
132626429906096000000000000000000 [通り]
となります。
ぱねえ
ちなみに、漢字で書くと、
十三穣 二千六百二十六𥝱 四千二百九十九垓 六百九京 六兆 [通り]
になります。
ぱねえ。
試しに全部回ってたら余裕で寿命尽きてしまうでしょう。
というわけで、人類の偉大なる奴隷、コンピューターにこの計算を託すことにしました。
次回はコーティング編です。
(追記8/11)
コーディング編
ポケモンスタンプラリー2014を最適ルートで回ってみた (コーディング編) - 新米コンサルの日常
