駆け出しエンジニアの作業ノート

駆け出しエンジニアが作業ノート風にまとめるページ(関係無い事もしばしば)

Graphillionを使って最長片道切符のルートを算出する

だいぶ間隔が空いてしまいましたが皆さんはお元気でしょうか?

 

さて、皆さんが長距離を移動する際にJRを使う方が多いと思います。JRで移動する際にはみどりの窓口指定席券売機で乗車券等を購入します。

 

この乗車券は「JR線」を「一筆書き」で「同じ駅を2度通らない」という条件であればどんな乗車券でも購入する事が出来ます。この条件で最も長いのが「最長片道切符」です。これに関してはいくつか作品が出ています。

 

最長片道切符の旅 (新潮文庫)

最長片道切符の旅 (新潮文庫)

 

 

 さて、肝心のルートですが、これは「デスクトップ鉄」さんによって、新線開業や廃線があった際に発表されています。

 

http://www.desktoptetsu.com/saichohensen.htm

http://d.hatena.ne.jp/desktoptetsu/

 

ただ、デスクトップ鉄さんはエクセルのソルバー(注:Excel2010以降では動作しない)を用いた手法で計算しているので、今回は別の方法を模索しました。

http://www.geocities.jp/longest_route/download1.htm

 

今回はこちらのブログでGraphillionを用いたやり方が紹介されていたので、それを使いました。

 

halpha656.hatenablog.com

 

データセットを用意して、コードは経路順で出力されるように工夫しました。

 

 

from graphillion import GraphSet as gs
import gc

def root_calc():
filename =
f = open(filename, "r", encoding="utf-8")
lines = f.readlines()
f.close()
univ = []
for line in lines:
dat = line.split(",")
dat[2] = float(dat[2])
edge = tuple(dat[0:3])
univ.append(edge)
del dat
del edge
gc.collect()
w = gs.set_universe(univ)
start = ""
end = ""
paths = gs.paths(start, end)
del w
gc.collect()
for path in paths.max_iter():
#print(path)
root_print(path, start, end)
break

def root_print(path, search, end):
another = ""
for i in path:
if search in i:
root_list = list(i)
print(root_list)
path.remove(i)
root_list.remove(search)
another = root_list[0]
break
else:
another = search
continue
if another != "":
root_print(path, another, end)


if __name__ == '__main__':
root_calc()

 

トウトウ,トウシナ,6.8,東海道,東京→品川
トウシナ,トウオマ,2.4,東海道,品川→大井町
トウオマ,ハマカワ,9.0,東海道,大井町→川崎
ハマカワ,ハマツミ,3.5,東海道,川崎→鶴見
ハマツミ,ハマヒナ,5.3,東海道,鶴見→東神奈川
ハマヒナ,ハマハマ,1.8,東海道,東神奈川→横浜
ハマハマ,ハマフナ,17.7,東海道,横浜→大船
ハマフナ,ハマチサ,12.1,東海道,大船→茅ヶ崎
ハマチサ,ハマコツ,19.1,東海道,茅ヶ崎国府津
ハマコツ,ハマオタ,6.2,東海道,国府津→小田原
ハマオタ,シツミシ,36.8,東海道,小田原→三島
シツミシ,シツヌマ,5.5,東海道,三島→沼津
シツヌマ,シツフシ,20.0,東海道,沼津→富士
シツフシ,シツシツ,34.0,東海道,富士→静岡
シツシツ,シツカケ,49.1,東海道,静岡→掛川
シツカケ,シツシハ,53.1,東海道,掛川新所原
シツシハ,ナコトヨ,11.2,東海道,新所原豊橋
ナコトヨ,ナコオカ,32.3,東海道,豊橋→岡崎
ナコオカ,ナコナヤ,36.8,東海道,岡崎→金山
ナコナヤ,ナコナコ,3.3,東海道,金山→名古屋
ナコナコ,ナコヒワ,4.0,東海道,名古屋→枇杷島
ナコヒワ,ナコキフ,26.3,東海道,枇杷島→岐阜
ナコキフ,キトマイ,49.6,東海道,岐阜→米原
キトマイ,キトクサ,45.5,東海道,米原草津
キトクサ,キトヤシ,16.7,東海道,草津→山科
キトヤシ,キトキト,5.5,東海道,山科→京都
キトキト,オサシオ,39.0,東海道,京都→新大阪
オサシオ,オサオサ,3.8,東海道,新大阪→大阪
オサオサ,オサアマ,7.7,東海道,大阪→尼崎
オサアマ,コヘコヘ,25.4,東海道,尼崎→神戸
 

 

データセットは上記の様にしました。JRの駅には各駅ごとに電略記号が存在し必ずカナ2文字で省略されます(一部例外あり)。ただ、地理的に離れている場合ですと同じ略記が使い回されている場合があります。(例:熊谷と熊本の「クマ」等) そこで、各駅の略記の上に駅を管轄する支社の略記を被せて、重複が起こらないようにしました。

 

現在のルートでは、「稚内」と「肥前山口」がそれぞれスタートとゴールになっており(ルートの関係上逆は不可能)スタートとゴールにはそれぞれ対応する略記を入れます。

 

結果、現在デスクトップ鉄さんが発表しているルートとほぼ同じになりました。ルート上「肥前山口」は2度通る(2回目でゴール)ので、その部分を補完する必要があります。今後は、かつて、国鉄及びJRだった路線等を含めたルートでの最長片道切符のルート算出に挑んでみたいと思います。

 

ちなみに、現在のルート図は下のリンクにあります。

 

http://mikaka.org/kohorogi/rail/lop/railmap/mapindex.cgi?route=54