最短路

地図上で最短路を出してくれるサービスは便利で,最近では専用ナビなどは必要なくなった.大学の演習用に,使われている地図や最短路アルゴリズムについて調べてみた.

Google Map 

ゼンリンをやめて自社の地図を利用.利用し初めのときは色々変な箇所があったが,どんどん改良しているようだ.このように,走りながら修正するのは日本の企業にはできない芸当だ.最短路もそこそこ速い.試しに,青森から香川の最短路を出してみたところ,数秒で以下の結果が得られた.


画像1


距離と時間は1272km, 16:24.

Yahoo Map

地図はゼンリンで表示は提携したmapbox.最短路は不明.時間は多少長く5秒程度.1254km, 18:48
画像2

Microsoft (Bing) Map 

地図はやはりゼンリン.最短路はたぶんMS ResearchにGoldbergがいるので,reachとlandmarkの組み合わせ(だと推測).1423km, 19:25


画像3

同じゼンリンマップなのに,出てくるルートが異なる(条件は一緒).Goldbergのは厳密解のはずなので,Yahooのがヒューリスティクスの可能性が高い.

OpenStreetMap

地図はオープンソース.最短路はOSRM(highway hierarchy) なので高速で厳密解.1197km, 15:36と他とくらべてかなり短時間で着く.制限速度で計算しているはずだが,距離まで短いのは不思議だ(実際にルートも違う).


画像4

このように,地図によって得られる最短路が違う.全部いっぺんに呼んでくれるサービスなどがあったらありがたい.


この記事が気に入ったらサポートをしてみませんか?