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

エロと研究と日々の徒然

巡回ディズニー問題

こんばんは。昼のプルさわです。
みなさんディズニーは好きですか?
私は大好きです。

この前友人とディズニーランドの話をしていたところ
「行きたいアトラクション最短で回るコース、パッと出してくれる何か作ってよ~。」
と言われたので、ちょっと取り組んでみました。

ということで、

目的のアトラクションを最短距離で回る問題

を考えてみたいと思います。

巡回セールスマン問題

 さて、このディスニーランド最短距離で回りたい問題は、有名な「巡回セールスマン問題」として考えることができます。
「え、巡回セールスマン問題って何?」
という感じですね。
ググればすぐに分かりますが、簡単に言うと以下のような問題です。

地図上にある指定のポイントを最短距離で回るためにはどのように回れば良いか?

この問題は非常に奥が深く、多くの研究者が取り組んできた問題です。
そのため解法などが充実しているのですが、今回は無視してすべての経路を求める力技を使おうと思います。*1

距離データを集める

さて、問題を解くためにはアトラクション間の距離を集めたデータが必要です。
どっかに落ちてないかな~と思って調べたのですが、ちょろっと検索しただけでは見つからなかったので作りました。
本来なら道を歩いて距離を計測するべきなんですが、面倒だったので地図上の直線距離で近似しました。

SK ロードカウンタ RM-3MW

SK ロードカウンタ RM-3MW

 

 さて、アトラクションですがこちらも本来ならすべてのアトラクションに関するデータを収集する必要があるのですが、めんどくさいので人気アトラクション(ファストパスを発行しているアトラクション)のみに絞ってデータを取ってきました。

以下が、アトラクション間の距離を集めたデータです。

f:id:oscillograph:20141016211556p:plain

最も離れているのは「スプラッシュ・マウンテン」と「スターツアーズ」です。
逆に最も近いのはスプラッシュ・マウンテン」と「ホーンテッドマンション」です。

これはディズニー好きなら納得の結果になっています。

ちなみにアトラクション間で平均の距離は326mですので、単純に考えると8つのアトラクションをすべて回ると

326×7=2282m=2.2km

となり結構な距離を歩くことになります。

最短経路を見つける

今回は高々8地点なので、高度なアルゴリズムを使わずともすべての経路をリストアップして距離を計算し、距離が短い順に並べることで解を求めようと思います。

さて、どのような道順があるかを考えます。
どのような道順をたどるかという問題は「組み合わせ」として捉えることができます。

なので8地点を回る道順は

8!=8×7×6×5×4×3×2×1=40320(通り)*2

あることになります。かなり様々な種類の道順がありますね。

というわけで計算してみました。*3

結果

 計算の結果

  1. ビッグサンダー・マウンテン
  2. スプラッシュ・マウンテン
  3. ホーンテッドマンション
  4. プーさんのハニーハント
  5. スペース・マウンテン
  6. スターツアーズ
  7. モンスターズ・インク
  8. バズ・ライトイヤー

 の順で回ると総距離が1056mとなり、最短となることが分かりました。

先ほどの平均的な距離が2.2kmだったことを考えると、計算することによって総距離が半分以下になりました。

この結果はちょっと参考になるかもしれません。ちょっと。

f:id:oscillograph:20141016233000p:plain

 

(あるか分からない)今後の展開

今回はいくつか問題点が残っていて、主に3つあります。

  • 地図上の直線距離は実際の歩く距離でないこと
  • 待ち時間が考慮されていないこと
  • アトラクション数が絞られていること

これらを解決できればそれなりに役立つ何かができるかもしれません。

 おまけ

ちなみに、ディズニーランドの全アトラクション数は公式的に67あるそうです。
67個のアトラクションを考えたときの全組み合わせは94ケタ(!)の数です。

3600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 通り

(ちなみに64ケタが不可思議、68ケタが無量大数

こうなってくると全ルートを求めるのはとても大変です。
なので、前述の巡回セールスマン問題で考えられた様々なアルゴリズムが有効になってくるのです。
それらのアルゴリズムを駆使すれば、すべてのルートを調べなくても良かったりします。

数学者様々ですね!


おまけ その2(参考文献)

 

追記(2014/10/18)

後から気づいたんですが、スタート地点に戻ってきてないので、正確には巡回じゃないっすね…。

ということで、タイトルに偽りありでした。すみません。

*1:「じゃあ、なんで巡回セールスマン問題を出したんだ?」という感じですが、とりあえずこんなものがあるんですよ~という話題までに出してみました。

*2:正確にはどこからスタートしても良いことと、行き帰りの距離が同じことから 「7! / 2 」となりますが、簡単のため「 8!」としました。

*3:Ruby大好きなのでRubyで実装