ちょこっとシャーロックくらぶ☆コミュのナビの道の選び方

先日、引っ越しました。
新居から、高速入り口の道順をナビが選ぶと、行きと帰りで違う道を選ぶのです。確かに地図で見ても、どちらも同じくらいの距離なのですが、行きは必ず東側、帰りは必ず西側を選ぶのです。
何故なんでしょう？

コメント(2)

最初
全て
最新の40件

すごく初歩的な点で恐縮ですが、どこかに一方通行や、あるいは右車線と左車線で制限速度が違う道路があったりしませんかね？

で、もしこういった一方通行がらみでないとしますと、この問題は、専門的には大きく分けると最短路探索アルゴリズムの問題と、そのアルゴリズムに対する入力グラフの構成方法の問題の二つに分かれます。

1. 最短路探索アルゴリズム
この手のナビは、概ね最短路をダイクストラ法と呼ばれるアルゴリズムで探索しています（注：アルゴリズムというのは、“問題の解き方”のことです）。

で、フツーにこのアルゴリズムをプログラムにすると、

　・同じ距離の最短経路が二つある場合、必ず左若しくは右の経路を優先して出力する

みたいな性質を示します。

結果的に、往路では東、復路では西が優先される可能性があるのですね。

2. 入力グラフの構成法

もう一つ、往路と復路で経路が異なる可能性として、

　・ナビが、地図をどのように抽象化してから、ダイクストラ法を適用しているのか？

の問題があります。

最近のナビはなかなか進歩しておりまして、ネットワークに接続して、道路の現在の混雑具合を調べてから、経路を出してくれたりします。

すると、例えば通勤などの要因で、時間帯によって大きく渋滞するような道路が経路に入っていると、往路（朝）と復路（夕）で違った道を選択してくる可能性があるわけですね。

このように、ナビは必ずしも“地図の上での最短経路”を示しているわけではないのでして、可能な限り“乗っている人が短い時間で到着する”経路を探索するようプログラムされています。

と、まぁ今回はかなり専門的な解説となりました、分かりづらくて申し訳ありません。……下手に専門の知識が絡んでいると、言葉が難しくなって良くないですねぇ、にゅるにゅる。

[2] mixiユーザー 11月09日 18:22

専門的な解説をして頂いて、とっても嬉しいです。
こういう答えがほしかったのです