アルゴリズムについて

質問

このサイトのアルゴリズムをどなたか教えていただけないでしょうか？
http://oraclesqlpuzzle.hp.infoseek.co.jp/java/java-3-6.html

お願いしますm(_ _)m

回答No.1

mtaka2

典型的な「深さ優先探索」アルゴリズムです。

初期状態の盤面から、「取り得る操作全てを試してみて、その結果盤面」を作り出します。空きマスが中央にあるなら、上下左右の4パターンですね。
さらに、生成した盤面から、さらにその次の「取り得る操作全てを試してみて、その結果盤面」を作り出します。
そうやって、取り得る操作パターンを全て順番に試してみて、その結果盤面が完成状態かチェックしているのです。

> while (st.isEmpty() == false){
> StackDataDef priInfo = st.pop();
ここで、「試すべき盤面データ」が空でない間はループします。
そして、盤面データを一つ取ってきます。

> boolean isOK = true;
(略)
> if (maxLevel > priInfo.Level) maxLevel = priInfo.Level; //高さ制限値を更新
> }
この部分は、完成形かどうかのチェックと結果経路の表示です。
で、次の行の
> if (priInfo.Level >=maxLevel) continue; //高さ制限
この、今までに見つけた操作手順数の最短値を覚えておいて、それより長い経路は辿らないようにするものです。

次に
> X=Y=0;
> while(priInfo.ValList[X][Y] !=0){
> if (++Y == 4){
> X++;Y=0;
> }
> }
これで、空きマスを探しています。
ここまでが、1ループ中の下準備です。
次に、4方向の各操作に対応する盤面を作り出します。
ただし、毎回4パターンすべてを試すわけではありません。
空きマスが左端にあったり、直前に左移動をした場合には、右移動は無し、など。
> //左の数字を移動
> if (X!=0 && !priInfo.priMove.equals("←")){
これがその判断部です。X(マスの横方向位置)が0(左端)でない、かつ、直前の移動操作が左移動でない場合に、右移動盤面を作り出します。

右移動盤面は、空きマスとその左のマスの数字を入れ替えで作ります。それが
> priInfo.ValList[X-1][Y] = 0;
> priInfo.ValList[X][Y] = saveVal;
この部分。
そして、
> st.push(priInfo,"→");
ここで、生成した盤面と行った操作を追加し、
> willPush.ValList[X-1][Y] = saveVal;
> willPush.ValList[X][Y] = 0;
これで、盤面を操作前に戻します。
1ループ内で、こういった操作を4方向分行います。
以上の繰り返し。

ただし、このプログラムはあまり出来が良いものではないですね。

このループ内にある処理とまったく同じものが、
ループの直前にもあります。これは無駄です。
> void main() {
> StackClass st = new StackClass();
> StackDataDef willPush = new StackDataDef();
> st.push(willPush,"");
> int ansCnt=0;
> while (st.isEmpty() == false){
といった感じで初期盤面をstに入れるようにすれば、この部分は要りません。

また、スタックを使った深さ優先探索なのも、ダメダメです。
この手の探索問題は、大抵「最短手」を見つけるのが目的ですが、
深さ優先探索では、とりあえず操作をどんどん進めていくので、
最悪の場合、答えが見つからないまま永遠に操作を進めることになったりします。
(このプログラムの場合は、30手で打ち止めにしていますが、そうなると最短手が30手以上の場合、解を見つけられません)

こういうパズルを解くときはスタックではなく「キュー」を使った「幅優先探索」を使うのが基本です。
幅優先探索では、「1手で作れる盤面を全部作り出す」→「2手で作れる盤面を全部作り出す」→「3手で作れる盤面を全部作り出す」…
と手順を増やすので、必ず最初に最短手が見つかります。

それと、直前の操作しか覚えていないので、「上左下右」といったぐるっと回って元に戻る無駄な操作が発生します。(実行例の解1にも、そういう操作が入ってますね。)
直前の操作だけでなく、今までに生成した盤面すべてをチェックして、同じ盤面に戻るような操作は試さないようにすべきです。

お礼

とても分かりやすい解説、どうもありがとうございますm(_ _)m
非常に参考になりました！！！