公共交通機関を含めた経路探索

メモというか特許対策（になる？）というか・・・。

徒歩と鉄道、バスなどを利用した経路探索を行うには、各種時刻表を利用できればいいのですが、なかなかデータを集めるのが大変だったり、時刻表を利用できるように探索のアルゴリズムを拡張するのが困難だったりめんどくさかったりします。それに事前に大まかなルートを調べておきたいときなんかには、時刻表ほど詳細なデータはさほど重要でもないと思われます。すごい田舎の場合は別ですが。

1. 頂点にも自由に重みを設定できるようにダイクストラのアルゴリズムを拡張します。
2. 駅と駅をつなぐ辺の重みを、交通機関が駅から発車してから駅に到着するまでの時間にします。
3. 駅となる頂点の重みを、その交通機関の発車間隔から適当に決めた時間にします。
4. 徒歩は、時速4km程度と見積もってダイクストラで計算します。

ぜんさんのアドバイスを受けて改良してみました。

1. 交通機関の乗車用の頂点を作成します。（乗り換えなどを考慮するなら、普通、快速、など路線ごとに作成）
2. 駅頂点から交通機関乗車用の頂点までのコストを発車間隔と駅構内の移動時間を考慮して決定します。（下車時には待ち時間がないので、コストは乗車時にのみの有向グラフを作成）
3. 各路線の乗車用の頂点間に移動のみ（出発してから到着するまで）にかかる時間を設定します。
4. 徒歩は、時速4km程度と見積もってダイクストラで計算します。（A*では、直線距離、LAESAともに最適解は求まらない）

ただ、電車を使えるようにすると、A*で直線距離は使えなくなります。