ページ

2011年9月14日水曜日

GDD2011 DevQuiz スライドパズル

以下のサイトを見ると、皆さんいろいろなアルゴリズムで探索しているようです。

「GDD2011 DevQuiz のスライドパズル晒し祭りをまとめてみた」
http://d.hatena.ne.jp/harapon1012/touch/20110912/1315805381

言語はjavaが多いようですが、中にはJavaScriptで4000問以上正解したという人もいたようです。

私もJava(Swing)で作成しました。幅優先探索とステップ実行を並列処理で行うようにしました。
枝刈りには、MD(移動距離)及びID(転倒距離)の厳しい方を採用。ここで壁を考慮した枝刈りをすればもっと効率の良い探索が出来たんだろうなぁと思います。


■ 探索アルゴリズムの纏め

1.深さ優先探索(DFS)
先頭のノードから、子のない最後のノードに行き着くまで、深く伸びていく探索、その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。

2.幅優先探索(BFS)
先頭のノードで始まり隣接した全てのノードを探索する。それからこれらの最も近い子ノードのそれぞれに対して同様のことを繰り返す。

3.反復深化(IDDFS)
深さ優先探索の深さ制限を徐々に増大させ、最終的に目標状態の深さになるまで反復するもの。

4.A*探索(IDA*)
過去のステップ数と残りの距離見積りの和で与えた閾値を上げながら反復深化(これが最も有効だったようだ)

5.双方向探索
同時に2つの方向から探索を行う。一方は初期状態から順方向に探索し、もう一方は最終状態から逆方向に探索して、その中間でぶつかった時点で終了する

6.端優先
人がパズルを組み立てる時のように端から順に揃えていくアルゴリズム。

7.ステップ実行
指定された回数探索を行い、それまでにゴールに達しなかった場合、過去に見つかった残りの距離見積りが最小のものをスタートに再度探索を繰り返す。(それ以外のノードを捨てる)
実装は簡単ですが、無駄なノードに対しても与えられた探索回数までは広く探索を行う点が難。


■ 作成したソース
https://github.com/isystk/gdd2011jp

■ デモ
http://www.ise-web.com/sample/jws/

■ 結果


■ 参考にしたサイト
http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

0 件のコメント:

コメントを投稿