質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.58%

15パズルをA*アルゴリズムで解きたいが、あるケースで無応答になる

解決済

回答 5

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 2,703

score 85

前提・実現したいこと

ここに質問したいことを詳細に書いてください

8パズルのAスターアルゴリズムを15パズルにして解いています。
短い手数の15パズルは解けるのですが、

1 3 4 8
2 6 14 7
0 9 12 15
5 11 13 10

の28手詰めの15パズルを与えると、ArrayIndexOfBoundsExceptionが発生したので、
ハッシュテーブルを
boolean[] visited = new boolean[990000];
にして解消しますと、無応答になります。無応答と言うかWhile文で探索中のままになっている?!

8パズルはこのA*アルゴリズムで解けています。15パズルにして応用して解こうとしています。
解決できませんか?

ちなみに、
1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15

の入力は8手詰めで、8が出力されます。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

import java.util.*;

class field{
    int[] cell = new int[16];
    int evaluation;
    int[] route;
    int floor;

    field(int[] cell, int hash){
        floor = 1;
        route = new int[1];
        route[0] = hash; //route[0]初期状態のハッシュキー
        for(int i=0;i<16;i++) this.cell[i] = cell[i];
        int eva = 0;
        for(int i=0;i<16;i++){
            if(cell[i] != 0){
                //横方向の距離を加算
                //i:着目しているセル
                //cell[i]:着目している数字
                eva += Math.abs((cell[i]-1)%4 - i%4);
                //縦方向の距離を加算
                eva += Math.abs((cell[i]-1)/4 - i/4);
            }
        }
        evaluation = eva;
    }


    field(int[] cell, int[] route, int hash){
        this.floor = route.length;
        this.route = new int[floor+1];
        System.arraycopy(route, 0, this.route, 0, floor);
        this.route[floor] = hash; //hashを格納する
        for(int i=0;i<16;i++) this.cell[i] = cell[i];
        int eva = 0;
        for(int i=0;i<16;i++){
            if(cell[i] != 0){
                //横方向の距離を加算
                //i:着目しているセル
                //cell[i]:着目している数字
                eva += Math.abs((cell[i]-1)%4 - i%4);
                //縦方向の距離を加算
                eva += Math.abs((cell[i]-1)/4 - i/4);
            }
        }
        evaluation = eva; //推定コスト
    }

    public String toString(){
        return new String(cell[0] + " " + cell[1] + " " + cell[2] + " " + cell[3] + "\n" +
             cell[4] + " " + cell[5] + " " + cell[6] + " " + cell[7] + "\n" +
             cell[8] + " " + cell[9] + " " + cell[10] + " " + cell[11] + "\n" +
             cell[12] + " " + cell[13] + " " + cell[14] + " " + cell[15] + "\n");
    }
}



class ev_list{
    field elem;
    ev_list next;

    ev_list(){
        next = null;
        this.elem = null;
    }

    ev_list(field elem){
        next = null;
        this.elem = elem;
    }

    public void insert(ev_list node){
        //ヒューリスティック関数の値が次のノードの値より大きい、
        //または次のノードが先端のとき挿入
        if(this.next == null || this.next.elem.evaluation + this.next.elem.floor < node.elem.evaluation + node.elem.floor){
            //次のノードよりヒューリスティック関数の値が小さい時
            //this, this.nextにnodeを挿入し、this, node, node.next(this.next)にする
            node.next = this.next;
            this.next = node;
        }else this.next.insert(node);
        //次のノードの値が等しいか大きい時、次のノードにnodeを挿入する
    }

    public field pop(){
        if(this.next == null) return null;
        if(this.next.next == null){ //次の次がnullなら
            field temp = this.next.elem; //この次のフィールドをtempへ
            this.next = null; //この次はnullにする
            return temp; //この次だったフィールドのtempを返す
        }else return this.next.pop(); //次の次がnullでなかったら、次をpopする
        //最先の要素を引き出す
    }
}



public class Algo47{
    static final int LEFT = 0;
    static final int RIGHT = 1;
    static final int UP = 2;
    static final int DOWN = 3;
    static final int[] factor = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8172, 16344, 32688}; //1から始まり、前の要素を2倍する

    //ハッシュキー生成関数
    static public int hashkey(int[] cell){
        int[] val = new int[16];
        System.arraycopy(cell, 0, val, 0, 16);
        for(int i=0;i<16;i++){
            for(int j=i+1;j<16;j++){
                if(val[j] > val[i]) val[j]--;
            }
        }
        //valは、0も多いがまちまちの値が出力される、ハッシュに関わる数
        int hash = 0;
        for(int i=0;i<16;i++){
            hash += val[i] * factor[15-i]; //factorから大きな数字から取り出され掛け合わされる
        }
        return hash;
    }



    static public field dehash(int key){
        int[] cell = new int[16];
        for(int i=0;i<16;i++){
            cell[i] = key/factor[15-i]; //factorから大きな数字から割っていく、cellはvalと同じ
            key %= factor[15-i]; //factorの除算の余りをkeyへ
        }
        for(int i=15;i>=0;i--){
            for(int j=i+1;j<16;j++){
                if(cell[i] <= cell[j]) cell[j]++;
            }
        }
        //hashしたkeyを与えると、(valをcellに戻す)、初期値であるcellが得られるdehashである
        return new field(cell, key);
    }



    //4*4のフィールドの、移動できる範囲
    //move[i][LEFT]:左に動けるか(0,1)
    //move[i][RIGHT]:右に動けるか(0,1)
    //move[i][UP]:上に動けるか(0,1)
    //move[i][DOWN]:下に動けるか(0,1)
    static boolean[][] move = new boolean[16][4];

    public static void main(String[] args){

        //移動可能方向の設定部分

        //移動できる方向に各セルに対して設定する
        //右に動けるかどうかを指定
        move[0][RIGHT]=move[1][RIGHT]=move[2][RIGHT]=move[4][RIGHT]=move[5][RIGHT]=move[6][RIGHT]=move[8][RIGHT]=move[9][RIGHT]=move[10][RIGHT]=move[12][RIGHT]=move[13][RIGHT]=move[14][RIGHT]=true;
        move[3][RIGHT]=move[7][RIGHT]=move[11][RIGHT]=move[15][RIGHT]=false;


        //左に動けるかどうかを指定
        move[1][LEFT]=move[2][LEFT]=move[3][LEFT]=move[5][LEFT]=move[6][LEFT]=move[7][LEFT]=move[9][LEFT]=move[10][LEFT]=move[11][LEFT]=move[13][LEFT]=move[14][LEFT]=move[15][LEFT]=true;
        move[0][LEFT]=move[4][LEFT]=move[8][LEFT]=move[12][LEFT]=false;

        //上に動けるかどうかを指定
        move[0][UP]=move[1][UP]=move[2][UP]=move[3][UP]=false;
        move[4][UP]=move[5][UP]=move[6][UP]=move[7][UP]=move[8][UP]=move[9][UP]=move[10][UP]=move[11][UP]=move[12][UP]=move[13][UP]=move[14][UP]=move[15][UP]=true;

        //下に動けるかどうかを指定
        move[12][DOWN]=move[13][DOWN]=move[14][DOWN]=move[15][DOWN]=false;
        move[0][DOWN]=move[1][DOWN]=move[2][DOWN]=move[3][DOWN]=move[4][DOWN]=move[5][DOWN]=move[6][DOWN]=move[7][DOWN]=move[8][DOWN]=move[9][DOWN]=move[10][DOWN]=move[11][DOWN]=true;


        //初期配置の設定部分
        //初期配置
        field st;
        int[] cell = new int[16];

        Scanner scan = new Scanner(System.in).useDelimiter("[\\s]+");
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                cell[4*i+j] = scan.nextInt();
        //for文で繰り返しでcell入力

        st = new field(cell, hashkey(cell)); //推定距離(推定コスト)とハッシュキーをフィールドに持たせる

        //ハッシュテーブル
        boolean[] visited = new boolean[990000];
        for(int i=0;i<362880;i++)
            visited[i] = false;
        //visited[i]を未訪問にする

        //探索部分

        //ソートリストを設定
        ev_list list = new ev_list();
        list.insert(new ev_list(st)); //リストにフィールドを挿入する
        visited[hashkey(cell)] = true; //ハッシュキーのテーブルをtrueにする

        field cur;
        int hash;
        int count=0;
        while( (cur=list.pop() )!= null){
            count++; //探索回数を1増やす


            for(int i=0;i<16;i++){
                if(cur.cell[i]==0){ //curはカレントフィールド、cell[i]が0の時
                    if(move[i][LEFT]){ //左に動けるなら、左と交換
                        cur.cell[i]=cur.cell[i-1];
                        cur.cell[i-1]=0;
                        hash=hashkey(cur.cell); //hashkeyを生成
                        if(!visited[hash]){ //hashkeyを訪れていないなら
                            visited[hash]=true;
                            list.insert(new ev_list(new field(cur.cell, cur.route, hash) ));
                        }
                        cur.cell[i-1]=cur.cell[i]; //元に戻す
                        cur.cell[i]=0;
                    }

                    if(move[i][RIGHT]){
                        cur.cell[i]=cur.cell[i+1];
                        cur.cell[i+1]=0;
                        hash=hashkey(cur.cell);
                        if(!visited[hash]){
                            visited[hash]=true;
                            list.insert(new ev_list(new field(cur.cell, cur.route, hash) ));
                        }
                        cur.cell[i+1]=cur.cell[i];
                        cur.cell[i]=0;
                    }

                    if(move[i][UP]){
                        cur.cell[i]=cur.cell[i-4];
                        cur.cell[i-4]=0;
                        hash=hashkey(cur.cell);
                        if(!visited[hash]){
                            visited[hash]=true;
                            list.insert(new ev_list(new field(cur.cell, cur.route, hash) ));
                        }
                        cur.cell[i-4]=cur.cell[i];
                        cur.cell[i]=0;
                    }

                    if(move[i][DOWN]){
                        cur.cell[i]=cur.cell[i+4];
                        cur.cell[i+4]=0;
                        hash=hashkey(cur.cell);
                        if(!visited[hash]){
                            visited[hash]=true;
                            list.insert(new ev_list(new field(cur.cell, cur.route, hash) ));
                        }
                        cur.cell[i+4]=cur.cell[i];
                        cur.cell[i]=0;
                    }
                }
            }

            if(cur.evaluation==0){ //推定コストが0になった時
                System.out.println(cur.route.length-1); //cur.routeの長さ-1を出力する
                //System.out.println(count+"");
                //System.out.println("evaluation[ " +0+ " ]=" + dehash(cur.route[0]).evaluation + "\n" + dehash(cur.route[0]) );
                //evaluation推定コスト、cur.route[0]初期ハッシュキーのtoString()
                //for(int i=1;i<cur.route.length;i++){
                    //System.out.println("↓");
                    //System.out.println("evaluation[ " +i+ " ]=" + dehash(cur.route[i]).evaluation);
                    //System.out.println("evaluation + floor[ " +i+ " ]=" + (dehash(cur.route[i]).evaluation + i) );
                    //evaluation推定コスト、floor移動距離
                    //System.out.println( dehash(cur.route[i]).toString() );
                //}
                break;
            }
        }
    }
}

試したこと

補足情報(言語/FW/ツール等のバージョンなど)

より詳細な情報

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

checkベストアンサー

+1

A*アルゴリズムでは、このようなパズルは解けません。

wikipediaによるとA*アルゴリズムは、

グラフ上でスタートからゴールまでの道を見つける

ということなので、0が2回同じフィールドを通ることを想定していません。
実装でいうとvisited[hash]がそれにあたるかと思います。

おそらくですが、
以下の5手詰めですら結果が出ません。
1 2 3 4
5 6 8 11
9 10 7 0
13 14 15 12

あと、「無応答」ではなく、
「何も表示されずに終了する」だと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/06/14 13:45

    そういうこともあるんですね。
    A*アルゴリズムは直線的なんですね。
    解説ありがとうございました。

    キャンセル

+1

今回の件とは関係ないかもしれませんが念のため。

15パズルには絶対に解くことが出来ない配置が存在します。
解く事が出来ない⇒無限ループ、となっている可能性があります。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

すいません、私もコードをよく追っていないのでピント外れかもしれませんが、コード自体は8パズル版を単純に15パズル版に拡張したのですよね?そしてA*法で解く...というのは各盤面の状態をノードとみなし、初期状態から完成状態への経路を探索するアプローチでしょうか。となると、ノードの数が階乗のオーダーで増加し、まともに解けなくなる可能性はないでしょうか。アプローチの見直しが必要かもしれません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

の28手詰めの15パズルを与えると、ArrayIndexOfBoundsExceptionが発生したので、
ハッシュテーブルを
boolean[] visited = new boolean[990000];
にして解消しますと、無応答になります。
解消できませんか?

プログラムが動かないととき、その原因を把握せずにあてずっぽうで手を加えて動かそうとしているような印象を持ちます。もしそうならそれは正しい対処とは言えないと思います。

まずはArrayIndexOfBoundsExceptionがどこで何故発生したのかを調べ、その原因を把握した上で対処を考えるのが自然な問題解消法だと思います。


「無応答」になる原因はおそらく無限ループなのではないかと思えますがコードを見てませんのでわかりません・・・余計なお世話ではありますが、自分は質問者さんご自身でなんらかのデバッグをした結果が明記されていない場合、代わりにデバッグする気にはなかなかなれません。もしデバッグされているのでしたらその結果を書かないのは不合理ですよ?それが書かれていさえすれば、回答者にとっても原因がつかみやすくなり、それだけ原因のヒントが得られる可能性が上がるのですから。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

Google 先生に尋ねると、確かに 15パズルを A* アルゴリズムで解くというサイトがヒットしますね。
それを参考にされたのでしょうか。
ちらりと見たところでは、手数が多くなるほどに盤面パターンが爆発するので、メモリ不足に陥るようですが。

ちなみに15パズルの場合、あらゆる可能な盤面には1枚ずつ動かしたとしても最短で80手まででたどり着くことが証明されています(複数枚を一度に動かしてよいなら43手まで)。
※つまりどれだけ複雑な盤面であっても、最適手を取れば80手までで正しく戻せる

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.58%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る