2016.07.31

祝Pokémon GOリリース！Neo4jでレアポケモンゲットだぜ！ #neo4j

この記事は1年以上前に投稿されました。情報が古い可能性がありますので、ご注意ください。

neo4j_logo

木内です。最初にお詫びします。タイトルは釣りです。

さて、日本のみならず世界的に大ブームとなっているポケモンGO。みなさんも楽しんでいますか？ちなみに私はレベル11です。ジムには怖くてまだ行けていません。

レベルも上がってくると自宅や会社の近くのポケモンも一通りゲットし、なんとも物足りなくなってきます。またいろいろ調べていると新宿御苑にはピカチュウが出るなどの情報もちらほらと聞き、「よし、次の休みにはレアポケモンを取りに行ってみるか・・・」など考え始めたりするものです。

また様々なIT企業(?)のマーケティング担当もこのブームになんとかあやかりたいといろいろネタを探し求める不思議な光景になっています。かくいう私もその一人であることは否めません。このブログもそんなよこしまな動機で書かれています。ごめんなさい・・・。

では前口上はこのくらいにして、クリエーションラインらしくまじめにやってみましょう。

レアポケモンってなに？

通常のプレイでは入手できないポケモンで、例えば以下のようなものがよくレアポケモンと呼ばれているようです。

ピカチュウ
イーブイ
ガーディ
カモネギ
サンド
ディグダ
パウワウ
コイル
ビリリダマ
ルージュラ
エレブー
ポリゴン
ラプラス

・・・けっこういっぱいありますね。夏休みのお子さんならともかくとして、お父さんお母さんには結構厳しい。

さらにこれらのレアポケモンは出現場所が決まっているようです。ちなみに私が調べた範囲ではそれぞれ以下のような場所に出るようです。

ピカチュウ: 新宿御苑
イーブイ: 世田谷公園
ガーディ: 新宿御苑
カモネギ：代々木公園
サンド: 代々木公園
ディグダ: 日比谷公園
パウワウ: 水元公園
コイル: お台場海浜公園
ビリリダマ: 井の頭公園
ルージュラ: 大宮公園
エレブー: 上野公園
ポリゴン: 渋谷
ラプラス: 江ノ島

だいぶ広範囲に散らばっていますね・・・。Googleマップに書きだしてみるとこんな感じです。

https://drive.google.com/open?id=1Ktf_tYgJ9GaiaGvR7TPCidy_y_8&usp=sharing

できればレアポケモンを全部ゲットしてご家庭の話題にしたり、同僚に自慢したいものです。とはいうもののこれだけ広く散らばっているとポケモンスタンプラリーよりも難易度が高いと言えるでしょう。子供に一人で出かけてこいと言うにはあまりに過酷ですし、サラリーマンであるお父さんお母さんに与えられた休暇は限られています。なんとか効率的に回ってゲットし、いい夏の思い出にしたいものです。

経路探索アルゴリズム

実はこの問題は「巡回セールスマン問題」もしくは「ハミルトン閉路問題」と呼ばれるグラフ経路探索問題に属します。いきなりめっちゃまじめな方向になりましたが気にしないで進めましょう。要するに「出発点から複数の通過点を全て通過し、出発点に戻る最短の経路を探索する」という問題に答えを出すための理論です。

さらにこの「巡回セールスマン問題」は数学的にけっこう難易度の高い問題である、"NP困難"問題に属しています。NP困難の定義自体かなり難しく一般の人が理解することも大変なのですが、誤解を恐れずに言えば「計算量があまりに多すぎるためコンピュータを使って計算してもひょっとしたら解けないかもしれない問題」という意味です。「ハミルトン閉路問題」は「巡回セールスマン問題」の条件を一部限定することによって、"NP困難"である「巡回セールスマン問題」の一部をより難易度が低く、時間をかければ解くことができる"NP完全"問題に変化させたものです。

今回はポケモンをゲットする経路を「ハミルトン閉路問題」として解いてみることにしましょう・・・といきたいところですが、残念ながらneo4jにはハミルトン閉路問題を解くためのライブラリが搭載されていません。Python NetworkXにはまさに hamilton_path なるハミルトン閉路問題を解くためのライブラリがありますが、グラフデータを独自形式で持つ必要があるため、neo4jと連携して解くことができません。

残念ですが今回は自前で探索アルゴリズムを実装し、ブルートフォースで最短経路を導くことにします。つまり総当りで探索することになるのですが、では探索するべき経路はいくつあるのでしょうか。

上記で例示したレアポケモンスポットは11箇所あります。これらのスポットを回る順番を順列組み合わせで求めると 11! = 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 39,916,800 。なんと約4000万通りの経路があります。これの最短経路をいちいち手で計算していたらそれだけで夏が終わってしまいます。目的は真のレアポケモンゲッターになることであったり楽しい夏の思い出を作ることであって、経路を調べることではありません。ですので、難しい問題はコンピュータに任せましょう。

では、実際に計算を始めていきます。

経路をNeo4jでグラフデータにする

上記でレアポケモンがどこにいるかはわかりました。電車で移動すると仮定して、電車の経路を含めたグラフデータを作成しましょう。以下のURLのNeo4jグラフデータ定義をクエリウィンドウに貼り付けます。

https://raw.githubusercontent.com/m-kiuchi/neo4j-pokemongo/master/pokemongo.neo4j

以下の図のようなグラフができました。それぞれのポケモン出現場所の最寄り駅や、駅間の経路も定義されています。駅間のリレーションにはどの程度の時間がかかるかの情報も含まれています。

pokemongo-1

経路探索と移動コストの算出

neo4jでは任意の2頂点間の最短経路を算出する関数を持っています。以下のように使用します。

MATCH path=allShortestPaths((a)--(b))
WHERE a.someProperty = 'hogehoge' AND b.someProperty = 'fugafuga'
RETURN path

これで1つの経路の中にある、1つのレアポケモンスポットから次のスポットへの移動は最短の経路を選択することができます。グラフデータの経路探索の場合、グラフの中に循環経路などが含まれていると単純な探索ではクエリが収束しない場合があるので知っておくと便利です。

また探索した個々のリレーションが持っている移動コストを合計するには以下のようなクエリを実行します。

MATCH path=allShortestPaths((a)-[r*]-(b))
WHERE a.someProperty = 'hogehoge' AND b.someProperty = 'fugafuga'
WITH path,reduce(s = 0, rel IN r | s + rel.cost) AS totalCost
RETURN path

プログラムと実行結果

以下が上記を統合した経路探索プログラムです。

https://github.com/m-kiuchi/neo4j-pokemongo/blob/master/pokemongo.py

以下がプログラムの実行結果です。全ての経路探索に要した時間は約18分でした。

OOOOO.O.OO..O.....O.....O.....O.OO.....
(中略)
Num of traversal route: 39916800
All route has traversalled
-----
calculated fastest path to Rare-Pokemon-master !!
(401, 372, 378, 379, 374, 373, 381, 382, 377, 375, 376, 380, 401)
estimated duration: 15.00 hours
Good luck !!

経路探索で計算したオススメルート

以下がNeo4jを活用した経路探索で算出した最短のレアポケモン探索ルートです！とはいうものの算出した移動時間のみで15時間、各公園でポケモンゲットする時間を入れた合計所要時間は18時間に及びます。また算出したルートには食事の時間や休憩、トイレの時間なども入っていません。あまりに過酷です。

まさか試す人はいないとは思いますが、以下が算出された最短巡回ルートです。

06:00AM: クリエーションライン社を出発。秋葉原駅に向かう
06:16AM: 秋葉原駅から総武線に乗り新宿駅へ
06:31AM: 新宿駅で降りる。徒歩で新宿御苑へ
07:00AM: 新宿御苑着。ピカチュウとガーディをゲット！
07:15AM: 新宿御苑を出発。徒歩で新宿駅に向かう
07:45AM: 新宿から中央本線に乗り吉祥寺へ向かう
08:05AM: 吉祥寺駅着。徒歩で井の頭公園へ
08:15AM: 井の頭線公園着。ビリリダマをゲット！
08:25AM: 井の頭公園を出発。徒歩で吉祥寺駅に向かう
08:35AM: 吉祥寺駅から中央本線で新宿駅へ
08:55AM: 新宿駅着。埼京線に乗り換え大宮駅へ向かう
09:35AM: 大宮駅着。東武野田線に乗り換え大宮公園駅へ
10:00AM: 東武大宮公園駅着。徒歩で大宮公園へ
10:10AM: 大宮公園着。ルージュラをゲット！
10:25AM: 大宮公園を出発。徒歩で東武大宮公園駅へ
10:35AM: 東武大宮公園駅から東武野田線に乗り大宮駅へ
10:50AM: 大宮駅着。JR埼京線に乗り新宿へ
11:30PM: 新宿駅着。JR山手線に乗り換え原宿駅に向かう
11:45PM: 原宿駅着。徒歩で代々木公園へ
11:55PM: 代々木公園到着。カモネギとサンドをゲット！
12:15PM: 代々木公園を出発。徒歩で原宿駅に向かう
12:25PM: 原宿駅からJR山手線で渋谷駅に向かう
12:40PM: 渋谷駅着。東急田園都市線に乗り換え三軒茶屋駅に向かう
12:50PM: 三軒茶屋駅着。徒歩で世田谷公園に向かう
13:05PM: 世田谷公園到着。イーブイをゲット！
13:15PM: 世田谷公園を出発。徒歩で三軒茶屋駅に向かう
13:25PM: 三軒茶屋駅から東急田園都市線で渋谷駅に向かう
13:40PM: 渋谷駅着。渋谷駅を出てポリゴンをゲット！
14:00PM: 再び渋谷駅からJR湘南新宿ラインに乗り横浜駅に向かう
14:35PM: 横浜駅着。東海道線に乗り換え藤沢駅に向かう
15:05PM: 藤沢駅着。江ノ島電鉄線に乗り換え江ノ島駅に向かう
15:25PM: 江ノ島駅着。徒歩で江ノ島へ
15:45PM: 江ノ島着。ラプラスをゲット！
15:55PM: 江ノ島を出発。徒歩で江ノ島駅へ
16:05PM: 江ノ島駅より江ノ島電鉄線で藤沢駅へ
16:25PM: 藤沢駅着。JR東海道線に乗り換え横浜駅に向かう
16:55PM: 横浜駅着。そのままJR東海道線で品川駅へ
17:25PM: 品川駅着。そのままJR東海道線で新橋駅へ
17:40PM: 新橋駅着。ゆりかもめに乗り換え台場駅へ
18:05PM: 台場駅着。徒歩でお台場海浜公園へ
18:15PM: お台場海浜公園到着。コイルをゲット！
18:25PM: お台場海浜公園を出発。台場駅に向かう
18:35PM: 台場駅からゆりかもめで新橋駅に向かう
19:00PM: 新橋駅着。JR山手線に乗り換え有楽町駅へ
19:15PM: 有楽町駅着。徒歩で日比谷公園へ
19:25PM: 日比谷公園到着。ディグダをゲット！
19:35PM: 日比谷公園を出発。徒歩で有楽町駅へ
19:45PM: 有楽町駅着。JR山手線で上野駅まで
20:15PM: 上野駅着。JR常磐線に乗り換え北千住駅へ
20:35PM: 北千住駅着。東京メトロ千代田線に乗り換え金町駅へ
20:55PM: 金町駅着。徒歩で水元公園へ向かう
21:25PM: 水元公園到着。パウワウをゲット！
21:35PM: 水元公園を出発。徒歩で金町駅に向かう
22:05PM: 金町駅より東京メトロ千代田線に乗り北千住駅へ
22:25PM: 北千住駅着。JR常磐線に乗り換え上野駅へ
22:45PM: 上野駅着。徒歩で上野公園へ
22:55PM: 上野公園到着。エレブーをゲット！
23:05PM: 上野公園を出発。徒歩で上野駅へ
23:15PM: 上野駅着。JR山手線で秋葉原駅へ
23:30PM: 秋葉原駅着。徒歩でゴールであるクリエーションラインへ
23:40PM: クリエーションライン到着。ゴール！！

さいごに

下心まる出しで始めた本記事ですが意外にもなかなか見れるものになったなあ・・・というのが本音です。いちおうタイトルはぎりぎりセーフというところでしょうか。算出されたルートはさすがに1日で回るのは厳しすぎますので、現実的には2日にわけてゆっくり風景などを楽しみながら探索するのがいいでしょう。

Neo4jを活用した経路探索は、今回の記事意外にもアイデアしだいで様々なケースに応用できると思います。ご興味を持っていただけたのであれば幸いです。

ではまた！