改善：最短区間数に満たないルートを評価対象外にする

今のプログラムでは、5路線で45分とか200分掛かる。
前回の検証で、名古屋市営地下鉄の全6路線の最短完乗ルートの検索には150日もの時間が掛かるという予測。
抜本的な改善が必要ではあるけど、まずは今のプログラムを少しでも速くするためにプログラムコードを見直してみた。


ルートの評価、時間の計算に掛かるコストを削減
例えば、東山線と桜通線に限定すると路線は次のようになる。

この2路線は2ヵ所で交差していて乗換えができる。

それぞれに終端駅が2駅、合計4駅の終端駅がある

2路線で6区間あるので(上図参照)、最低でも6区間のルートでないと完全乗車ルートにはならない。
更に、終端駅では折り返しをするので、4駅の折り返して4区間余分に乗車する必要があるので6+4で10区間。
でも、スタート駅を終端駅にすれば、その駅での折り返しは不要。
更に、ゴール駅も終端駅のルートなら、その駅での折り返しも不要。
そう考えると、2区間少ないルートも成立する。
6+4-2 = 8区間

8区間がこの路線図での完乗ルートの最短区間数ということになる。
つまり、作成したルートが8区間未満なら、その路線を評価(所要時間の計算や比較)をする必要が無い。

他のケースでも同様。
東山線と名城線(環状線)だと路線は次のようになる。

この2路線は5区間で構成されていて、2ヵ所で交差していて乗換えができる。

終端駅は東山線に2駅だけで、名城線には無い。

よって、5+2-2=5で、最低5区間でルートが成立。

この路線図での完乗ルートの最短区間数は5区間。


プログラムを改善
最短区間数に満たないルートを評価の対象外にするようにプログラムを改善。

改善前、3路線(東山線、桜通線、名城線)

改善後、3路線(東山線、桜通線、名城線)

計算結果は同じ。
計算時間は、改善前が218.1秒、改善後が217.9秒。
改善効果はわずか0.1%弱。

最短区間数に満たないルートを評価の対象外にしたことによるコストの減少と、評価の対象にするかどうかの判断を行うコストがほとんど変わらないということなんだろうか。
それとも、プログラムの改善方法に問題があるのだろうか。


残念ながら、この改善の効果はほとんど無かった。

つづく。