地下鉄が複雑すぎるので、経路の組み合わせが天文学的に増えるおそれを解消するため、まず経路の予想を立ててから計算しよう、と考えた。
1.駅情報に、運賃計算のための営業キロに加えて、緯度と経度を導入する。
2.まず最短経路予想をする。始点から終点までの緯度と経度を比較して、上りと下りどっちに進めば目的地に付きそうかを判断しながら、1本経路を作る。
例えば丸ノ内線新宿駅から半蔵門線半蔵門駅に行きたければ、新宿と半蔵門を比較すると半蔵門は東北方向にあるから荻窪行きではなく池袋行き方面に進めばいいだろうなぁ、と予想する。
で、最短経路の運賃を先に計算しておく。
3.乗り換え駅ごとに分岐して経路探索する。ただし、探索中に最短経路の運賃をオーバーしたらそこの経路は捨てる。
4.乗り換えのない終点駅について、しかも目的地に到達しない経路は捨てる。
5.最短経路より運賃が安い経路があったら、最安値を更新してそれより運賃の高い経路を全部捨てる。
以上で、計算量をかなり減らせるのではないか。まず東京メトロ版から作ってみようと思う。

Tweet