Visualizing Dijkstra's, and A* Search Algorithm

先日話題になっていた最短経路探索問題を考察するにあたり、探索回数を如何に減らすかを主眼において考えてみました。それに伴い、いくつかの可視を行いました。


さて、順を追って考えてみましょう。以下は文字で提示されていた迷路です。

**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************


この問題を計算機で解くにはグラフ構造を用いるのが適切です。各節点を繋ぐ経路を元に、隣接した節点間の距離がそれぞれ等しくなるようなグラフとします。この距離をdとしておきます。


では初めに、ダイクストラアルゴリズムを伴った幅優先探索を検証します。幅優先探索にはFIFO、キュー構造を用いました。まずは、すでに訪れた節点にも再度訪れる条件として、節点群がどのような順番で探索されていくかを可視しました。

各節点に描画されている数値は開始地点から節点までの最短経路の距離を示しています。ここで式を導入しておきましょう。任意の節点を節点nとし、開始地点から節点nまでの最短経路の距離を最短経路コストg(n)とおきます。

この問題では隣接した節点間の距離は等しくdですので、節点n_iに接続している節点n_{i+1}の開始地点からの最短経路コストg(n_{i+1})は以下のように表すことが出来ます。

節点n_iに接続している節点n_{i+1}は複数存在している場合があるので、注意してください。

では、ある節点n_iから2回探索を進めた節点n_{i+2}を考えてみましょう。節点n_{i+2}は節点n_{i+1}からさらに1回探索を進めた節点であるため、開始地点からの最短経路コストg(n_{i+2})は以下のように表すことが出来ます。

これを一般化してみましょう。ある節点n_iからN回探索を進めた節点n_{i+N}の最短経路コストg(n_{i+N})は以下となります。

こう考えて行くと、FIFOには開始地点から節点nまでの最短距離コストg(n)が小さい順番で格納されるであろうことが分かります。したがって、FIFOを伴った幅優先探索では各節点までの最短経路コストg(n)がより小さいものから探索すると考えることが出来ます。そのため、目的の地点に到達した際も、最短距離コストg(n)は他のどの経路から到達した最短経路コストと同じか、より小さいことが保証されます。したがって、目的地点に到達すると同時に処理を打ち切ってもよいことが分かります。また、処理を打ち切ることにより、探索が訪れない節点も出てきます。目的の節点の右下の節点群がそのような節点となります。


さて、繰り返しとなりますが、隣接する節点間の距離が等しいグラフである場合、FIFOを用いた幅優先探索は最短経路コストg(n)が小さいものを優先して探索します。そのため、何れの経路から節点nに到達したとしても、初めてその節点に到達した経路の最短経路コストg(n)が最短であることが保証されていると考えることが出来ます。そのため、すでに訪れた節点を再度訪れる必要がなくなります。

すでに訪れた節点を再度訪れないようにすることを条件として、節点群がどのように探索されていくかを可視したものが以下となります。

この2つを比べると、探索回数が随分減っていることが分かります。


次にダイクストラアルゴリズムを伴った幅優先探索深さ優先探索の比較を行います。幅優先探索と異なり、ダイクストラアルゴリズムを伴った深さ優先探索では各節点nを訪れた時点で、開始地点から節点nまでの最短経路コストg(n)が最小であることが保証されません。言い換えれば、他の経路から到達した最短経路コストg(n)がより小さい場合がある、ということです。

最短経路コストg(n)を保証するには、その節点nに到達するであろう全ての最短であろう経路を探索するしか方法がありません。したがって、任意の節点に対して複数の経路が探索される可能性があります。

私の実装では、開始地点から目的の地点までの経路を6種類探索したようです。以下は、それら経路群の可視です。より色の濃い経路がより先に目的の地点に到達していることを表しています。

最短経路か否かはともかく、それぞれそれなりの経路を訪れているよう感じられたので、初めて目的の地点に到達した経路のみの可視も行なってみました。


以下はダイクストラアルゴリズムを伴った深さ優先探索の探索順序を可視したものです。節点nを訪れた際の最短経路コストg(n)を保証出来ないため、全ての節点を訪れていることが分かります。また、深さ優先探索と言われるだけあって、節点を訪れる軌跡の多くは経路そのものに重なります。そのため、軌跡としては少なく見えるかも知れません。


A*探索アルゴリズムダイクストラアルゴリズムを発展させたものです。開始地点から任意の節点nまでの推定最短経路コストをg*(n)、その節点nから目的の地点までの推定最短経路コストをh*(n)とすると、節点nを通る、開始地点から目的地点までの推定最短経路コストf*(n)を以下のように計算することが出来ます。

A*探索アルゴリズムの詳細は、A*(A-star:エースター)探索アルゴリズム|カンガルーハウスが大変秀逸ですのでそちらを参照してください。

さて、A*探索アルゴリズムを用いて探索する際の概念は以下のようになります。h(n)は節点nから目的の地点への最短経路です。通常は初めて節点nに到達した時点では判明していない経路です。また、ヒューリスティック関数h*(n)は節点nから目的の地点への直線距離とし、矢印で表しています。


さて、ダイクストラアルゴリズムを伴った幅優先探索の場合と同様に、ある節点nを訪れた際に開始地点から節点nまでの最短経路コストg(n)は保証されています。そのため、推定最短経路コストg*(n)をg(n)と置き換えることが出来そうです。式に反映すると、以下となります。

また、この問題の場合、隣接する各節点間の距離は等しいので、ある節点n_iの次に訪れる節点n_{i+1}における推定最短経路コストf*(n_{i+1})は以下のように考えることが出来ます。

ダイクストラアルゴリズムを伴った幅優先探索ではFIFOを用いました。これは、キューに格納している経路のうち、最短経路コストg(n)が小さいものから探索するためだったのでした。A*探索アルゴリズムでは最短経路コストg(n)ではなく、推定最短経路コストf*(n)が小さいものから探索を行います。推定最短経路コストf*(n)の算出に用いられる推定最短経路コストh*(n)は訪れた節点nによって変化する母数であるため、FIFOを用いると自然な実装とはなりません。そのため、A*探索アルゴリズムの実装では、最小ヒープをキューとして選択しました。

以下はA*探索アルゴリズムの探索の様子を表したものです。

ダイクストラアルゴリズムを伴ったものとは異なり、節点には推定最短経路コストf*(n)を描画しています(小数点以下は四捨五入しています)。


ここまで見てきたように、A*探索アルゴリズムで用いられる推定最短経路コストf*(n)は最短経路コストg(n)と比べ多少複雑なものです。さて、ではダイクストラアルゴリズムを伴った幅優先探索と同様、A*探索アルゴリズムでも訪れたことのある節点を再度訪れなくてもよいのでしょうか? それとも、深さ優先探索と同様、訪れなければならないでしょうか?

答えは訪れなくてもよい、となります。節点n_iに訪れる、最短経路コストg(n_i)が異なる2つの経路を考えると理解が容易です。この2つの最短経路コストをg(n_{i_A})、g(n_{i_B})とします。

すると、推定最短経路コストf*(n_i)は、経路によって異なった値を取ります。

しかし、上の式群にて推定最短経路コストh*(n_i)は等しいですから、g(n_{i_A})がg(n_{i_B})より小さい場合、f*(n_{i_A})もf*(n_{i_B})より小さいことが分かります。したがって、n_{i_A}はn_{i_B}よりも先に節点n_iを訪れる経路であることが分かります。

さて、すでに訪ねた節点は除外するようにしたA*探索アルゴリズムを適用した結果が以下となります。探索回数はこれまでアルゴリズムと比べ、かなり減りました。

まとめ

さて、今回はダイクストラアルゴリズムを伴った幅優先探索深さ優先探索、およびA*探索アルゴリズムに関して考察を行ないました。今回扱ったグラフは隣接する節点間の距離が等しく、また無向グラフであったため、グラフの探索を考察するのに大変的した題材であったと思います。

追記(2011/10/26)

用語の誤りを訂正しました(幅優先検索 => 幅優先探索)