Graphillionで最長片道切符のルート探索(2) 本州内のルート探索
前回、Graphillionを用いて北海道内のルートを探索することに成功したが、次は本州内のルートを探索してみる。
とりあえず計算
本州内の最長ルートということで、前回と似たようにまずはデータを準備して、中小国→小倉のルートを数え上げた上で最長のものを表示すればよい。
しかしまず最初の問題として、本州の路線図は北海道のそれに比べて規模がはるかに大きい。そのため手打ちで路線図を作っていくのは現実的ではない。そこで、SWA氏製作のLOP toolkit(
http://www.swa.gr.jp/lop/lop_a032.htmlにて公開
)に同梱された路線データedges.csvを読み込んで、2004年3月時点での最長経路を計算してみた。
edges.csvを読み込むスクリプトは以下の通り。
filename = 'edges.csv' f = codecs.open(filename, 'r', 'utf-8') lines = f.readlines() f.close() univ = [] univ2 = [] for line in lines: dat = line.split(',') dat[1] = int(dat[1]) dat[2] = int(dat[2]) dat[3] = float(dat[3]) edge = tuple(dat[1:4]) edge2 = tuple(dat[1:3]) if edge2 in univ2: print "Duplicate edge:", line err = 1 else: univ2.append(edge2) univ.append(edge) if err: print "Please check the duplicate edges and try again." exit() gs.set_universe(univ)
前に書いたように、Graphillionでは2つの頂点を結ぶ辺は1つしか扱えないので、重複があった場合は処理を中断させている。
edges.csvを読み込むと、重複する辺が5つ(北上→一ノ関,横浜→大船,福山→三原,三原→海田市,岩国→櫛ケ浜)出てくるので、対策をしておく。
そして、前回と同様のスクリプトで、中小国から小倉までのルートを数え上げ、最長のものを表示してみる。
さすがにグラフが大規模なだけあって、北海道のように一瞬で終わったりはしない。しかし、それでも手元のPCで、pathsメソッドを実行するのに45秒程度、最長のものを表示するのに10秒程度で済む。
SWA氏のLOP toolkitを使用してGLPK(v4.52)を用いると数分程度かかった。Graphillionを使うと解き直しの手間もかからないので、現状ではこの方法が最速と言えるのではないだろうか。
なお、得られた経路集合に対して、len()メソッドを用いてその総数を調べると、実に471,754,961,437,722,794,251,171,200通り(!)という結果が出る。
得られたルートを、edges.csvの情報をもとにわかりやすく表示してみる。
for eline in lines: dat = eline.strip().split(',') linename = dat[-2] staname = dat[-1] stacode1 = int(dat[1]) stacode2 = int(dat[2]) edge = tuple([stacode1,stacode2]) if edge in longest: print u'{0},{1}'.format(linename,staname).encode("utf-8")
出力は以下の通り。なんとなく眺めれば経路が浮かぶ・・・だろうか？？
津軽,中小国→青森 東北４,青森→野辺地 東北４,野辺地→八戸 東北新幹線,八戸→盛岡 山田,盛岡→茂市 山田,茂市→釜石 釜石,釜石→新花巻 釜石,新花巻→花巻 東北,花巻→北上 北上,北上→横手 東北,一ノ関→小牛田 大船渡,一ノ関→気仙沼 陸羽東,小牛田→古川 奥羽,秋田→大曲 羽越,秋田→余目 (以下略)
特例への対応
これを眺めると、今回探索した最長経路はSWA氏の解とやや異なっている。異なる点は、
の2点である。ともに運賃計算上の特例に起因するものだが(詳細はhttp://www.swa.gr.jp/lop/lop_a014.htmlも参照)、せっかくなので、Graphillionで対処してみる。
まず、岩国-櫛ケ浜は、この区間で山陽本線を使用してはならないという制約を加える。Graphillionでは、グラフ集合のうち特定の頂点や辺などの要素を含まない部分集合を返すexcludingメソッドが存在するので、一行で済む。
paths2 = paths.excluding([(299, 300)]) # 山陽,岩国→櫛ケ浜
次に、九州への入り方だが、幡生-新下関と新下関-小倉の同時使用を禁止する。これには、「幡生-新下関と新下関-小倉を両方使うグラフの集合」を求め、元のグラフ集合から除外する。
hatabu = paths2.including([(314, 315)]) # 山陽,新下関→幡生 prohibit = hatabu.including([(314, 318)]) # 新幹線,新下関→小倉 paths3 = paths2 - prohibit
得られたpaths3を先ほどの表示スクリプトで眺めると、SWA氏の算出したルートに一致することが確認された。めでたしめでたし。
