🎄teratailクリスマスプレゼントキャンペーン2024🎄』開催中!

\teratail特別グッズやAmazonギフトカード最大2,000円分が当たる!/

詳細はこちら
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

5回答

4442閲覧

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

gyro16

総合スコア89

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

1クリップ

投稿2017/06/14 02:48

編集2017/06/14 03:25

###前提・実現したいこと
ここに質問したいことを詳細に書いてください

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が出力されます。

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

エラーメッセージ

###該当のソースコード

Java

1 2import java.util.*; 3 4class field{ 5 int[] cell = new int[16]; 6 int evaluation; 7 int[] route; 8 int floor; 9 10 field(int[] cell, int hash){ 11 floor = 1; 12 route = new int[1]; 13 route[0] = hash; //route[0]初期状態のハッシュキー 14 for(int i=0;i<16;i++) this.cell[i] = cell[i]; 15 int eva = 0; 16 for(int i=0;i<16;i++){ 17 if(cell[i] != 0){ 18 //横方向の距離を加算 19 //i:着目しているセル 20 //cell[i]:着目している数字 21 eva += Math.abs((cell[i]-1)%4 - i%4); 22 //縦方向の距離を加算 23 eva += Math.abs((cell[i]-1)/4 - i/4); 24 } 25 } 26 evaluation = eva; 27 } 28 29 30 field(int[] cell, int[] route, int hash){ 31 this.floor = route.length; 32 this.route = new int[floor+1]; 33 System.arraycopy(route, 0, this.route, 0, floor); 34 this.route[floor] = hash; //hashを格納する 35 for(int i=0;i<16;i++) this.cell[i] = cell[i]; 36 int eva = 0; 37 for(int i=0;i<16;i++){ 38 if(cell[i] != 0){ 39 //横方向の距離を加算 40 //i:着目しているセル 41 //cell[i]:着目している数字 42 eva += Math.abs((cell[i]-1)%4 - i%4); 43 //縦方向の距離を加算 44 eva += Math.abs((cell[i]-1)/4 - i/4); 45 } 46 } 47 evaluation = eva; //推定コスト 48 } 49 50 public String toString(){ 51 return new String(cell[0] + " " + cell[1] + " " + cell[2] + " " + cell[3] + "\n" + 52 cell[4] + " " + cell[5] + " " + cell[6] + " " + cell[7] + "\n" + 53 cell[8] + " " + cell[9] + " " + cell[10] + " " + cell[11] + "\n" + 54 cell[12] + " " + cell[13] + " " + cell[14] + " " + cell[15] + "\n"); 55 } 56} 57 58 59 60class ev_list{ 61 field elem; 62 ev_list next; 63 64 ev_list(){ 65 next = null; 66 this.elem = null; 67 } 68 69 ev_list(field elem){ 70 next = null; 71 this.elem = elem; 72 } 73 74 public void insert(ev_list node){ 75 //ヒューリスティック関数の値が次のノードの値より大きい、 76 //または次のノードが先端のとき挿入 77 if(this.next == null || this.next.elem.evaluation + this.next.elem.floor < node.elem.evaluation + node.elem.floor){ 78 //次のノードよりヒューリスティック関数の値が小さい時 79 //this, this.nextにnodeを挿入し、this, node, node.next(this.next)にする 80 node.next = this.next; 81 this.next = node; 82 }else this.next.insert(node); 83 //次のノードの値が等しいか大きい時、次のノードにnodeを挿入する 84 } 85 86 public field pop(){ 87 if(this.next == null) return null; 88 if(this.next.next == null){ //次の次がnullなら 89 field temp = this.next.elem; //この次のフィールドをtempへ 90 this.next = null; //この次はnullにする 91 return temp; //この次だったフィールドのtempを返す 92 }else return this.next.pop(); //次の次がnullでなかったら、次をpopする 93 //最先の要素を引き出す 94 } 95} 96 97 98 99public class Algo47{ 100 static final int LEFT = 0; 101 static final int RIGHT = 1; 102 static final int UP = 2; 103 static final int DOWN = 3; 104 static final int[] factor = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8172, 16344, 32688}; //1から始まり、前の要素を2倍する 105 106 //ハッシュキー生成関数 107 static public int hashkey(int[] cell){ 108 int[] val = new int[16]; 109 System.arraycopy(cell, 0, val, 0, 16); 110 for(int i=0;i<16;i++){ 111 for(int j=i+1;j<16;j++){ 112 if(val[j] > val[i]) val[j]--; 113 } 114 } 115 //valは、0も多いがまちまちの値が出力される、ハッシュに関わる数 116 int hash = 0; 117 for(int i=0;i<16;i++){ 118 hash += val[i] * factor[15-i]; //factorから大きな数字から取り出され掛け合わされる 119 } 120 return hash; 121 } 122 123 124 125 static public field dehash(int key){ 126 int[] cell = new int[16]; 127 for(int i=0;i<16;i++){ 128 cell[i] = key/factor[15-i]; //factorから大きな数字から割っていく、cellはvalと同じ 129 key %= factor[15-i]; //factorの除算の余りをkeyへ 130 } 131 for(int i=15;i>=0;i--){ 132 for(int j=i+1;j<16;j++){ 133 if(cell[i] <= cell[j]) cell[j]++; 134 } 135 } 136 //hashしたkeyを与えると、(valをcellに戻す)、初期値であるcellが得られるdehashである 137 return new field(cell, key); 138 } 139 140 141 142 //4*4のフィールドの、移動できる範囲 143 //move[i][LEFT]:左に動けるか(0,1) 144 //move[i][RIGHT]:右に動けるか(0,1) 145 //move[i][UP]:上に動けるか(0,1) 146 //move[i][DOWN]:下に動けるか(0,1) 147 static boolean[][] move = new boolean[16][4]; 148 149 public static void main(String[] args){ 150 151 //移動可能方向の設定部分 152 153 //移動できる方向に各セルに対して設定する 154 //右に動けるかどうかを指定 155 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; 156 move[3][RIGHT]=move[7][RIGHT]=move[11][RIGHT]=move[15][RIGHT]=false; 157 158 159 //左に動けるかどうかを指定 160 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; 161 move[0][LEFT]=move[4][LEFT]=move[8][LEFT]=move[12][LEFT]=false; 162 163 //上に動けるかどうかを指定 164 move[0][UP]=move[1][UP]=move[2][UP]=move[3][UP]=false; 165 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; 166 167 //下に動けるかどうかを指定 168 move[12][DOWN]=move[13][DOWN]=move[14][DOWN]=move[15][DOWN]=false; 169 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; 170 171 172 //初期配置の設定部分 173 //初期配置 174 field st; 175 int[] cell = new int[16]; 176 177 Scanner scan = new Scanner(System.in).useDelimiter("[\\s]+"); 178 for(int i=0;i<4;i++) 179 for(int j=0;j<4;j++) 180 cell[4*i+j] = scan.nextInt(); 181 //for文で繰り返しでcell入力 182 183 st = new field(cell, hashkey(cell)); //推定距離(推定コスト)とハッシュキーをフィールドに持たせる 184 185 //ハッシュテーブル 186 boolean[] visited = new boolean[990000]; 187 for(int i=0;i<362880;i++) 188 visited[i] = false; 189 //visited[i]を未訪問にする 190 191 //探索部分 192 193 //ソートリストを設定 194 ev_list list = new ev_list(); 195 list.insert(new ev_list(st)); //リストにフィールドを挿入する 196 visited[hashkey(cell)] = true; //ハッシュキーのテーブルをtrueにする 197 198 field cur; 199 int hash; 200 int count=0; 201 while( (cur=list.pop() )!= null){ 202 count++; //探索回数を1増やす 203 204 205 for(int i=0;i<16;i++){ 206 if(cur.cell[i]==0){ //curはカレントフィールド、cell[i]が0の時 207 if(move[i][LEFT]){ //左に動けるなら、左と交換 208 cur.cell[i]=cur.cell[i-1]; 209 cur.cell[i-1]=0; 210 hash=hashkey(cur.cell); //hashkeyを生成 211 if(!visited[hash]){ //hashkeyを訪れていないなら 212 visited[hash]=true; 213 list.insert(new ev_list(new field(cur.cell, cur.route, hash) )); 214 } 215 cur.cell[i-1]=cur.cell[i]; //元に戻す 216 cur.cell[i]=0; 217 } 218 219 if(move[i][RIGHT]){ 220 cur.cell[i]=cur.cell[i+1]; 221 cur.cell[i+1]=0; 222 hash=hashkey(cur.cell); 223 if(!visited[hash]){ 224 visited[hash]=true; 225 list.insert(new ev_list(new field(cur.cell, cur.route, hash) )); 226 } 227 cur.cell[i+1]=cur.cell[i]; 228 cur.cell[i]=0; 229 } 230 231 if(move[i][UP]){ 232 cur.cell[i]=cur.cell[i-4]; 233 cur.cell[i-4]=0; 234 hash=hashkey(cur.cell); 235 if(!visited[hash]){ 236 visited[hash]=true; 237 list.insert(new ev_list(new field(cur.cell, cur.route, hash) )); 238 } 239 cur.cell[i-4]=cur.cell[i]; 240 cur.cell[i]=0; 241 } 242 243 if(move[i][DOWN]){ 244 cur.cell[i]=cur.cell[i+4]; 245 cur.cell[i+4]=0; 246 hash=hashkey(cur.cell); 247 if(!visited[hash]){ 248 visited[hash]=true; 249 list.insert(new ev_list(new field(cur.cell, cur.route, hash) )); 250 } 251 cur.cell[i+4]=cur.cell[i]; 252 cur.cell[i]=0; 253 } 254 } 255 } 256 257 if(cur.evaluation==0){ //推定コストが0になった時 258 System.out.println(cur.route.length-1); //cur.routeの長さ-1を出力する 259 //System.out.println(count+""); 260 //System.out.println("evaluation[ " +0+ " ]=" + dehash(cur.route[0]).evaluation + "\n" + dehash(cur.route[0]) ); 261 //evaluation推定コスト、cur.route[0]初期ハッシュキーのtoString() 262 //for(int i=1;i<cur.route.length;i++){ 263 //System.out.println("↓"); 264 //System.out.println("evaluation[ " +i+ " ]=" + dehash(cur.route[i]).evaluation); 265 //System.out.println("evaluation + floor[ " +i+ " ]=" + (dehash(cur.route[i]).evaluation + i) ); 266 //evaluation推定コスト、floor移動距離 267 //System.out.println( dehash(cur.route[i]).toString() ); 268 //} 269 break; 270 } 271 } 272 } 273}

###試したこと

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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

ベストアンサー

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 04:40

szk.

総合スコア1400

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

gyro16

2017/06/14 04:45

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

0

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

投稿2017/06/14 05:01

Bongo

総合スコア10811

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

投稿2017/06/14 04:14

torisan

総合スコア678

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

投稿2017/06/14 05:02

tacsheaven

総合スコア13703

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

の28手詰めの15パズルを与えると、ArrayIndexOfBoundsExceptionが発生したので、

ハッシュテーブルを
boolean[] visited = new boolean[990000];
にして解消しますと、無応答になります。
解消できませんか?

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

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


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

投稿2017/06/14 03:46

KSwordOfHaste

総合スコア18400

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.36%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問