スライドパズルに関するアルゴリズムのサマリー
ソースさらし祭り(?)に参加されている人の解説などを含め今回調べたアルゴリズムを整理したページです。広く浅く、全体を俯瞰できるようにすることを目標に書いてみます。
☆問題の定式化
駒数をKとすると可能な盤面はK！個あり、それらを要素とする集合Sを考える。
Sの各要素は駒を一回移動することで遷移できる要素と繋がっていると考えることで無向グラフとみなすことができる。
与えられた問題面ノードからゴールノードまでの経路探索問題と解釈できる。
なお、Kが３６の場合K!は３．７×１０^３６となり、無限の要素を持つと思って考えていい。
今後、n,g,h,h'を以下の意味で使う。
n：与えられた盤面
g(n)：スタートの盤面からnまでの駒の移動回数
h(n)：nからゴールまでの最短経路の駒の移動回数
h'(n)：h(n)の推定値。（マンハッタンディスタンスなどを利用したnからゴールまでの駒の移動回数の推定値）
☆経路探索アルゴリズム：幅探優先探索
駒の移動回数の小さい順に探索していくアルゴリズム。
見つかったノードをキューに入れていく形で実装。
過去の盤面をメモリーに保存するため、メモリーサイズで探索できるノード数が限られる。
http://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
☆経路探索アルゴリズム：深さ優先探索
ノードが途切れるか、ゴールに到達するまで深く探索していき、その後はバックトラック。
スライドパズルのような開いた木の最適解を求めるためには下記のIDDFSやIDA*のような手法を使う。
過去の盤面を保存しないのでメモリー消費は小さい。
http://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
☆経路探索アルゴリズム：IDA*
深さ優先探索で以下の閾値を設けて探索を行う。
g(n) + h'(n) <Threshold
ある閾値でゴールが見つからなかった場合は、閾値を徐々に増大させながら探索を繰り返す。
ここでh'(n)が以下を満たす時、最初に見つけた経路が最短経路である事が証明できる。
0 ≦ h'(n) ≦ h(n)
この閾値の評価を単に
g(n) < Threshold
としたものは反復深化深さ優先探索(IDDFS)と呼ばれる。
木構造の根元に近い部分を何度も調べることになるため無駄のように見えるが、ノードの多くは木構造の底辺にあるため、それほどコスト増大にはならない。（深さNに応じてx＾Nでノード数は増大するため、たとえばx=2の場合、高々2倍の演算量にしかならない）
http://ja.wikipedia.org/wiki/%E5%8F%8D%E5%BE%A9%E6%B7%B1%E5%8C%96%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
☆経路探索アルゴリズム：A*
幅優先のキューをプライオリティキューにして、もっとも推定コストの小さいノードを優先して探索しているアルゴリズム。
推定コストとは
f(n) = g(n) + h'(n)
ここでIDA*同様h'(n)が以下を満たす時、最初に見つけた経路が最短経路である事が証明できる。
0 ≦ h'(n) ≦ h(n)
幅優先探索の拡張であるのでメモリが探索深度に応じ指数関数的に消費されていくため、ある程度以上の深度まで探索しようとすると、使われないノードを一旦破棄し必要に応じて再利用（SMA*）が必要になる。
http://ja.wikipedia.org/wiki/A*
☆評価関数h'(n)
高得点を得ていたアルゴリズムはほぼA*かIDA*を利用したものだったが、これらのアルゴリズムでは評価関数h'(n)の精度が重要になる。
h'(n)がh(n)に近ければ近いほど演算量は小さくなるので、いかにh(n)に近い関数を見つけるかがとても重要！
以下で説明するようにいくつかの手法が考案されており、これらを組み合わせて使う（もっとも値の大きいh'(n)の値を利用する）こともできる。
☆マンハッタンディスタンス（MD)
個々の駒に関してゴール位置への移動回数を計算したもの。http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%8F%E3%83%83%E3%82%BF%E3%83%B3%E8%B7%9D%E9%9B%A2
パターンデータベース（PDB）
前もって特定のパターンとそのパターンのh(n)を計算しておき、それをハッシュ化して保存しておきh'(n)の計算に利用する手法。http://www.ise.bgu.ac.il/faculty/felner/research/jairpdb.pdf
☆ギャップ集合
MDを利用したh'(n)とh(n)とのギャップがいくつであるかに応じたデータベースをあらかじめ作っておく。探索時にそのDBを参照し、ギャップに応じてMDに値を加算する。
http://www.jstage.jst.go.jp/article/tjsai/26/2/419/_pdf/-char/ja/
☆転倒距離
駒の並びを順列と考え、小さい順に並んでいない駒の数（転倒が起こっている回数）を利用http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html
☆ウォーキングディスタンス
ゴール盤面で各行（または各列）に属している駒が、その盤面でそれぞれの各行（または各列）に何個あるかというパターンをデータベース化したもの。PDBの一種（？）
４×４くらいまでは有効だが、５×５以上ではデータベースが膨大になり現実的ではない。
http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html
☆最短経路以外の解を求める探索
ここまでは全て最短経路を求めるためのアルゴリズムだが、今回のDevquizの問題は与えられた移動可能駒数に余裕があり、参加者の多くは非最短解を求めるアルゴリズムを考案・採用されていた。
大別すると以下のパターンに分類できる。
☆上限を守らない評価関数
上に述べたように任意の盤面nに対し
0 ≦ h'(n) ≦ h(n)
を満たすような評価関数であれば、最短経路である事が保障されますが、この上限をあえて守らない事でより早くゴールにたどり着こうという発想。
具体的には、MD値を各コマに対して足し上げる際に端の駒の重みを大きくしたり、駒の並び順に応じてペナルティスコアを加算したり等。
☆段階を置いてゴールに辿りつこうという方法
いきなりゴール面までの探索をする代わりに、途中に中継点を置いて中継点までの探索を行い、中継点からゴールまでの探索を再度行う方法。
私が行った、端優先、ステップ実行はこれにあたる。
（ 端優先、ステップ実行という名前は私が勝手に付けた）
☆キューのサイズに上限を設ける方法
A*など幅優先系のアルゴリズムでプライオリティキューのサイズに上限を設け、上限に達したらプライオリティのもっとも低いノードをキューから削除する方法。
☆経路探索アルゴリズム：双方向探索
逆方向からも探索する事で演算量を下げる方法。
やり方によっては最適解にもなる。
x^Nがx^(N/2)となり、大幅に演算量を下げることができる。
http://ja.wikipedia.org/wiki/%E5%8F%8C%E6%96%B9%E5%90%91%E6%8E%A2%E7%B4%A2
0 件のコメント:
コメントを投稿