Roboticsロボット技術の相談やコンサルティングについては、こちらからお問い合わせください。2019-02-23スポンサーリンク日常的にGoogleマップや乗り換えアプリなどで経路探索を行う方は多いと思います。これらの技術によって、僕たちは最適な道順を選んだり、目的地に早く着けたりすることが出来ます。今回からの記事では、この様な経路探索を行うために、グラフ理論を用いた経路探索問題について紹介したいと思います。スポンサーリンクContentsグラフ探索問題グラフとは地図をグラフで表す経路探索法まとめグラフ探索問題グラフ探索問題とは、グラフ理論におけるグラフについて、スタートからゴールまでの経路を探索する問題です。グラフとは下のようなグラフが与えられた場合を考えます。このグラフについて、〇はノード(節点、頂点)と言い、ノード同士を繋いでいる線をエッジ(枝、辺)と言います。2つのノードがエッジで繋がれていれば、そのノード間を移動可能です。反対に、2つのノードがエッジで繋がれていない場合は、そのノード間は移動できません。それぞれのエッジにはコスト(重み)がついており、2つのノード間のエッジを移動する際に与えられます。地図をグラフで表す今回の記事では、地図(マップ)をグラフ理論におけるグラフで表した場合を取り扱います。地図とグラフの関係は下の表の通りです。グラフに含まれるノードは、地図上における町や駅、ジャンクションにあたります。エッジはその街や駅をつなぐ道路や線路を表しています。エッジにつけられたコストとは距離や時間、値段などを表します。これら基に、それぞれの町を車で移動する場合の移動経路を距離を考慮しながら描いたマップは下のようになります。このようなマップについて、経路探索法を用いて経路を解くことで、スタートからゴールまでの経路を見つけます。与えられたマップについて、スタートからゴールまでの最短な経路を探索する方法には、様々な方法があります。深さ優先探索Dijkstra’s法A*アルゴリズムなどがあります。今後の記事では、これらの経路探索法について紹介しながら、それぞれの利点や欠点を紹介していきたいと思います。まとめ今回は、ルート案内や乗り換え案内などで用いられている経路探索を行うために、グラフ理論で扱われているグラフについて説明しました。グラフを用いて経路探索を行うための手法のリストを紹介をしました。次回からは、今回は名前だけ紹介した経路探索法について、それぞれ紹介していきたいと思います。コメントをキャンセルメールアドレスが公開されることはありません。Arduinoスターターキットこれからを始めたい人におすすめ。作りたいものは大体作れます。R3スマートロボットカーロボットを作ってみたい方におすすめ。Piを始めたい方におすすめ。基本的に必要なものが揃ってます。