アルゴリズムc 第6回

[注意]今回のプログラムの内容を全ての人が隅々まで理解する必要はありません。 ただし、プログラム中で使われている 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。

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


プログラム

起動時にコマンド引数を与えると動作が異なる。 






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

...(略)...








アルゴリズムc 演習






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





提出した後は、正しく提出されていることを

http://ynitta.com/class/algoC/local/handin/

で必ず確認しておいて下さい。





課題提出〆切は次回の講義の開始時刻です。




課題6a





提出ファイルPuzzle8.java


コメント欄:

data3.txt, data4.txt それぞれについて

    

  • 最小の手数
    • 

  • 「optionなし」「-cオプション」「-dオプション」
それぞれについての hash.size()の値
    • 


を答えること。


提出先:
「宿題提出Web:アルゴリズムB：課題6a」

http://ynitta.com/class/algoC/local/handin/up.php?id=kadai6a








正しく並んだ解を得るまでの最小の手数を求めるプログラム 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