Googleの旅行アプリで使われている280年前のアルゴリズムとは？

By Celeste RC

Googleが2016年9月20日にリリースした「Google Trips」は旅行に関する情報をまとめて管理できるアプリで、目的地までの移動方法や行き方、移動時間、観光地の場所や付近にあるレストランなど、さまざまな情報を元にして旅行の計画表を自動で作ることができます。Googleによれば、このGoogle Tripsに使用しているアルゴリズムは280年前のものを元にしているとのことで、その詳細をGoogleが公式ブログで明かしています。

Research Blog: The 280-Year-Old Algorithm Inside Google Trips
https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html

Google Trips - Google Play の Android アプリ
https://play.google.com/store/apps/details?id=com.google.android.apps.travel.onthego

Google Tripsは、現地に行く前に1日の詳細な予定を組むことが可能なアプリで旅行のアシスタント的な役割を果たしてくれ、最適な旅行のプランを自動で考えてくれるのですが、驚くべきことにこのアプリに使われているアルゴリズムは280年前に発案されたものだとのこと。

スイス人数学者のレオンハルト・オイラーは旧東ドイツにあった都市・ケーニヒスベルクと、その街にある7つの橋に関する数学的な論文を1736年に執筆しました。この論文では「一筆書きで7つの橋全てをわたることは可能か？」ということが書かれており、オイラーが出した答えは「不可能」というもの。不可能という答えにたどり着くのにオイラーは、陸地と橋のレイアウトを表現するために1つの手法を編みだし、後に「Geometriam Situs」と名付けました。

オイラーが発案したGeometriam Situsこそが、現代の数学の理論の1つである「グラフ理論」です。グラフ理論は以下の図のように、ノード(6つの接点)とエッジ(接点を結ぶ辺)からなるグラフに関する理論で、オイラーは陸地をノード、橋をエッジとして表現しました。

オイラーは「ケーニヒスベルクには当てはまらないものの、ノードに接するエッジの数が、各ノードで同じだった場合にのみ一筆書きが成立する」ということに気づきます。

Google ResearchはオイラーのGeometriam Situsに感銘を受け、「どうすればたくさんの観光名所を一度の旅行で回ることができるのか？」という疑問を解消すべく、これを「旅行日程問題」と名付けて調査を実施。この問題を解くには、「観光地のピックアップ」と「ピックアップした観光地を旅行日程に組み込む」という2つの目的を達成する必要があったとのこと。特に2つ目は「移動時間を短く」「観光名所が閉まっている時に訪れない」「美術館など同じような観光名所を連続で訪れない」などといった課題があり、この課題をクリアしながら効率のよいルートを検索するアルゴリズムの構築には、 大変手を焼いたそうです。

効率がよいルートの検索を可能にすべく、Googleはクリストフィードの近似アルゴリズムを使用し問題の解決に当たりました。クリストフィードの近似アルゴリズムを使用することで、「複数の目的地を結ぶ移動ルート」の中でも最短のものを検索結果で提示することができるようになったとのこと。以下の図はクリストフィードの近似アルゴリズムを使用してルートが絞られていく様子を表しています。

効率的なルート検索のアルゴリズムを構築した後は、観光名所を訪れることで得られるメリットや観光名所の入場料を観光名所ごとに計算。ユーザーが観光名所を訪れることで得られるメリットは、観光名所の人気・すでに訪れた観光名所との違いなどから導き出されるそうです。以下の図は、ロンドンの観光ルートを構築する様子で、一番左は「ウエストミンスター寺院からビッグベンまでを往復するルート」ですが、アルゴリズムを使うことで、一番右の「ウエストミンスター寺院からセントジェームズパーク、ビッグベン、バッキンガム宮殿、ハイドパークを回るルート」が提示されるようになっているのがわかります。

Google Tripでは、「私の友人はこんな場所もオススメしてくれている。また、観光に使えるのは午前中だけですが、午後の予定に組み込まれている観光名所も朝のうちに行きたい」といったユーザーからの個人的な要望に応えられるようなアルゴリズムを組み込んでいるとのことです。

最新のアプリに280年も前に発案されているのは衝撃的。オフラインでも使えるということで旅先で重宝しそうなGoogle Tripsは、記事作成時点でインストールこそできるものの日本語には対応しておらず、日本語版のリリースに期待がかかります。