※ 最新の算出プログラムは以下をご参照ください
psyduck-take-it-easy.hatenablog.com
だいぶ間隔が空いてしまいましたが皆さんはお元気でしょうか?
さて、皆さんが長距離を移動する際にJRを使う方が多いと思います。JRで移動する際にはみどりの窓口や指定席券売機で乗車券等を購入します。
この乗車券は「JR線」を「一筆書き」で「同じ駅を2度通らない」という条件であればどんな乗車券でも購入する事が出来ます。この条件で最も長いのが「最長片道切符」です。これに関してはいくつか作品が出ています。
決定版 列島縦断 鉄道12,000km 最長片道切符の旅【NHKスクエア限定商品】
- 出版社/メーカー: NHKエンタープライズ
- 発売日: 2008/04/23
- メディア: Blu-ray
- この商品を含むブログを見る
さて、肝心のルートですが、これは「デスクトップ鉄」さんによって、新線開業や廃線があった際に発表されています。
ただ、デスクトップ鉄さんはエクセルのソルバー(注:Excel2010以降では動作しない)を用いた手法で計算しているので、今回は別の方法を模索しました。
今回はこちらのブログでGraphillionを用いたやり方が紹介されていたので、それを使いました。
データセットを用意して、コードは経路順で出力されるように工夫しました。
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だった路線等を含めたルートでの最長片道切符のルート算出に挑んでみたいと思います。
ちなみに、現在のルート図は下のリンクにあります。