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 !!