- ベストアンサー
最短経路が知りたい
ある地域の観光地を5箇所ほど回りたいと思っています。出発地点をAとしてB,C,D,Eを最短時間で回れるナビみたいなのはありますか。
- ofuroyoifu
- お礼率85% (331/387)
- 道路・高速道路
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
＞最短時間で回れるナビみたいなのはありますか。 ありません。 「複数の指定した地点を最短距離で巡回する経路を求める問題」を「巡回セールスマン問題」と言い、経由地点が増えるほど、解法が複雑になり難解になる事が知られています。 巡回セールスマン問題 https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3%83%AB%E3%82%B9%E3%83%9E%E3%83%B3%E5%95%8F%E9%A1%8C ５～６地点でもかなりの計算量になり、有料回避や一方通行などの制約事項を含めて最短経路を求めるのは、とても時間が掛かり実用になりません。 将来、ナビ用コンピュータが高性能になり、今の千倍～１万倍くらい高速に計算可能になれば、実用化されるかも知れません。
お礼
有難うございます。やはりそうですか、狭い範囲の各地点だと余計にいろいろな条件が絡んできますね。単純に時計周りか反時計回りでやってみます。