続・幅優先探索とスライドパズル
前回は幅優先探索で「6 パズル」を解きました。(1 5 2 6 3 4 0) は 11 手で解くことができましたが、5040 通りの配置の中では、これよりも短い手数で解けるものもあるでしょうし、もっと長い手数がかかるものもあるでしょう。そこで、今度は単純に解くのではなく、パズルが完成するまでにいちばん手数がかかる配置を求めることにします。つまり、最短手数で解いてもいちばん長い手数となる、いちばん難しい配置を求めます。
●最長手数の求め方
最長手数の求め方ですが、5040 通りの配置の最短手数がすべてわかれば、最長の手数となる配置を求めることができます。しかしながら、この方法では時間がとてもかかりそうです。そこで、完成形から始めていちばん長い手数の局面を生成することにします。
まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ伸ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。ただし、初期状態からの探索しかできないので、同一局面のチェックが線形探索のままでは時間がかかる、ということは覚悟してください。
このプログラムの目的は、いちばん長い手数となる配置を求めることなので、その手順を表示することは行いません。このため、ひとつ前の局面番号を格納するベクタ *prev* は定義しません。その代わり、その局面までの手数を格納するベクタ *move* を用意します。ひとつ前の局面の手数を *move* から求め、それに 1 を足せば現在の局面の手数となります。
それから、もうひとつプログラムの欠点を修正します。6 パズルや 15 パズルの場合、同じ駒を続けて動かすと、駒を元の場所に戻すことになってしまいます。これは元の局面に戻ることなので、わざわざ同一局面のチェックを行う必要はありません。前回のプログラムではこのチェックを行っていないため、無駄な探索処理が行われているのです。同じ駒を続けて動かさないようにすれば、実行速度はもう少し速くなるでしょう。この処理は移動した駒をベクタ *piece* に格納しておいて、駒を動かすときに 1 手前と同じ駒かチェックすれば簡単に実現できます。
●プログラムの作成
それではプログラムを作ります。次のリストを見てください。
List 1 : 6 パズルの最長手数を求める(1)
(defun solve-max ()
(let ((rear 1) (front 0))
; 初期化
(setf (aref *state* 0) '(1 2 3 4 5 6 0)
(aref *move* 0) 0
(aref *space* 0) 6
(aref *piece* 0) 0)
(while (< front rear)
(let ((space (aref *space* front))
(board (aref *state* front))
(prev (aref *piece* front)) piece new-board)
(dolist (pos (aref *adjacent* space))
(setq piece (nth pos board))
; 動かす駒のチェック
(when (/= piece prev)
(setq new-board (move-piece piece board))
(unless (find new-board *state* :end rear :test #'equal)
; キューに書き込む
(setf (aref *state* rear) new-board
(aref *space* rear) pos
(aref *move* rear) (1+ (aref *move* front))
(aref *piece* rear) piece)
(incf rear)))))
(incf front))
; 解の表示
(print-answer-max (1- rear))))
関数 solve-max には最終状態をチェックする処理がないことに注意してください。生成できる局面がなくなるまで、つまりキューにデータがなくなるまで処理を繰り返します。
それから、同じ駒を続けて動かさないようにチェックします。1 手前に移動した駒を prev にセットし、これから移動する駒 piece と比較します。違う駒であれば、move-piece で piece を移動します。キューに書き込むときは、移動した駒 piece をベクタ *piece* に追加することをお忘れなく。
最後に print-answer-max で最長手数とその配置を出力します。この関数は簡単なので説明は省略します。プログラムリスト をお読みくださいませ。
これでプログラムは完成です。さっそく実行してみましょう。
(solve-max) 最長手数 15 手 (4 6 5 1 3 2 0) (4 3 5 0 6 2 1) (0 6 5 4 3 2 1) (4 6 2 0 3 5 1) (4 3 2 1 6 5 0) (0 3 2 4 6 5 1) (4 6 0 5 3 2 1) (0 6 4 5 3 1 2) (0 6 3 4 5 1 2) (4 0 5 6 3 2 1) (0 4 6 5 3 2 1) (4 6 5 0 2 3 1) (0 4 5 6 1 2 3) (0 5 4 6 3 2 1) (6 0 3 4 5 2 1) (5 2 0 4 3 6 1) (0 2 5 4 1 6 3) (0 5 6 4 2 3 1) (0 3 1 4 6 2 5) (1 6 2 4 3 5 0) (3 6 1 4 0 2 5) (0 1 2 4 3 5 6) (1 3 5 4 6 2 0) (2 1 5 4 3 0 6)
最長手数は 15 手で、その配置は全部で 24 通りになりました。そのうちのひとつを図に示すと次のようになります。
図 1 : いちばん難しい配置の例
ちなみに、生成した全局面は 5040 個になりました。しがたって、6 パズルでは数字をランダムに配置しても、必ず完成形に到達できることがわかります。実行時間ですが、M.Hiroi のオンボロマシン (Pentium 166 MHz) では約 53 秒 と時間がかかります。生成した局面は 5040 個もあるのですから、データの比較は相当の回数になります。実行時間の短縮には、同一局面のチェックに高速な探索アルゴリズムを使う必要があります。
●ハッシュ法による高速化
それでは同一局面のチェックにハッシュ法を使ってみましょう。ハッシュ法のプログラムは、拙作の ちょっと寄り道「ハッシュ法」 で作成したプログラムとほとんど同じです。ハッシュ法の詳しい説明は、そちらをお読みくださいませ。プログラムは次のようになります。
List 2 : 6 パズルの最長手数を求める(2)
(defun solve-max1 ()
(let ((rear 1) (front 0))
; 初期化
(setf (aref *state* 0) '(1 2 3 4 5 6 0)
(aref *move* 0) 0
(aref *space* 0) 6
(aref *piece* 0) 0)
(init-hash)
(insert-hash '(1 2 3 4 5 6 0))
(while (< front rear)
(let ((space (aref *space* front))
(board (aref *state* front))
(prev (aref *piece* front)) piece new-board)
(dolist (pos (aref *adjacent* space))
(setq piece (nth pos board))
; 動かす駒のチェック
(when (/= prev piece)
(setq new-board (move-piece piece board))
; ハッシュ法による同一局面のチェック
(when (insert-hash new-board)
(setf (aref *state* rear) new-board
(aref *space* rear) pos
(aref *move* rear) (1+ (aref *move* front))
(aref *piece* rear) piece)
(incf rear)))))
(incf front))
(print-answer-max (1- rear))))
キューの初期化といっしょにハッシュ表の初期化を関数 init-hash で行い、初期状態を関数 insert-hash でハッシュ表に登録します。insert-hash は、ハッシュ表にデータが見つからない場合はデータを登録して真を返し、データを見つけた場合は nil を返します。init-hash と insert-hash の詳細は プログラムリスト をお読みくださいませ。
あとは、同一局面のチェックで insert-hash を呼び出して、new-board が新しい局面であればキューに登録します。これでプログラムは完成です。
さっそく実行してみたところ、実行時間は 6.2 秒 (Pentium 166 MHz) まで短縮されました。約 9 倍弱の高速化ですね。ハッシュ法の効果は十分に出ていると思います。ところで、今回のプログラムはハッシュ表の大きさを 1009 としましたが、実行速度はハッシュ表の大きさやハッシュ関数によって大きく変化します。興味のある方はいろいろ試してみてください。
●プログラムリスト
;
; six_max.l : 「6 パズル」の最長手数を求める
;
; Copyright (C) 2002 Makoto Hiroi
;
; キューの定義
(defvar *state* (make-array 5040)) ; 局面を格納する
(defvar *space* (make-array 5040)) ; 空き場所の位置
(defvar *move* (make-array 5040)) ; 手数
(defvar *piece* (make-array 5040)) ; 動かした駒
; 隣接リスト
(defvar *adjacent* #((1 2 3) ; 0
(0 3 4) ; 1
(0 3 5) ; 2
(0 1 2 4 5 6) ; 3
(1 3 6) ; 4
(2 3 6) ; 5
(3 4 5))) ; 6
; 駒を動かす（リストはコピーされる）
(defun move-piece (piece board)
(cond ((null board) nil)
((= piece (car board))
(cons 0 (move-piece piece (cdr board))))
((= 0 (car board))
(cons piece (move-piece piece (cdr board))))
(t (cons (car board) (move-piece piece (cdr board))))))
; 最長手数の局面を表示
(defun print-answer-max (pos)
(let ((max-move (aref *move* pos)))
(format t "~%最長手数 ~D 手" max-move)
(while (= max-move (aref *move* pos))
(print (aref *state* pos))
(decf pos))))
; 最長手数の局面を求める
(defun solve-max ()
(let ((rear 1) (front 0))
; 初期化
(setf (aref *state* 0) '(1 2 3 4 5 6 0)
(aref *move* 0) 0
(aref *space* 0) 6
(aref *piece* 0) 0)
;
(while (< front rear)
(let ((space (aref *space* front))
(board (aref *state* front))
(prev (aref *piece* front)) piece new-board)
(dolist (pos (aref *adjacent* space))
(setq piece (nth pos board))
; 動かす駒のチェック
(when (/= piece prev)
(setq new-board (move-piece piece board))
(unless (find new-board *state* :end rear :test #'equal)
; キューに書き込む
(setf (aref *state* rear) new-board
(aref *space* rear) pos
(aref *move* rear) (1+ (aref *move* front))
(aref *piece* rear) piece)
(incf rear)))))
(incf front))
; 解の表示
(print-answer-max (1- rear))))
;
; ***** ハッシュ法 *****
;
; 初期化 (1009 は素数)
(defun init-hash ()
(setq *myhash* (make-array 1009)))
; ハッシュ値の計算
(defun hash-value (state)
(let ((value 0))
(dolist (x state (mod value 1009))
(setq value (+ (* value 10) x)))))
; ハッシュ表に挿入
(defun insert-hash (state)
(let ((value (hash-value state)))
(unless (find state (aref *myhash* value) :test #'equal)
; 挿入する
(push state (aref *myhash* value)))))
; 最長手数の局面を求める
(defun solve-max1 ()
(let ((rear 1) (front 0))
; 初期化
(setf (aref *state* 0) '(1 2 3 4 5 6 0)
(aref *move* 0) 0
(aref *space* 0) 6
(aref *piece* 0) 0)
(init-hash)
(insert-hash '(1 2 3 4 5 6 0))
;
(while (< front rear)
(let ((space (aref *space* front))
(board (aref *state* front))
(prev (aref *piece* front)) piece new-board)
(dolist (pos (aref *adjacent* space))
(setq piece (nth pos board))
; 動かす駒のチェック
(when (/= prev piece)
(setq new-board (move-piece piece board))
; ハッシュ法による同一局面のチェック
(when (insert-hash new-board)
(setf (aref *state* rear) new-board
(aref *space* rear) pos
(aref *move* rear) (1+ (aref *move* front))
(aref *piece* rear) piece)
(incf rear)))))
(incf front))
(print-answer-max (1- rear))))
図 2 : 下限値の求め方