この10月にモバイルファクトリーに新卒で入社し、エンジニアとして働いています。)、全国4000の駅の思い出を集めながら日々全国の駅と路線の構造に想いをはせていました。モバファクのアドベントカレンダーに参加することになりましたので、また別の路線図の最長経路問題について書くことに決めた次第です。掲載されている、きっぷのルール等を定めた旅客営業規程を読んでみると以下の記述を見つけられます。第43条の規定にかかわらず、次の区間内各駅発着の場合、又は同区間を通過する場合の片道普通旅客運賃は、最も短い経路のキロ程によって計算する。通過となる普通乗車券又は回数乗車券を所持する旅客は、その区間内においてはその乗車券の運賃計算経路にかかわらず、う回して乗車することができる。世界有数の複雑な路線を持つ東京メトロであれば、きっと思いもよらない長い迂回路を取ることができるだろうと期待できます。この最長経路を考えてみることにしました。この記事では以下の条件を満たすような経路をコンピュータを駆使して求めることを目標にします。出発駅から到着駅までの経路の営業キロの和が最長となるような迂回経路を求める。運賃は東京メトロの片道乗車券の上限である310円までとし、初乗り運賃にこだわることはしない。出発駅の改札を通った後は、到着駅まで改札を出ることはない。通過した駅にもう一度訪れてゴールとする経路は考えない。条件2、3、4を変えることでさらに面白い問題にすることが可能ですが、今回は簡単のため単純な条件を採用しました。注:読者から条件4が不足していることを指摘していただきました。ありがとうございます。GitHub)を採用しました。GraphillionはPythonとC++を組み合わせて作られた高速にグラフ問題を解くためのライブラリです。具体的なアルゴリズムは割愛しますが(これも面白いのでまたの機会に!)、ライブラリの威力は次の動画でで実感できるでしょう。youtu.be元々私はC#で実装した自前の最長経路探索アルゴリズムを使っていたのですが、この記事を書くに当たってそれより数十倍高速なGraphillionを知ってしまい、思わず乗り換えることになりました。これがあればJR線最長片道切符の旅の経路計算で度重なる領域分割に苦労することもなかったでしょう。おまけに、早口で言うと「グラフ理論」に聞こえるところもおしゃれで好きです。インストールとサンプルの実行Grapillionのインストールはpipで簡単に行うことができます。Python3の両方に対応しています。2であることに気をつけてください。GitHub)、実際のGraphillionの使い方を見ていきます。説明のため問題と解答を一部改変しています。一部の例外を除いて、旅客営業を行う日本の鉄道路線では駅間を双方向に列車が行き来しています。そのため駅をノード、路線をエッジとする無向グラフとして路線図を見ることが可能になります。解くにあたっては各駅間の営業キロが必要になるので、営業キロを重みとする重み付き無向グラフを採用します。括弧内の数字が駅間距離を表しています。この路線図に対して以下の問題を解きます。東京から品川までの経路は何通りでしょう?東京から品川までの最長経路はなんでしょう?四ツ谷を経由して東京から品川まで至る経路には何があるでしょう?これらの問題はGraphillionを利用することで簡単に解くことができます。形のタプルで表し、リストに格納します。そのリストを用いてset_universe()でグラフを生成すれば準備完了です。3.7)]gs.set_universe(universe)まずは東京から品川までの経路を列挙したグラフセット(条件を満たすグラフの集合)を生成します。'品川')これだけで東京から品川までのすべての経路が分かりました。第1問はpathsのlenを取れば求められます。print(len(paths))続いて、全経路pathsからmax_iter()を呼び出すことで重みの降順でソートされた経路を取り出すことが可能になります。よって第2問はその最初の経路を取ればよいことになります。print(next(paths.max_iter()))最後に、あるノードを通過するような経路をincluding()によって抽出することができます。第3問はこれを使って四ツ谷を通るようなグラフセットのみを得ることができます。print(paths.including('四ツ谷'))グラフセットの選択により複雑な条件を課すことで、グラフで表現できる様々な問題に対処できます。Graphillionを使って最長片道経路を求める前処理ここからは本題の東京メトロの路線図で最長経路問題を解いていきます。Grapillionに路線データを読み込ませてグラフにします。残念ながら駅間距離を取得するAPIを見つけることができなかったので、各種資料にあたって調べたものを手動でCSVにまとめます。...これを2次元データの解析に便利なライブラリpandasを用いて読み込み(今回はCSVを読んでいるだけですが)、すべてのグラフの元になるユニバースを生成します。上のJR線の例とは違って、後に最長経路の距離を求めるために、タプルで表したエッジをキーとするディクショナリとして重みweightsを持っています。v['dist']gs.set_universe(univ)例えば東京から池袋までの最長経路を求め、その距離を求めるには以下のように書けばよいです。weights[edge]print(distance)あとは出発駅と到着駅について考えられるすべてのパターンを試し、2駅の最長の経路が最も長かったものが求める最長片道経路です。駅名が異なるが乗り換え可能な場合の扱いここからは単純に路線を読み込むだけでは処理できないケースについて見ていきます。東京メトロでは赤坂見附駅と永田町駅のように、駅名が異なる場合でも改札を出ることなく乗り換えが可能な駅が存在します。Graphillionでユニバースを生成する際には駅名が同じであれば同一のノードとしてみなされますが、駅名が異なる場合は乗り換え可能であるにも関わらずエッジでつながらないことになります。そこで、これらの駅は駅間営業キロ0kmの線路でつながっているとみなし、重み0のエッジとして実装しました。...ある組の駅の間に2路線存在する場合の扱いさらに東京メトロでは2路線が並行している区間がいくつかあります。有楽町線と副都心線は小竹向原以北において線路を共有していますし、細かいところでは霞ヶ関-日比谷などが該当します。Graphillionはあるノードの組に対しては1つのエッジでしかつなぐことができません。そこで、該当する駅はノード名を(路線名)駅名とし、別々のノードとした上で「駅名が異なるが乗り換え可能な駅の扱い」と同様に重み0のエッジでつなぎました。乗り換え注:当初渋谷にて銀座線と半蔵門線の改札内乗り換えが可能としていましたが、誤りのため訂正いたします。それに伴って上の例を表参道に変更しました。副都心線と半蔵門線は改札内で乗り換えが可能です。改札外乗り換えになる場合の扱い東京メトロでの最長経路問題を複雑にしているのが改札外での乗り換えです。池袋駅や大手町駅には、乗り換えのために一度改札外に出るためのオレンジ色の改札があります。それに関して旅客営業規程では以下の条件を定めています。この規定は特に初乗り運賃での最長経路を求めようとするタイプの問題において重要になります。このような改札外での乗り換えが必要な駅は東京メトロのサイトで案内されている以下の13駅です。第3項にもあるように、実際は大手町と新宿三丁目は改札内で乗り換えが可能です。(日比谷線と半蔵門線)築地駅‐新富町駅(日比谷線と有楽町線)今回はオレンジ色の改札を通らなければならない乗り換え方法については認めないというルールにしたので、「ある組の駅の間に2路線存在する場合」「ある組の駅の間に2路線存在する場合」から、該当する乗り換え表現エッジを削除しました。2回同じ駅を通る場合を除く最後に2回同じ駅を通ってしまう場合を排除します。「ある駅の組の間に2路線存在する場合」においてノードの重複を避けるために路線名を頭につけた駅名を採用しましたが、このままでは同じ駅を別の路線で2回通ることが可能になってしまいます。そこで、先に求めた経路から同じ駅を2回通る場合を引いて、残った経路の集合から最長片道経路を求めます。有楽町線の千川と副都心線の千川をどちらも通る場合を考えます。それぞれはincludingを指定することで抽出できるため、それらの積を全体から引けばよいことが分かります。senkawaこの操作を該当する他の駅に対しても実行することで、2回同じ駅を通過する経路を除くことができます。(路線名B)駅名)の形のエッジが経路に含まれる場合を除いておく必要があります。注:当初記載されていた情報では方法の説明が不十分であったため、但し書きを追加しました。!和光市から西船橋まで78.8kmの経路です。都内南西でトリッキーな動きをするのが面白いですね。注:更新に伴って求めた経路を路線ごとに色分けしました。まとめ今回はグラフ検索ライブラリGraphillionを用いて、東京メトロの改札内乗り換え最長片道経路を計算してみました。旅客営業規定の解釈とアルゴリズムの正確性について100%の自信があるわけではございませんので、実際にこの経路で旅行される際は自己責任でお願いいたします。ちなみに、私なら自分が間違っているのが怖いので必ず1日乗車券を買って行きます。このような限界に挑むような経路の他にも、「旅行に行くけど目的地をどうやったら効率よく回れるかな」といったカジュアルな問題にもGraphillionは適用することができます。18:00Graphillionで東京メトロの最長経路問題を考える【追記あり】Tweet次のページ採用情報モバイルファクトリーは技術好きなエンジニアを募集しています!興味を持った方はぜひ応募してみてください。2020に参加してきました!~エンジニアのみなさんへ、採用って楽しいよ!月別アーカイブスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。