山手線でグラフ理論 ダイクストラ法を試す。
グラフ理論のダイクストラ法は基本的部分であるけれど取っつきにくかった。
リンクをたどり最短で目的地到達とか、到達距離とか時間を計算する手法が
グラフ理論なのだけれど、数字ばかりで論理的理解では理解できるものの
エモーショナルな部分で??と腑に落ちていなかったので、エモーショナルな
部分でも感応できるように、山手線+αのグラフとSciPyのダイクストラ法を
試してみたいと思います。
プログラム仕様
各駅を点として山手線、中央線、京浜東北線などをグラフ化し、これで目的地
までの時間など試します。
試すファンクションはscipy.sparse.csgraphdijkstraを使います。
詳細は下記リンクを参照。
SciPy.org - scipy.sparse.csgraph.dijkstra
山手線+αグラフ
駅コード
駅区間移動時間(分)
までの時間など試します。
試すファンクションはscipy.sparse.csgraphdijkstraを使います。
詳細は下記リンクを参照。
SciPy.org - scipy.sparse.csgraph.dijkstra
山手線+αグラフ
駅コード
駅 | コード |
---|---|
東京 | 0 |
神田 | 1 |
上野 | 2 |
日暮里 | 3 |
池袋 | 4 |
渋谷 | 5 |
品川 | 6 |
新宿 | 7 |
川崎 | 8 |
横浜 | 9 |
駅区間移動時間(分)
駅 | 駅 | 移動時間(分) |
---|---|---|
東京 | 品川 | 8 |
品川 | 渋谷 | 13 |
渋谷 | 新宿 | 6 |
新宿 | 神田 | 12 |
東京 | 神田 | 2 |
神田 | 上野 | 5 |
上野 | 日暮里 | 4 |
日暮里 | 池袋 | 12 |
池袋 | 新宿 | 6 |
品川 | 川崎 | 14 |
川崎 | 横浜 | 12 |
Pythonサンプルプログラム
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import pprint
# 駅
station_def = ['東京','神田','上野','日暮里',
'池袋','渋谷', '品川','新宿', '川崎','横浜']
# 区間データ
Station_section = [
['東京', '品川', 8],
['品川', '渋谷', 13],
['渋谷', '新宿', 6],
['新宿', '神田', 12],
['東京', '神田', 2],
['神田', '上野', 5],
['上野', '日暮里', 4],
['日暮里', '池袋', 12],
['池袋', '新宿', 6],
['品川', '川崎', 14],
['川崎', '横浜', 12]]
# 駅コード辞書登録
stations_no, stations_name = {}, {}
for i, s in enumerate(station_def):
stations_no[s] = i
stations_name[i] = s
print(s, i)
# 駅区間データの生成
section = []
for ss in Station_section:
st1 = stations_no[ss[0]]
st2 = stations_no[ss[1]]
section.append([st1, ss[0], st2, ss[1],ss[2]])
section.append([st2, ss[1], st1, ss[0], ss[2]])
section = np.array(section)
pprint.pprint(section)
# csr_matrixの生成
row = np.array(section[:,0].astype(np.int32))
col = np.array(section[:,2].astype(np.int32))
data = np.array(section[:,4].astype(np.float64))
N = max(np.max(row), np.max(col)) + 1
print('N=', N)
graph = csr_matrix((data, (row, col)), shape=(N, N))
print('{}\n'.format(graph.toarray()))
start_st_indx = [0, 9]
# ダイクストラ法
distance_mat, processors = dijkstra(graph, directed = False, indices =start_st_indx, return_predecessors = True)
print('始点からの最短時間(分)')
print('{}\n'.format(distance_mat))
print('各駅の直前の駅')
print('{}\n'.format(processors))
for stidx, st in enumerate(start_st_indx):
# 最短時間
print('%d:%s駅からの最短時間(分)'%(stidx+1,stations_name[st]))
for i, d in enumerate(distance_mat[stidx]):
print(' {0}({1}) --> {2}({3}) {4}分'.format(stations_name[st], st, stations_name[i],i, d))
# 各駅の直前の駅
print ('\n 各駅の直前の駅')
for i, d in enumerate(processors[stidx]):
if 0 <= d:
print(' {0}({1}) <-- {2}({3})'.format(stations_name[i], i, stations_name[d], d))
print()
プログラムは東京(0)駅発と横浜(0)駅発を計算します。
なお、鈍行の移動時間だけで計算し、駅での停車時間、
快速、湘南新宿ラインなどは除外しています。
dijkstra()のパラメータindicesに開始駅のコードを入力します。
動作環境
結果
東京駅発
1:東京駅からの最短時間(分)
東京(0) --> 東京(0) 0.0分
東京(0) --> 神田(1) 2.0分
東京(0) --> 上野(2) 7.0分
東京(0) --> 日暮里(3) 11.0分
東京(0) --> 池袋(4) 20.0分
東京(0) --> 渋谷(5) 20.0分
東京(0) --> 品川(6) 8.0分
東京(0) --> 新宿(7) 14.0分
東京(0) --> 川崎(8) 22.0分
東京(0) --> 横浜(9) 34.0分
各駅の直前の駅
神田(1) <-- 東京(0)
上野(2) <-- 神田(1)
日暮里(3) <-- 上野(2)
池袋(4) <-- 新宿(7)
渋谷(5) <-- 新宿(7)
品川(6) <-- 東京(0)
新宿(7) <-- 神田(1)
川崎(8) <-- 品川(6)
横浜(9) <-- 川崎(8)
駅での停車時間がない分だけ早い気もしますが、
まあ、妥当かなともおもえます。
横浜駅発
2:横浜駅からの最短時間(分)
横浜(9) --> 東京(0) 34.0分
横浜(9) --> 神田(1) 36.0分
横浜(9) --> 上野(2) 41.0分
横浜(9) --> 日暮里(3) 45.0分
横浜(9) --> 池袋(4) 51.0分
横浜(9) --> 渋谷(5) 39.0分
横浜(9) --> 品川(6) 26.0分
横浜(9) --> 新宿(7) 45.0分
横浜(9) --> 川崎(8) 12.0分
横浜(9) --> 横浜(9) 0.0分
各駅の直前の駅
東京(0) <-- 品川(6)
神田(1) <-- 東京(0)
上野(2) <-- 神田(1)
日暮里(3) <-- 上野(2)
池袋(4) <-- 新宿(7)
渋谷(5) <-- 品川(6)
品川(6) <-- 川崎(8)
新宿(7) <-- 渋谷(5)
川崎(8) <-- 横浜(9)
こんなところでしょうか。
感想
こういうことはめんどくさいせいか?グラフ理論を開設するWebページではやっていません。
まあ、当然かな。
でも、品川-横浜間の京浜急行だったら?とか、新宿-横浜間の湘南新宿ラインは
どうなの?これだといろいろイメージがわきます。
おもしろいですね。
まあ、当然かな。
でも、品川-横浜間の京浜急行だったら?とか、新宿-横浜間の湘南新宿ラインは
どうなの?これだといろいろイメージがわきます。
おもしろいですね。
関連
参考
写真出典
#python
#経路探索
- 関連記事
-
- 正規分布の円を描く、正規分布 2-D表現。 (2021/04/25)
- SciPy 最短経路問題を解いてみる (2021/04/18)
- 山手線でグラフ理論 ダイクストラ法を試す。 (2021/04/16)
- Scipy least_squares()で非線形最小二乗問題を解いてみる (2021/04/07)
- SciPyで求根を求める (2021/01/08)
スポンサーサイト
コメント