「python Adventvent Calendar 2017 16日目」TDLアトラクションの組み合わせ最適化をしてみる

初のQiita Advent Calendarへの参加です!
今回は、東京ディズニーランドのアトラクションの組み合わせ最適化問題について考えようと思います。

そろそろクリスマスシーズンなので、「クリスマスディズニー」を楽しむカップルや学生もいることでしょう。そんな方にむけて、アトラクション選定の最適化アルゴリズムを送りたいと思います。

「具体的に何を基準にどう最適化するか」については文字で説明するよりも下の表をみてもらった方が早いと思いますので、まずは表を見てみましょう。

アトラクション名 優先度 平均待ち時間(分) 平均体験時間(分)
オムニバス 2 4 6
ジャングルクルーズ 8 28 10
カリブの海賊 10 18 15
ウエスタンリバー鉄道 4 18 15
魅惑のチキルーム 2 11 10
スイスファミリーのツリーハウス 3 0 9
ビッグサンダーマウンテン 9 74 4
カントリーベア 1 16 17
蒸気船マークトレイン号 3 15 12
トムソーヤ島いかだ 7 6 3
スプラッシュマウンテン 6 95 10
ビーバーブラザーズのカヌー探検 2 20 10
プーさんのハニーハント” 8 88 5
ホーンテッドマンション 5 67 15
ピーターパンの空の旅 10 48 3
空飛ぶダンボ 1 41 2
白雪姫と七人の小人 3 26 3
ピノキオの冒険旅行 3 22 2
イッツ・ア・スモールワールド 5 18 10
アリスのティーパーティー 1 13 2
キャッスルカルーセル 1 12 2
ミッキーのフィルハーマジック 7 60 15
シンデレラのフェアリーテイル・ホール 2 20 8
ロジャーラビットのカートゥーンスピン 2 38 4
ガジェットのゴーコースター 7 23 1
モンスターズインク~ライド&ゴーシーグ~ 10 99 4
バズ・ライトイヤーのアストロブラスター 8 69 4
スペースマウンテン 6 69 3
スター・ツアーズ 7 13 5

今回は、各アトラクションに付与した「優先度」を基準としてアトラクションの選定をしていきます。
表の優先度は私の主観で適当に設定しました。
ルールは以下の通り。
・アトラクションを楽しむのに使える時間は5時間(待ち時間+体験時間)
・アトラクション間の移動時間を無視し、それにかかる移動コストは最適化の対象外とする

上記の通り、移動コストは完全に無視しているため、最短経路を計算することはできませんが、テーマパークで遊ぶのだから一定の自由度を確保しておいた方がよいのです。

ここからは実際に、5時間という限られた時間の中で「優先度」の合計ポイントを可能なだけ高められるような組み合わせを考えていきます。

貪欲法動的計画法で計算し、出力結果を軽く比べてみます。

言語はpython、数値計算ライブラリであるnumpyを使用します。


参考にしたサイト
平均待ち時間:http://disneyuramania.com/
体験時間:http://www.tokyodisneyresort.jp/

貪欲法

まずは、貪欲法で計算していく。

貪欲法とは、巡回セールスマン問題や集合カバー問題などの厳密解を計算するのが困難なNP完全/NP困難な問題に対して、局所的な最適化を行なっていくことで、それなりに良い近似解を得ようとする方法です。
計算が単純なため高速であり、最適解にも近くなりやすいためよい近似アルゴリズムになるといわれています。

貪欲法でアトラクション選定を行う

以上、実行すると以下となる。

与えられた時間が経過するまで、ひたすら優先度が高いアトラクションを順に選定していくという、非常に単純明快なアルゴリズムです。

合計優先度ポイントは39で、合計所要時間は265分

制限時間まで35分余り、各アトラクションの所要時間と優先度を厳密に比較し最適化を行なったわけではありません。
とはいえ、単純なアルゴリズムでそれなりの解を得られるということがわかります。

動的計画法

次は、動的計画法で計算していきましょう。
動的計画法とは、対象の問題を部分問題に分割し、その計算結果を記録・再利用しながら(メモ化)、最終的に対象の問題の最適解を求める方法です。

貪欲法では、最適解に近い近似解を求めたが、今度は一つの最適解を求める。

動的計画法では、グリッドを用いる。
グリッドのセルの意味合いは解く問題によって異なる。今回は、以下の通り。

アトラクション名\分 1 2 3 10 38 48 300分
オムニバス 0 0 0 2 2 2 2
ジャングルクルーズ 0 0 0 2 8 10 10
カリブの海賊
スター・ツアーズ

最初の二つのアトラクション以外省略しているが、このように最適化対象の「優先度」を順にセルに入れいく。
1分単位で列を分割し、それぞれの時間での最適解を順にセルに記入していく。
・計算列 < 該当アトラクションの合計所要時間 → 一つ前の行・同列の値を入れる
・計算列 = 該当アトラクションの合計所要時間 → 一つ前の行・同列の値 or 該当アトラクションの優先度ポイント
・計算列 > 該当アトラクションの合計所要時間 → 一つ前の行・同列の値 or 該当アトラクションの優先度ポイント + 計算列 – 該当アトラクションの合計所要時間の列にあたる優先度ポイント

最終的に、制限時間である5時間の中で、もっとも優先度が高くなるような組み合わせを見つけるのです。
容量が決まったナップザックに、できるだけ価値の合計が高くなるように物を詰め込もうとするナップザック問題と同系統の問題です。

動的計画法でアトラクション選定を行う

今回は再帰を使用せず、愚直にfor文で回していきます。

グリッド計算には、行列を使用し、1行ずつ(1アトラクションずつ)計算を行なっていく。
グリッドの作成が完了すると、answer_best_attraction関数を呼び、グリッド更新を辿り、解となるアトラクションを特定していく。

以上、実行すると以下となる。

合計優先度ポイントは68で、合計所要時間は298分
時間の余りはわずか2分であり、この時間で遊べるアトラクションは存在しない。
貪欲法では、解として「モンスターズインク~ライド&ゴーシーグ~」が出力されたが、動的計画法では出力されなかった。
これは、いわゆるコストパフォーマンスが低いからです。優先度は最高の10だが、時間がかかりすぎるのです。

おわりに

以上、アルゴリズム初心者がつらつらと綴りました。「記事のこの部分間違っている!」だとか「もっとこうした方がいいよ!」という方がいれば、ご指摘いただけると幸いです!

Python, 数学

Posted by tanatyu


PAGE TOP