A*アルゴリズムで８パズル解いてみた
まず、「A*アルゴリズム（A*探索アルゴリズム）」というのは、ダイクストラ法を改良したようなものです。
ダイクストラ法というのは、初期状態からノードまでの必要最小コストが小さいものから順に探索していく方法で、具体的には
(0)まず、最初にリストに初期状態を入れる
(1)リストから、「初期状態からの必要最小コスト」の値が最も小さいノードを選ぶ。
(2)そのノードから到達できる状態を調べ、リストに追加する。
(3)目的の状態に到達したら終わる。
(4)到達しなかったら(1)から繰り返し。
「必要最小コスト＝初期ノードからの移動回数」なら幅優先探索と同じになるわけです。
次に、「Aアルゴリズム」とは、ここに「たぶんあとこれぐらいで目的の状態に着く」という、
目的地までのコストの推定値を求める関数（ヒューリスティック関数）h*(x)(xはノード)を考えて、
さっきのアルゴリズムの(1)を改造して
(0)まず、最初にリストに初期状態を入れる
(1)リストから、「初期状態からの必要最小コスト＋h*(x)」の値が最も小さいノードを選ぶ。
(2)そのノードから到達できる状態を調べ、リストに追加する。
(3)目的の状態に到達したら終わる。
(4)到達しなかったら(1)から繰り返し。
つまり、h*(x)をうまく作れれば、ダイクストラ法よりもさらに速くなるというわけです。
ただし、ダイクストラ法が「初期状態からの必要最小コスト」が最小の、いわゆる最適解を確実に見つけられるのに対し、こっちは必ずしもそういうわけにはいきません。
そこで、h*(x)を、実際に目的の状態に着くまでの最短経路より小さい値を返すように作ると、このアルゴリズムでも必ず最適解を求められます。
そのときのAアルゴリズムを特に「A*アルゴリズム」と言います。
えー……
前置き終わり。
てか、まんまWikipediaパクってきたのでそっちを見て。
「A*」
http://ja.wikipedia.org/wiki/A*
このh*(x)の説明は、ほかの文献見るあたり「目的状態との差異」みたいな感じで作ればいいみたいです。
つまり、目的状態に近ければ近いほど小さい値になるようにする。
要はこのアルゴリズムは、いままで適当に全部調べてた幅優先探索やダイクストラ法を、「目的の状態に近いものから調べていく」という単純な戦略によって改良したものなわけです。
実際幅優先探索でやってる検索を見てみると、ずいぶん無駄なノードを調べてるはずです。
……まあ、あとで比較結果見せますが、かなり無駄な検索してます。
で、８パズルの適用例。
８パズルに関しては、次のページを見て。
「１５パズル」
http://ja.wikipedia.org/wiki/15%E3%83%91%E3%82%BA%E3%83%AB
この「１５パズル」の３×３バージョンが８パズル。
戦略的には、初期状態からどんどん動かしていって、目的の状態が見つかるまで繰り返す。
ただし、二度と同じ状態にならないようにハッシュテーブルを用いて到達・未到達を管理する、という感じ。
で、この動かし方が「手当たり次第」ならただの幅優先探索ですが、ここに
h*(x)=「各数字パネルの、もとの位置からの距離の和」
（距離：タテ・ヨコにそれぞれどれだけ離れているか）
というヒューリスティック関数（出典：オライリー：『アルゴリズムクイックリファレンス』）を導入して、
初期状態からの距離＋h*(x)の値を用いたA*アルゴリズムを使いました。
今の状態から数字を元の場所に戻すには、最低でも距離と同じだけその数字パネルをスライドさせなければならないので、
一回の状態移動が一回のスライドに対応している本プログラムにおいては、
h*(x)<（解状態までの実際の距離）
が成り立つため、A*アルゴリズムとなります。
で、実際のコードがこちら。
ev_listクラス:「初期状態からの距離＋h*(x)」の値でソート済みのソートリスト（優先度付きキュー:priority queue）
fieldクラス:状態を保存する為のクラス。evaluation:h*(x),floor:初期状態からの距離
import java.util.*;
import java.io.*;
class field{
int cell[ ]=new int[ 9 ];
int evaluation;
int route[ ];
int floor;
field(int cell[ ],int hash){
floor=1;
route = new int[ 1 ];
route[ 0 ] = hash;
for(int i=0;i<9;i++)this.cell[ i ]=cell[ i ];
int eva=0;
for(int i=0;i<9;i++){
if(cell[ i ]!=0){
//横方向の距離を加算
//i:着目しているセル
//cell[ i ]:着目している数字
eva+=Math.abs( (cell[ i ]-1)%3-i%3);
//縦方向の距離を加算
eva+=Math.abs( (cell[ i ]-1)/3-i/3);
}
}
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;
for(int i=0;i<9;i++)this.cell[ i ]=cell[ i ];
int eva=0;
for(int i=0;i<9;i++){
if(cell[ i ]!=0){
//横方向の距離を加算
//i:着目しているセル
//cell[ i ]:着目している数字
eva+=Math.abs( (cell[ i ]-1)%3-i%3);
//縦方向の距離を加算
eva+=Math.abs( (cell[ i ]-1)/3-i/3);
}
}
evaluation = eva;
}
public String toString(){
return new String("[ "+cell[ 0 ]+" ]"+"[ "+cell[ 1 ]+" ]"+"[ "+cell[ 2 ]+" ]\n"+"[ "+cell[ 3 ]+" ]"+"[ "+cell[ 4 ]+" ]"+"[ "+cell[ 5 ]+" ]\n"+"[ "+cell[ 6 ]+" ]"+"[ "+cell[ 7 ]+" ]"+"[ "+cell[ 8 ]+" ]");
}
}
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){
node.next = this.next;
this.next = node;
}
else this.next.insert(node);
}
public field pop(){
if(this.next==null)return null;
if(this.next.next==null){
field temp=this.next.elem;
this.next=null;
return temp;
}
else return this.next.pop();
}
}
class egt_pzl{
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,1,2,6,24,120,720,5040,40320};
//ハッシュキー生成関数
static public int hashkey(int cell[ ]){
int val[ ] = new int[ 9 ];
System.arraycopy(cell,0,val,0,9);
for(int i=0;i<9;i++){
for(int j=i+1;j<9;j++){
if(val[ j ]>val[ i ])val[ j ]--;
}
}
int hash=0;
for(int i=0;i<9;i++){
hash+=val[ i ]*factor[ 8-i ];
}
return hash;
}
static public field dehash(int key){
int cell[ ] = new int[ 9 ];
for(int i=0;i<9;i++){
cell[ i ]=key/factor[ 8-i ];
key%=factor[ 8-i ];
}
for(int i=8;i>=0;i--){
for(int j=i+1;j<9;j++){
if(cell[ i ]<=cell[ j ])cell[ j ]++;
}
}
return new field(cell,key);
}
//3*3のフィールドの、移動できる範囲
//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[ 9 ][ 4 ];
public static void main(String args[ ]){
////////移動可能方向の設定部分////////
//移動できる方向を各セルに対して設定する。
//右に動けるかどうかを指定。
move[ 0 ][ RIGHT ]=move[ 1 ][ RIGHT ]=move[ 3 ][ RIGHT ]=move[ 4 ][ RIGHT ]=move[ 6 ][ RIGHT ]=move[ 7 ][ RIGHT ]=true;
move[ 2 ][ RIGHT ]=move[ 5 ][ RIGHT ]=move[ 8 ][ RIGHT ]=false;
//左に動けるかどうかを指定。
move[ 1 ][ LEFT ]=move[ 2 ][ LEFT ]=move[ 4 ][ LEFT ]=move[ 5 ][ LEFT ]=move[ 7 ][ LEFT ]=move[ 8 ][ LEFT ]=true;
move[ 0 ][ LEFT ]=move[ 3 ][ LEFT ]=move[ 6 ][ LEFT ]=false;
//上に動けるかどうかを指定。
move[ 3 ][ UP ]=move[ 4 ][ UP ]=move[ 5 ][ UP ]=move[ 6 ][ UP ]=move[ 7 ][ UP ]=move[ 8 ][ UP ]=true;
move[ 0 ][ UP ]=move[ 1 ][ UP ]=move[ 2 ][ UP ]=false;
//下に動けるかどうかを指定。
move[ 0 ][ DOWN ]=move[ 1 ][ DOWN ]=move[ 2 ][ DOWN ]=move[ 3 ][ DOWN ]=move[ 4 ][ DOWN ]=move[ 5 ][ DOWN ]=true;
move[ 6 ][ DOWN ]=move[ 7 ][ DOWN ]=move[ 8 ][ DOWN ]=false;
////////初期配置の設定部分////////
//初期位置
field st;
int cell[ ]= new int[ 9 ];
//各セルの初期値を設定。
//めんどいのでハードコーディング。
//「0」は空セルの意味。
cell[ 0 ]=1;
cell[ 1 ]=8;
cell[ 2 ]=0;
cell[ 3 ]=4;
cell[ 4 ]=3;
cell[ 5 ]=2;
cell[ 6 ]=5;
cell[ 7 ]=7;
cell[ 8 ]=6;
st = new field(cell,hashkey(cell) );
////ハッシュテーブル////
boolean visited[ ] = new boolean[ 362880 ];
for(int i=0;i<362880;i++)visited[ i ]=false;
////////探索部分////////
//ソートリストを設定
ev_list list = new ev_list();
list.insert(new ev_list(st) );
visited[ hashkey(cell) ]=true;
field cur;
int hash;
int count=0;
while( (cur=list.pop() )!=null){
count++;
for(int i=0;i<9;i++){
if(cur.cell[ i ]==0){
if(move[ i ][ LEFT ]){
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 ][ 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-3 ];
cur.cell[ i-3 ]=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-3 ]=cur.cell[ i ];
cur.cell[ i ]=0;
}
if(move[ i ][ DOWN ]){
cur.cell[ i ]=cur.cell[ i+3 ];
cur.cell[ i+3 ]=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+3 ]=cur.cell[ i ];
cur.cell[ i ]=0;
}
}
}
if(cur.evaluation==0){
System.out.println(count+"");
System.out.println("evaluation[ "+0+" ]="+dehash(cur.route[ 0 ]).evaluation+"\n"+dehash(cur.route[ 0 ]) );
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) );
System.out.println( dehash(cur.route[ i ]).toString() );
}
break;
}
}
}
}
このプログラムを用いて、このパズルを解いてみました。
「0」が空のマスです。
1 8 0
4 3 2
5 7 6
参考までにヒューリスティック関数の初期値は
h*(x)=0+2+2+0+2+1+1+2=10
出力はこちら。
63
evaluation[0]=10
[1][8][0]
[4][3][2]
[5][7][6]
↓
evaluation[1]=9
evaluation+floor[1]=10
[1][8][2]
[4][3][0]
[5][7][6]
↓
evaluation[2]=8
evaluation+floor[2]=10
[1][8][2]
[4][0][3]
[5][7][6]
↓
evaluation[3]=7
evaluation+floor[3]=10
[1][0][2]
[4][8][3]
[5][7][6]
↓
evaluation[4]=8
evaluation+floor[4]=12
[0][1][2]
[4][8][3]
[5][7][6]
↓
evaluation[5]=9
evaluation+floor[5]=14
[4][1][2]
[0][8][3]
[5][7][6]
↓
evaluation[6]=8
evaluation+floor[6]=14
[4][1][2]
[5][8][3]
[0][7][6]
↓
evaluation[7]=7
evaluation+floor[7]=14
[4][1][2]
[5][8][3]
[7][0][6]
↓
evaluation[8]=6
evaluation+floor[8]=14
[4][1][2]
[5][0][3]
[7][8][6]
↓
evaluation[9]=5
evaluation+floor[9]=14
[4][1][2]
[0][5][3]
[7][8][6]
↓
evaluation[10]=4
evaluation+floor[10]=14
[0][1][2]
[4][5][3]
[7][8][6]
↓
evaluation[11]=3
evaluation+floor[11]=14
[1][0][2]
[4][5][3]
[7][8][6]
↓
evaluation[12]=2
evaluation+floor[12]=14
[1][2][0]
[4][5][3]
[7][8][6]
↓
evaluation[13]=1
evaluation+floor[13]=14
[1][2][3]
[4][5][0]
[7][8][6]
↓
evaluation[14]=0
evaluation+floor[14]=14
[1][2][3]
[4][5][6]
[7][8][0]
と、最短手順14手に辿りつきます。
このときの探索回数は63回となります。
ちなみにこのプログラム、ev_listの「挿入」関数insertのif文周りをコメントアウトすると、
ev_listが単なるキューになり、幅優先探索を行うことになります。
そのときの探索回数は実に4169回！
どれだけヒューリスティックが重要か……というか、如何に幅優先探索が無駄かが良く分かる例ですな。
久しぶりにさらりとうまく言った気がする。
迷路のグダグダがあったからだろうか。
今後も更新頻度上げてきたいです（`・ω・´）。
と、いうより、もっといろんなアルゴリズムを書いていきたいっす。
それではまた（・ω・）ﾉｼ
