カーナビの経路判断の仕組みについて

質問

カーナビ、或いはオンライン(Mapquest等）の経路判断の仕組みについて理解したいのです。

論文とか白書とかあったら教えてください。

回答No.2

gatten

最近見たテレビでカーナビの仕組みについて解説がありました。
http://www.nhk.or.jp/denno/nagare/17/04.html
論文とか白書でなくてごめんなさい。でも実際の放送を見て、自分の使っているカーナビのすごさを再確認しました。多少間違ってもゆるすことにします。
アルゴリズムは知恵比べですね。もちろん全部検索できたら良いけど、大事なところはしっかりと、省略すべきところは省略する。ですね。

参考URL：

http://www.nhk.or.jp/denno/nagare/17/04.html

お礼

これは、面白い番組ですね。とっても分かりやすく簡単に説明されています。

たいへん参考になりました。ありがとうございます。

回答No.1

teltel

最短経路を導き出すアルゴリズムとして代表的なものにダイクストラ法というものがあります。
インターネットワークのルーティングやカーナビにも利用されているものです。
下記に参考ＵＲＬを記載しますので、参照ください。

参考URL：

http://www.lab.me.sophia.ac.jp/~ishizuka/OC/spath_00.html

お礼

早々の回答ありがとうございます。

ダイクストラを使う場合、すべての道路情報が手元にないといけませんよね。情報量が多いことを考えると、何か階層的な仕組みを使って、ダイクストラ等のアルゴリズムを当てはめるのではないかと思われるのですが。

たとえば、アメリカの東海岸のとある住所から、西海岸のとある住所までの経路を知りたいとします。どうあっても、全米すべての道路を一元的に管理して、経路を計算するとは考えられませんよね。

このあたりのことについてご存知でしょうか？