先日、乗換案内で経路が出ない話を書いた。乗換案内はどういうプログラムになっているのか考えて試してみた。基本はダイクストラ法だろう。カーナビなら各地点間の所要時間が分かっていればいいのだが、電車や飛行機は時刻が決まっているので、時刻表のデータを用意して、各駅に何時に到着するのかを調べていく必要がある。
（以下、出発時刻が決まっている例で書くが、到着時刻の場合はゴールから逆にたどるだけで同じことだ）
ダイクストラ法だと、スタートから最も早く出発する電車にとりあえず乗って進むことになる。まず、次の停車駅の到着時刻を記録する。後から快速など速い列車が来て追い越す場合もあるので、各駅で乗換を調べる必要※がある。乗換駅があると、乗換をする場合としない場合でどちらが早いか分からないので乗換をした場合の探索もする。既に探索済みの駅に以前の探索より早い時間に到着した場合には、結果を更新する。探索を開始するのは、常に到着時刻が最も早い駅だ。こうすることで最も早い経路が（絶対に）出せる。
探索する地図が小さければこれだけでも動くだろうが、日本全体だとこれは現実的ではない。東京から大阪に向かう時にも、東北方面の探索を延々とやることになる。人間ならムダとわかるが、機械にはムダかどうかは分からないし、確実に最短経路を求めるには全部探索する※※必要がある。例えば、仙台駅に大阪駅まで1分で行ける「どこでもドア」が設置されていたとすれば、東京→仙台→大阪が最短になる。この可能性を否定できないならば、厳密な答えを出すにはあさっての方向でも探索するしかない。
ダイクストラにはA*という改良アルゴリズムがあり、これを使っていると思われる。A*では、スタートから現在地までの時間と現在地からゴールまでの時間の推定値の和（＝現在地を経由した推定所要時間）が小さい場所から探索をする。推定値が全ての地点で0の場合が単純なダイクストラのアルゴリズムになる。推定値の部分に何を使うかが腕の見せ所だ。すぐに思いつくのはゴールまでの直線距離を適当な数値で割ったものだろうか。これであさっての方向の調査は途中で止まるようになる。推定値をうまく設定しないと、「遠回りだが所要時間が短い」経路が出せなくなる。
現実には「どこでもドア」は存在しないが、飛行機はあるので遠回りだが所要時間は短い経路は多々存在する。先日の大阪-茨城の例で試してみる。夜の茨城発はバスの接続が良いので、かなり広い範囲で飛行機が勝つ。実験にちょうどいいので逆の茨城→大阪の経路で試してみた※※※。探索範囲の変更は茨城側でやるので、到着地は素直に神戸の三宮にした。到着時刻を飛行機での到着時刻（21:32なので、21:35）に設定して様子を見る。使ったのはYahoo乗換。
まず、空港へのバスに直接乗れる石岡。JRだと1時間も多くかかるので、当然飛行機が1位で出る。
出発地点を徐々に南（東京方面）に変えていく。空港からは遠くなり神戸とは逆向きに電車に乗る時間が増える一方、JRは東京に近くなり所要時間が減る。（以下、32分着が飛行機、22分着など32分以外がJR）
土浦 まだ飛行機が36分リード
牛久 飛行機が出なくなる。JRの最速は17:14発
では、経由地に茨城空港を指定して試してみる。
17:42発、まだ飛行機が28分リードだが経由指定なしだと出してくれない。やはりどこかで経路を足切りしているようだ。30分逆方向に電車に乗って、さらに30分バスに乗る経路を出すのは難しいだろう。言い方を変えると、最適な経路を出す保証はないということだ。
ここから先はいずれにせよ経由を指定していないと新幹線のルートしか出ないが続けてみる。
取手 飛行機が2分リード
我孫子 逆転、新幹線が15分リード
今度、時間があれば他の乗換案内はどうなのか実験してみよう。
関連 乗換案内をVBAでバッチ処理する
※現実的には快速や特急が止まる駅と乗換駅だけ調べれば十分なので、事前に指定してあると思う。
※※正確にはゴールの到着時刻が確定するまで＝ゴールにおける全経路の探索が完了するまで。
※※※羽田だと便数が多すぎて色々な便が出て煩雑だが、茨城空港なら1便しかないので分かりやすい。