AI好きな人の備忘録

経路探索の概要では経路探索とはなんぞやをざっくりと説明した。
このページでは経路探索を実現するためのアルゴリズムを４つ紹介する。
各アルゴリズムの詳細はそれぞれのページを用意するので、そちらにて解説していく。


・深さ優先探索
わかりやすく木構造のグラフを例にしてみる。
木構造には必ず「根」と呼ばれるノードがあり、根を親のノードとする「子」と呼ばれるノードがある。
深さ優先探索は根のノードからできるだけ遠く、しかも、既に調べたノードの子であるノードから調べていく方法である。
以下の図で深さ優先探索を行うとどのような順番でノードを訪れるだろうか？
探索開始ノードは１段目の根とし目標ノードは２段目の子ノードとする。

深さ優先探索では下の図のようにノードを訪れる。
少々わかりづらかったかもしれないが、文章で説明すると以下のようになる。図を追いながら確認していこう。
根→２段目の親→３段目の親→４段目の左の子→３段目の親→４段目の右の子→３段目の親→２段目の親→２段目の子→２段目の親→根→１段目の子
という順番になる。
我々人間ならば「右に１段降りれば１ステップで終了」と思うはずだが、深さ優先探索ではなんと１２ステップもステップを踏んで目標ノードへ到達している。
１２ステップも踏む原因は最初の方に言った「根のノードからできるだけ遠く、しかも、既に調べたノードの子であるノードから調べていく」という深さ優先探索独特の手法を取っているためだ。
このアルゴリズムの詳細と実装は深さ優先探索のページで解説する。


・幅優先探索
こちらも深さ優先探索同様、木構造を例にして紹介していく。
このアルゴリズムは深さ優先探索と似ている。
違う所はノードの訪れ方だ。
深さ優先探索は「一番深いノードを真っ先に訪れようとする」のに対し幅優先探索は「隣り合うノードを真っ先に訪れる」。
では深さ優先探索で使った図を再び持ち出す。探索開始ノードは根とし目的ノードは２段目の子とする。
幅優先探索ではどのように訪れるだろうか？

幅優先探索では以下の図のようなノードの訪れ方をする。
文章で説明すると
根→２段目の親→２段目の子
となる。
深さ優先探索とは違いわずか３ステップで目的ノードへ到達する。
次は４段目の右の子を目的ノードとしてみよう。探索開始ノードは根とする。
どのように訪れるだろうか？



４段目の右の子を目的ノードとした場合、ノードの訪れ方は以下の図のようになる。
根→２段目の親→２段目の子→３段目の親→３段目の子→４段目の左の子→４段目の右の子
という順番で訪れる。
こういったノードの訪れ方になるのも幅優先探索独特の「隣り合うノードを真っ先に訪れる」ことに由来している。
このアルゴリズムの詳細と実装は幅優先探索?のページで解説する。


・ダイクストラ法
ダイクストラ法には深さ優先探索や幅優先探索には無かった大きな特徴がある。
「コスト・重み」と呼ばれるものだ。
この「コスト・重み」というのは現実世界で例えると「移動距離や移動時間」のようなものと考えてくれれば良い。
深さ優先探索や幅優先探索ではこの「コスト・重み」という考えが無かったため、例えば「最も総移動時間の少ない道はどのように通ればよいか？」という答えを出すことは保証出来ない。いくら時間がかかっても良いのでとにかく目的地に到達するための道を教えてくれという質問には深さ優先探索でも幅優先探索でもしっかり保証をしてくれる。
しかしダイクストラ法では「コスト・重み」という考えが備わったため「最もコストの低い経路」を求める事が出来る。
すなわち最短ルートを求めることが可能ということだ。


・A*（エースター）
A*はダイクストラ法に新たな概念である「ヒューリスティック」を追加し、ダイクストラ法よりも効率的に最短経路を求める事が出来るアルゴリズムである。
要はダイクストラ法の改良版だ。
ヒューリスティックとは人間で言うところの「経験則」のようなものである。
例えば食事処を探す際場所にもよるが大抵は駅前に食事処が集中している場合が多く人は自然と駅前に向かって歩みを進める。
人間は暗黙的に自らの経験に基づき「確実では無いがある程度、目的に近い解答」を出すことが出来る。
AIや計算機科学でも同様の事が可能でありA*はそれを利用している。
ゲームAIでは必ずと言っていいほど経路探索にはこのA*が用いられている。


次の章ではA*を解説していく。
初見では目を回す事もあるかもしれないが、ゆっくりと考えていけば意外とシンプルなアルゴリズムなので是非閲覧していただきたい。