改善：余分なルートを作らない

検索を早くするにはいくつかの方法が考えられる。

• 処理を効率化する
• 評価対象のルート数を減らす

もちろん、速いPCを使うとか、C/C++などで書き直すというのも高速化には有効だけど、C/C++はアルゴリズムが固まってからStep2で行うことにしているので今回はなし。
速いPCを使うのは当然効果があるけど、速いと言っても普通に手に入るPCであれば、せいぜい数倍。
アルゴリズムを見直すのが高速化の効果が高い。

ではどうするのか。
ルートを作るルールを1つ追加することにした。

• 同じ駅間(セグメント)を通るのは2回まで
• 《追加》 所要時間がそれまでの最短時間を上回ったら、それ以降のルートは検索しない

作ったルートの所要時間がそれまで求めた完乗ルートの所要時間を上回ったら、ルートが完成していなくてもそれ以降のルートは作らないようにする。
未完成のルートの所要時間を求める(ルートを評価する)ので、そのコスト(処理時間)が余分に掛かるが、せっかく完乗ルートができても所要時間が最短でなければ意味がないので。
評価対象のルートを大幅に減らせるはず。

試してみた。
藤が丘駅スタートで、東山線、名城線、名港線の3路線でルート検索。

左が旧バージョン、右が新バージョン

評価回数(intRouteNumMax)は、228,983回から17,623回に大幅に削減された。(元の7.7%)
処理時間も152.4秒が18.5秒に短縮。(元の12.1%)
当然、結果は同じ。

旧バージョンではできなかった、東山線、名城線、名港線、鶴舞線の4路線を試してみた。
1時間経っても終わらない。
まだまだ先は長い。


つづく