カーナビの道路検索ロジック

質問

以前から不思議に思っています。
カーナビの道路検索の仕組みはどうなっているのでしょうか？
どうやってあのようなルートが探せるようになっているのでしょうか？
その道路検索ロジックが知りたいです。
出発地と目的地を直線で結んで、その直線に近い道路をつないでいるわけでも無いし。
ご存知の方、是非教えてください。

回答No.1

pythian

詳しくは知らないのですが、大雑把には多分こういうことだと思います。

1.道路を線、交差点やICを点としてグラフを作成
2.道路に探索で使う重みをつける
3.目的地までの重みが最小となる経路を探索する

重みとは優先度みたいなもので、渋滞していると大きく、空いていて広い道路だったりすると小さくなります。（順調な高速道路がいちばん小さいのかな？）

カーナビは、これ以外にも様々なものを加味しますので一概には言えないのですが、情報工学で教わった経路探索はこんな感じです。

お礼

情報工学では経路探索を習うのですか。面白そうですね。なるほど。道路に重みをつけて、最小になるように探索するのですね。これだと定量的に納得できます。しかし交差点の数なんて、それこそ星の数ほどありそうなのに．．．．。ありがとうございました。