どうやって計算すればいいのか～ルート計算のアルゴリズム

最短完乗ルートの検索。
まずは力まかせ探索で完乗ルートを順番につくり、乗車時間を計算(評価)。
乗車時間が最短のルートを求める。

完乗ルートを作るためには、

1. スタート駅を決める
2. 行き先を1つ決める
3. 分岐駅にきたら、分岐先を順番に試す
4. 全線乗車(すべての駅間=セグメント)を1回以上通過するルートができたら1ルート完成
5. すべてのルートを試す

実際にプログラムを書いて動かしてみるとルートがまったくできない。
例えば藤が丘をスタートすると、

• 本山駅まで進む
• 藤が丘駅に進む
• 本山駅に進む
• ：
• ：

を繰り返してしまう。

そこで、以下のルールを追加。
同じ駅間(セグメント)は2回までしか通らない
つまり、

• 藤が丘から本山まで進む
• 本山から藤が丘まで進む
• 藤が丘から本山まで進む → 藤が丘～本山間を3回通ったので1つ戻って次
• 本山に戻る
• 今池まで進む .... 藤が丘へのルートの検索は終わったので本山から次の駅間に進む

やってみた。
ルートはできたけど、検索が終わらない。
例えば、名古屋市営地下鉄全6路線を藤が丘駅スタートの場合、こんなルートが検索された。

他にもたくさんあるけど、とても最短ルートとは思えない。
数時間動かしても終わらない。


つづく。