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)
スポンサーサイト

DevQuiz 2011

今年もDevQuizに参加しました。スライドパズルはいい問題でした。去年よりも盛り上がっていたように思います。

スライドパズルの結果は 4969/5000 残り31問で時間切れ。壁の本当の難しさに気づくことが遅れてしまったのが敗因です。DevQuiz2011


以下,考えたこと等をメモしておきます。

  • 基本的な考え方は,盤面をノードとしたグラフの探索で良いはず。
  • ノード数は,6x6のボードで36! 不可能な盤面もあるので 36!/2 かも。どちらにしても広大な探索空間となることは間違いない。
  • いかに沢山の探索をこなせるかと,無駄な探索を排除できるかがカギになるはず。
  • とりあえず,参考文献をあたる。手元の「アルゴリズムクイックリファレンス」に,ずばりそのものスライドパズルが扱われている。
  • グラフの探索はA*で良さそうだ。
  • とりあえず,ヒューリスティック関数はマンハッタン距離(MD)で試してみる。h*=MD×2でサクサクと解ける(もちろん解けない問題も多くある)。
  • 他も調査。下記のサイトが参考になりそう。
        15パズル自動解答プログラムの作り方
  • 反復深化(IDDFS,IDA*)という考え方があるらしい。 前述の参考書にもキーワードはあった。
  • 反復深化は評価値の閾値を変えながら何度も探索を実行するものらしい。
    • (理解が浅いだけかもしれないが)反復の度に同じ探索をやり直すので非効率では?
    • 局面数が多いので,いかに探索数を減らす or 多種の探索を行うかが至上命題。
    • 直前反復での閾値の際の局面を保存しておいて,次の反復はそこから始めれば速いかも?
      => これって A* そのものと変わらない気が・・・
    • 反復深化は,BFS,A*ではキューに溜めている局面情報を毎回探索基点からの探索を繰り返すことでオンデマンドに求めているものと考えればよいらしい。
    • 探索空間が大きい場合にはあまり実用的ではないような気がするので,今回の問題への適用はパスする。
  • とはいっても,単純にA*を用いてはメモリが足りなくなるのは明らか。
  • A*において評価値が悪い局面は,後で評価される(プライオリティキューの上位に浮上する)可能性が低いように思う。
  • スライドパズルはどちらかといえばグリーディな感じで手順が決まりそうで,一旦極端に評価値の悪い局面を経由しての最短手順はあり得そうにない。
  • プライオリティキューに最大サイズを設け,溢れた局面(悪い局面)は捨て去ることとする。
  • 忘却型プライオリティキューは set (STL)で簡単に実装できる。(処理効率には目を瞑る)
  • MDでは,壁に囲まれる部位で不利な方にタイルを動かしても評価値が向上してしまう。
    => 各点間の最短パスを事前に計算しておいて,その距離を評価値として用いることとする。
  • 他に評価値はないか? => 実際にスライドパズルで遊ぶ。
  • 自分が置かれる行,列で他のコマと順序が入れ替わっているケースは余計に手数がかかる。例えば,「12435」のようなケース。
    => このときは評価値+2としよう。
  • ヒューリスティック関数が「h* < 実際の残り手数」であれば,最短性が保障される。しかしながら,可能性のある盤面を丁寧に探しに行ってしまうので,探索時間が多くかかる。逆に「h*>実際の残り手数」であれば,最短性を犠牲にして評価値の良い局面をグリーディ的に探しに行くので早く解を見つけられる。
    => 探索時間のかかる問題は評価関数の係数を増やして求めていくこととしよう。
  • ゴール状態から逆向きに探索した状態を列挙しておいて,それらをゴールとすると効率が良さそう。
  • ゴールまで16手程度であれば,メモリ上に局面状態を展開できる。
  • これで,4750問程度
  • 現状,局面の探索では1手前の局面へ戻ることだけを抑止している。解けてない問題は,どこかでループが発生しているのかもしれない。
    => 探索先の局面でプライオリティキューにある局面へは(再)訪問しないようにしてみる。
        (キューには2百万局面保存)
  • これで,4830問
  • 解けない問題をトレース出力。壁が通路となっている問題が解けていないようだ。
  • 通路の場合,そこに入るタイルを連ねて移動させなければならない。
  • 評価関数に,各タイルの相対距離を使ってみよう。隣合うタイルが近くにあるほど評価値がよくなる。
  • これで,4969問。ここで時間切れ。残り31問なのが悔しい。

提出版のソースは下記の通りです。

続きを読む

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