全6路線の最短完乗ルートの検索に向けて

前回の計算で、5路線、東山線、名城線、名港線、鶴舞線、上飯田線の最短完乗ルートの計算に約45分掛かった。

目標は名古屋市営地下鉄の全6路線の最短完乗ルートの検索。

上記の5路線に桜通線を加えるだけだけど、プログラムを動かすといつまでたっても計算が終わらない。

どこのくら時間が掛かるのかを予想してみることにした。

今のプログラムで何とか5路線までは計算できる。

4路線、東山線、名城線、名港線、上飯田線と、これに桜通線を加えた5路線で計算時間とルート数を比較。

4路線、東山線、名城線、名港線、上飯田線

５路線、東山線、名城線、名港線、上飯田線

計算時間と検索ルート数は次の通り。

4路線に桜通線を加えることで、計算時間は約4800倍、検索ルート数は約3000倍以上になっている。

同じ5路線でも鶴舞線を桜通線に変えただけで計算時間が45分から200分、4.4倍になった。
区間数が、鶴舞線の6区間に対して、桜通線は7区間で1区間多いためと思われる。
1区間増えるとそこでの分岐が1回増えるので、他路線との交差の場合は単純計算で4倍。
4.4倍というのは妥当なところと言えそう。

前回の桜通線を除く5路線での計算時間は約45分(2707.3秒)、ルート数は230万(2,304,666)だった。
これに、桜通線を加えるには上記の比率、計算時間は4800倍、ルート数は3000倍する。

全6路線の計算時間は計算時間は21.6万分(=150日)、計算ルート数は69億と予想できる。
名古屋市営地下鉄の全6路線の最短完乗ルートの検索は、今のプログラムではまだまだ無理そう。


つづく。