Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

超覚えやすいグラフの探査アルゴリズム

グラフの経路探査で有名なダイクストラ法,A*探索を深さ優先探索(DFS)・幅優先探索(BFS)とのアナロジーで理解できることに気づきました。これを覚えておけば,スクラッチから何も参照せずにダイクストラ法,A*探索のコードを書けるようになります。
(以下の説明は,ある程度アルゴリズムを理解していることを前提としています。「超分かりやすい」でない点に注意ください)

グラフ探査の抽象化コード
グラフ探査を抽象化したコード(C++風擬似コード)は次のようになります。
Search()
{
  Container que;                      // 抽象コンテナ ・・・(1)

  // スタート地点をキューに入れる
  Vertex s(スタート地点);
  que.push(s);

  while( !que.empty() ){
    Vertex v = que.pop();
    if( isGoal(v) )                   // ゴールに到達したら終了
      return;
    while( Vertex w = adjacent(v) ){  // vに隣接する頂点wを順番に得る
      if( Condition(w) ){             // 探索候補選択の条件 ・・・(2)
        que.push(w);
      }
    }
  }
}
グラフ探索のエッセンスだけを抜き取るとDFS,BFS,ダイクストラ法もA*法もこのようなコードで表すことができます。 (実際には,経路・訪問済み記録等のコードが足されます)

「(1)コンテナ」と「(2)探索候補選択の条件」が各アルゴリズムで異なってきます。

DFS,BFS

DFSの場合は,コンテナに「スタック(LIFO)」を用います。BFSの場合は,「キュー(FIFO)」を用います。

探索候補の条件は,DFS・BFSともに「wが未訪問である」という条件になります。

A*

A*探索の場合は,コンテナに「優先度付きキュー(priority queue)」を用います。優先順位は次の式で決まります。

f*(v) = g(v) + h*(v)

g(v) はスタート地点から頂点vまでの距離(ステップ数,辺の重みの総和等),h*(v) は頂点vからゴール地点までの見積距離を示します。"*"表記はヒューリスティック(発見的)関数であることを示しています。

h*(v) は 実際のゴールまでの最短距離 h(v) に対して,次の式を満たすと,

0 <= h*(v) <= h(v)

A*探索は最短の経路を見つけることを保証します。

探索候補の条件は,

「wが未訪問 or  (prior f*(w) > new f*(w))」

となります。頂点wが訪問済みの場合,それまでのwの見積もり値(prior f*(w))に対して,新しい経路(v→w)の見積もり値(new f*(w))が小さい場合には再度探索候補として採択します。

ダイクストラ法

ダイクストラ法の場合は,コンテナに「上書き可能な優先度付きキュー」を用います。優先順位は「スタートから頂点vまでの距離」となります。
コンテナへの格納(push)は,初めて頂点vへ(経路候補として)到達したときにそのときの距離で格納します。その後の探索で,頂点vへのより短い距離の経路候補が見つかった場合には,その距離値で上書きします。このため,「上書き可能な優先度付きキュー」が必要となります。

探索候補の条件は,

「wが未訪問 or (prior D(w) > new D(w))」

となります。prior D(w)はこれまで見つかっている頂点wへの最短距離,new D(w)は新しい経路(v→w)による距離を示します。
各頂点vのD(v)の初期値をINT_MAX等にすることによって,「wが未訪問」という条件チェックを省くことが可能です。

前述のようにコンテナへのpush()は,すでに頂点wの要素が格納済みの場合は,新しい距離値で上書きとなります。C++ STLでは,このようなコンテナはないので,set で erase(),insert()を組み合わせる,または自前でコンテナを実装する等の処理が必要です。

経路の記録

DFS,BFS,ダイクストラ法では,queからpop()された段階で頂点vへの経路が確定します。

また,DFS,BFSは未訪問点のみpush()しますので,push()する段階で頂点vへの経路が確定します。ダイクストラ法の場合は,上書きでpush()しますので,(pop()される前の)最後のpush()で頂点vへの経路が確定します。

DFS,BFS,ダイクストラ法での各頂点への経路情報は,頂点に対応する一次元配列を用意し,push()時にどの頂点から遷移したかを記録しておけば十分です。一つ前の頂点を順に辿ることでスタート地点までの経路を得ることができます。

一方,A*探索の場合は,ある頂点vについて(別の経路で)何度も評価される(何度もpop()される)可能性があります。すなわち,pop()された段階でも頂点vへの最短経路は確定しません。このため,経路情報はコンテナに入れる要素(Vertex)に記録して持ちまわる必要があります。

まとめ

まとめると下表のようになります。

 

コンテナ

探索候補の条件

優先順位

DFSスタック未訪問
BFSキュー未訪問
A*優先度付きキュー未訪問 or
  旧f*(w) > 新f*(w)
f*(v)
  =g(v)+h*(v)
ダイクストラ上書き
優先度付きキュー
未訪問 or
  旧D(w) > 新D(w)
D(v)

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://msirocoder.blog35.fc2.com/tb.php/71-62da131c
この記事にトラックバックする(FC2ブログユーザー)

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。