最短路

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

Google Map 

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

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

Yahoo Map

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

Microsoft (Bing) Map 

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

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

OpenStreetMap

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

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