アルゴリズムB 第11回


[注意]今回のプログラムの内容を全ての人が隅々まで理解する必要はありません。 ただし、プログラム中で使われている HashMap, PriorityQueue, BitSet クラスと Comparable インターフェイス に関しては、必ずJava APIを読んでおいて下さい。

A*アルゴリズムの応用

8パズル

3×3のボードの上で8枚の駒を、空いたマス目を利用して動かし、目的の形にするパズル。 空白部に隣接する駒をスライドすることで盤面を操作する。

(この並び順にするのが目的)

入力形式

P1,1 P1,2 P1,3
P2,1 P2,2 P2,3
P3,1 P3,2 P3,3

Pi,jはそれぞれ0〜8の異なる整数であり、 1〜8がパネルに書かれた数字を、0が穴を表している。

与えられたデータに対し、正しく並べ替える最短の手数を求めるプログラムを作成せよ。

出力

「最短の手数」と「初期状態から最後までの盤面の状態」 と「解を得るまでに確定したノードの数」を示せ。 もしも解がない場合は "no answer" と出力すること。


h*(x)の候補0: 常に0

経由地から終点までの道のりは考慮しない。常に h*(x) = 0。


h*(x)の候補1: 正しくない場所にあるパネルの枚数

正しくない位置にあるパネルの個数。 下の例では h* (x) = 6。


穴の位置は計算に入れないことに注意しましょう。 もし穴の位置も計算に入れると、例えば1枚だけパネルがずれて

1 2 3
4 5 6
7 _ 8
となっている場合に、正しくはh(x)=1ですがこれをh*(x)=2 と間違ってしまい、 h*(x) <= h(x) が成り立たなくなってしまいます。

h*(x)の候補2: 正しい場所までのマンハッタン距離の和

位置が正しくないパネルの、正しい位置までのマンハッタン距離の和。 下の例では h* (x) = 1 + 1 + 1 + 2 + 3 + 3 = 11。

この方法でもパネルの位置だけを考慮し、穴の位置は計算に入れないことに注意しましょう。



プログラム

起動時にコマンド引数を与えると動作が異なる。
Puzzle8.java
import java.util.*;
public class Puzzle8 {
    static int mode;		// 0: dijkstra, 1: unmatched, 2: distance
    static final int BW=4;	// 1個のパネルを表現するのに必要なbit数
    static final int W=3;	// 盤の幅
    static final int N=3*3;	// パネルの枚数
    HashMap<BitSet,State> hash;	// 確定したノードを記録しておくメモ
    PriorityQueue<State> queue; // 未確定のノードを入れておくキュー
    int[][] dirs = {{1,0}, {0,-1}, {-1,0}, {0,1}}; // RIGHT,UP,LEFT,DOWN
    State solve(int[] board) {
	hash = new HashMap<BitSet,State>();
	queue = new PriorityQueue<State>();
	BitSet bs = board2bs(board); // ボードの状態をBitSetで表現する
	State state = new State(bs,0,-1); // 初期状態のノード (盤面、手数、操作)
	queue.add(state);	// 初期状態のノードをキューに入れる

	while (queue.size() > 0) { // キューにノードが存在する限り繰り返す
	    State s = queue.poll(); // 最も評価値が小さいノードを取り出して
	    if (s.h1() == 0) return s; // 正しく並んだら終了
	    if (hash.get(s.bs) != null) continue; // メモに記録されたノードは調べない
	    hash.put(s.bs,s);	// 最短距離が確定したノードをメモする
	    int zidx = getIndex(s.bs,0); // 穴の位置を取り出し
	    for (int i=0; i<dirs.length; i++) {	// 穴の上下左右のパネルを動かす
		int x = zidx%W;	// 穴の位置(x,y)
		int y = zidx/W;
		int nx = x + dirs[i][0]; // 動かすパネルの位置(nx,ny)
		int ny = y + dirs[i][1];
		if (nx>=0 && nx<W && ny>=0 && ny<W) { // はみでていなければ
		    int tidx = nx + ny * W; // 動かすパネルの一次元での位置
		    BitSet nbs = (BitSet) s.bs.clone();	// 盤の状態をコピーして
		    int val = get(nbs,tidx); // 動かすパネルに書いてある数字
		    int zero = get(nbs,zidx); // 穴の数字(0のはず)
		    assert zero == 0; // 確認
		    set(nbs,zidx,val); // 穴の位置にパネルを動かし
		    set(nbs,tidx,zero);	// 元のパネルの位置に穴がくる
		    if (hash.get(nbs) != null) continue; // メモにあれば捨てる
		    State ns = new State(nbs,s.distance+1,i); // 手数と操作と組にして
		    queue.add(ns); // キューに入れる
		}
	    }
	}
	return null;
    }
    BitSet prev(BitSet bs,int op) { // 盤面と操作から一手前の盤面を求める
	BitSet pbs = (BitSet) bs.clone();
	int zidx = getIndex(pbs,0);
	int x = zidx % W;
	int y = zidx / W;
	int px = x - dirs[op][0];
	int py = y - dirs[op][1];
	assert px>=0 && px<W && py >=0 && py<W;
	int pidx = px + py*W;
	int val = get(pbs,pidx);
	int zero = get(pbs,zidx);
	assert zero == 0;
	set(pbs,zidx,val);
	set(pbs,pidx,zero);
	return pbs;
    }
    Vector<State> getPath(State s) { // その盤面に到るまでの盤面をVectorで返す
	Vector<State> v = new Vector<State>();
	v.add(s);
	while (s.op >= 0) {
	    BitSet bs = prev(s.bs,s.op);
	    s = hash.get(bs);
	    assert s != null;
	    v.add(s);
	}
	return v;
    }
    static BitSet board2bs(int[] board) { // 盤面を表す配列からBitSetへ
	BitSet bs = new BitSet(BW*N);
	for (int i=0; i<N; i++) set(bs,i,board[i]);
	return bs;
    }
    static int[] bs2board(BitSet bs) { // 盤面を表すBitSetから配列へ
	int[] b = new int[N];
	for (int i=0; i<N; i++) b[i] = get(bs,i);
	return b;
    }
    static void set(BitSet bs,int idx,int val) { // idx番めのパネルの値をvalにする
	for (int i=0; i<BW; i++) {
	    bs.set(idx*BW+i,(val & 0x1)==1);
	    val >>>= 1;
	}
    }
    static int get(BitSet bs,int idx) {	// idx番めのパネルの値を取り出す
	int val=0;
	for (int i=BW-1; i>=0; i--) {
	    val = val * 2 + ((bs.get(idx*BW+i))? 1 : 0);
	}
	return val;
    }
    static int getIndex(BitSet bs,int val) { // 値がvalのパネルが何番目か
	for (int i=0; i<N; i++)
	    if (val == get(bs,i)) return i;
	return -1;
    }
    public static void main(String[] args) {
	mode = 0;
	if (args.length > 0) {
	    if (args[0].equals("-c")) mode=1;
	    else if (args[0].equals("-d")) mode=2;
	}
	Scanner sc = new Scanner(System.in);
	int[] board = new int[N];
	for (int i=0; i<N; i++)
	    board[i] = sc.nextInt();
	Puzzle8 p = new Puzzle8();
	State s = p.solve(board);
	if (s == null) { System.out.println("no answer"); System.exit(-1);}
	Vector<State> v = p.getPath(s);
	System.out.println("path.size() = "+v.size());
	System.out.println("hash.size() = "+p.hash.size());
	for (int i=v.size()-1; i>=0; --i)
	    System.out.println(v.get(i));
    }
    static class State implements Comparable<State> { // ノード(盤面、手数、操作)
	BitSet bs;
	int distance;
	int op;			// RIGHT,UP,LEFT,DOWN
	int f;
	public State(BitSet bs,int distance,int op) {
	    this.bs = bs;
	    this.op = op;
	    this.distance = distance;
	    f = distance + ((mode==2)?h2():((mode == 1)?h1():0));
	}
	public int compareTo(State s) {	// 比較に使う
	    return f - s.f;
	}
	int h1() {		// 経由地から目的地までの推定距離:(候補1)

	    // [課題] 候補1の方法でh*()を計算せよ

	}
	int h2() {		// 経由地から目的地までの推定距離:(候補2)

	    // [課題] 候補2の方法でh*()を計算せよ

	}
	public String toString() {
	    StringBuffer sb = new StringBuffer();
	    for (int i=0; i<N; i++)
		sb.append(Puzzle8.get(bs,i) + (((i+1)%W==0)?"\n":" "));
	    return sb.toString();
	}
    }
}
data01.txt
1 2 3
7 4 6
5 0 8
Puzzle8.javaの実行例
$ javac Puzzle8.java
$ java Puzzle8 < data01.txt
path.size() = 6
hash.size() = 57
1 2 3
7 4 6
5 0 8

1 2 3
7 4 6
0 5 8

1 2 3
0 4 6
7 5 8

1 2 3
4 0 6
7 5 8

1 2 3
4 5 6
7 0 8

1 2 3
4 5 6
7 8 0

$ java Puzzle8 -c <data01.txt
path.size() = 6
hash.size() = 7

...(略)...

$ java Puzzle8 -d < data01.txt
path.size() = 6
hash.size() = 6

...(略)...

data02.txt
7 8 2
6 3 4
5 0 1
Puzzle8.javaの実行例
$java Puzzle8 < data02.txt
path.size() = 26
hash.size() = 153107

...(略)...


$ java Puzzle8 -c < data02.txt
path.size() = 26
hash.size() = 24382

...(略)...

$ java Puzzle8 -d < data02.txt
path.size() = 26
hash.size() = 1370

...(略)...


アルゴリズムB 演習


作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。

提出した後は、正しく提出されていることを http://nw.tsuda.ac.jp/class/algoB/local/handin/ で必ず確認しておいて下さい。

〆切は次週の金曜日13:00です。

課題11a

提出ファイルPuzzle8.java
コメント欄: data3.txt, data4.txt それぞれについて
  • 最小の手数
  • 「optionなし」「-cオプション」「-dオプション」 それぞれについての hash.size()の値
を答えること。
提出先: 「宿題提出Web:アルゴリズムB:課題11a」 http://nw.tsuda.ac.jp/class/algoB/local/handin/up.php?id=kadai11a

正しく並んだ解を得るまでの最小の手数を求めるプログラム Puzzle8.java の 抜けている部分のコードを自分で書きなさい。

次のdata03.txtとdata04.txt を入力としたとき、 コマンドオプションによって解を得るまでに確定したノードの数がどのように 変わるか調べなさい。

data03.txt
7 6 2
0 4 8
3 1 5
data04.txt
8 7 6
5 2 0
4 3 1