今回は幅優先探索の具体的な例題として、15 パズルでお馴染みの「スライドパズル（スライディングブロックパズル）」を SML/NJ で解いてみましょう。なお、このドキュメントは拙作の パズルでプログラミング 「第 2 回 幅優先探索と 15 パズル」 のプログラムを SML/NJ で書き直したものです。内容は重複していますが、ご了承くださいませ。
┌─┬─┬─┬─┐
│１│２│３│４│
├─┼─┼─┼─┤
│５│６│７│８│
├─┼─┼─┼─┤
│９│10│11│12│
├─┼─┼─┼─┤
│13│14│15│ │
└─┴─┴─┴─┘
図 : 15 パズル
文献 [1] によると、15 パズルはアメリカのサム・ロイドが 1870 年代に考案したパズルで、彼はパズルの神様と呼ばれるほど有名なパズル作家だそうです。
15 パズルは左図に示すように、1 から 15 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を飛び越したり持ち上げたりすることはできません。
15 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、16! (約 2e13) 通りもあります。実際には、15 パズルの性質 [*1] からその半分になるのですが、それでもパソコンで扱うにはあまりにも大きすぎる数です。そこで、盤面を六角形に変形し、1 から 6 までの数字を並べる「6 パズル」を考えることにします。
１------５ １------２
／ ＼ ／ ＼ ／ ＼ ／ ＼
２------６------３ ===> ３------４------５
＼ ／ ＼ ／ ＼ ／ ＼ ／
４------０ ６------０
完成形
図 : 6 パズル
上図は 6 パズルをグラフで表したものです。0 が空き場所を表します。ここには 3, 4, 6 の駒を動かすことができます。6 パズルは単純に考えると駒の配置は 7! = 5040 通りとなります。これならば簡単に解くことができそうです。
6 パズルの盤面はリストを使って表します。下図に盤面の位置とリストの対応を示します。
１------５ ０------１
／ ＼ ／ ＼ ／ ＼ ／ ＼
２------６------３ ２------３------４
＼ ／ ＼ ／ ＼ ／ ＼ ／
４------０ ５------６
盤面:[1,5,2,6,3,4,0] 盤面とリストの対応
図 : 6 パズルの盤面
隣接リストとキューの定義は次のようになります。
リスト : 隣接リストとキューの定義
(* 隣接リスト *)
val 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 *)
(* キューの定義 *)
val max_state = 5040 (* 7! *)
val state_table = Array.array( max_state, nil: int list )
val prev_table = Array.array( max_state, 0 );
val space_table = Array.array( max_state, 0 );
このプログラムでは配列を使ってキューを定義します。配列によるキューの実装は拙作のページ ちょっと寄り道「配列によるキューの実装」 で詳しく説明しているので参考にしてください。6 パズルの局面は最大で 5040 通りなので、キュー（配列）の大きさは 5040 とします。
次は移動手順の管理を考えます。最短手順を求めるだけならば、全ての手順を記憶しておく必要はありません。n 手目の移動で作られた局面が n 手目以前の局面で出現しているのであれば、n 手より短い手数で到達する移動手順があるはずです。したがって、この n 手の手順を記憶しておく必要はないのです。そこで、キューには局面だけを格納し、手順は番号で管理することにします。
| 図 : 手順の管理 | ||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
左図を使って具体的に説明しましょう。局面は配列 state_table に格納します。このときの添字がその局面の番号になります。そして、その 1 手前の局面の番号を配列 prev_table に格納します。まず最初の局面を state_table の 0 番目にセットします。prev_table の 0 番目には終端を表すため -1 をセットします。
それから、駒を移動して 1 手目の局面を生成します。移動できる駒は 3 つあるので、新しく生成される局面は 3 つとなります。それぞれ、state_table の 1 番目から 3 番目にセットし、prev_table には元になった局面の番号 0 をセットします。
次に、2 手目の局面を生成します。state_table の 1 番目で駒を動かして生成される局面は 6 つありますが、そのうちの一つは元の局面に戻るので、新しい局面は 5 つになります。これらを state_table の 4 番目から 8 番目にセットします。このときの prev_table の値には、元になった局面の番号 1 がセットされます。
あとは同様に、キューから局面を取り出して駒を動かし、新しい局面であればキューに登録することを繰り返します。最終状態と同じ局面になったときは、prev_table をたどることで手順を再現することができます。
駒の移動は動かすことができる駒を探すよりも、空き場所を基準に考えた方が簡単です。その局面での空き場所の位置を配列 space_table に記憶しておきます。新しい局面を作るときは、空き場所に隣接している駒を隣接リストから求め、それを空き場所に移動させればいいわけです。
それではプログラムを作りましょう。最初に、駒を移動して新しい局面を作る関数 move_piece を作ります。
リスト : 駒を動かす
fun move_piece( _, nil ) = nil
| move_piece( a, x::xs ) =
if x = a then 0 :: move_piece( a, xs )
else if x = 0 then a :: move_piece( a, xs )
else x :: move_piece( a, xs )
関数 move_piece の第 1 引数 a が動かす駒、第 2 引数が局面を表すリストです。駒の移動はリストをコピーして空き場所 (0) と駒 a を交換するだけです。move_piece はこの処理を再帰定義で実現しています。リストをコピーしている途中で、0 を見つけたら a に、a を見つけたら 0 に置き換えます。これで駒 a を動かした局面を生成することができます。
次は、幅優先探索を行う関数 solve を作ります。
リスト : 6 パズルの解法(1)
fun solve_b( front, rear, goal ) =
if front = rear then ()
else solve_b( front + 1,
make_new_state( rear, front, goal,
List.nth( adjacent, Array.sub( space_table, front ))),
goal )
fun solve( start, goal ) = (
(* 初期化 *)
Array.update( state_table, 0, start );
Array.update( prev_table, 0, 0 );
Array.update( space_table, 0, position_if( fn(x) => x = 0, start ) );
solve_b( 0, 1, goal ) handle Exit => ()
)
プログラムの骨格は 経路の探索 で説明した幅優先探索と同じです。関数 solve の引数 start がスタートの局面で、goal がゴールの局面です。solve はキューを初期化するだけで、実際の処理は関数 solve_b で行います。このプログラムでは、最短手順を見つけたら例外 Exit を送出して処理を終了します。このため、handle で例外 Exit を補足しています。
関数 slove_b の引数 front と rear はキューの先頭と末尾を表します。最初に初期状態 start をキューに登録するので、solve_b の引数 rear の値は 1 になります。キューにデータがある間、solve_b は処理を繰り返しますが、この処理を while ループではなく再帰定義でプログラムしています。
引数 front と rear が等しくなるとキューは空になります。この場合、解はありません。そうでなければ、キューから局面を一つ取り出して、新しい局面を生成してキューに追加します。この処理を関数 make_new_state で行います。make_new_state はキューの末尾の値 (rear) を返すので、この値を使って solve_b を再帰呼び出しします。これでキューにデータがある間、探索処理を繰り返すことができます。
次は関数 make_new_state を作ります。次のリストを見てください。
リスト : 新しい局面を作る
fun make_new_state( rear, front, goal, nil ) = rear
| make_new_state( rear, front, goal, x::xs ) =
let
val state = Array.sub( state_table, front )
val new_state = move_piece( List.nth( state, x ), state )
in
if check_same_state( new_state, rear - 1 )
then make_new_state( rear, front, goal, xs )
else (
Array.update( state_table, rear, new_state );
Array.update( prev_table, rear, front );
Array.update( space_table, rear, x );
if goal = new_state
then (print_answer( rear ); raise Exit)
else make_new_state( rear + 1, front, goal, xs )
)
end
make_new_state の第 4 引数が隣接リストです。隣接リストが空リスト (nil) になったら rear を返します。そうでなければ、move_piece で x の位置にある駒を空き場所へ移動します。move_piece の返り値は変数 new_state にセットします。次に、関数 check_same_state で state_table に new_state と同じ局面がないかチェックします。
同じ局面がある場合、check_same_state は true を返すので、rear の値をそのままにして make_new_state を再帰呼び出しします。同一局面がない場合は new_state をキューに登録します。そして、ゴールに到達したかチェックします。そうであれば、関数 print_answer で手順を表示し、raise で例外 Exit を送出して探索を終了します。新しい局面を追加したときは、rear を +1 して make_new_state を再帰呼び出しします。
手順を表示する関数 print_answer は簡単です。
リスト : 手順の表示
(* int list の表示 *)
fun print_intlist( nil ) = print( "\n" )
| print_intlist( x::xs ) =
( print( Int.toString(x) ^ " " ); print_intlist( xs ) )
(* 手順を表示する *)
fun print_answer( n ) = (
if n > 0 then print_answer( Array.sub( prev_table, n ) ) else ();
print_intlist( Array.sub( state_table, n ) ) )
局面を表すリストを print_intlist でそのまま出力します。prev_table を順番にたどって出力すると、手順は逆順に表示されてしまいます。そこで、再帰呼び出しを使って最初の状態に戻り、そこから局面を順番に出力させます。
関数 check_same_state は単純な線形探索なので説明は省略いたします。あとは特に難しいところはないでしょう。詳細は プログラムリスト１ をお読みください。
これでプログラムは完成です。それでは実行してみましょう。
- solve( [1, 5, 2, 6, 3, 4, 0], [1, 2, 3, 4, 5, 6, 0] ); 1 5 2 6 3 4 0 1 5 2 0 3 4 6 0 5 2 1 3 4 6 2 5 0 1 3 4 6 2 5 1 0 3 4 6 2 5 1 3 0 4 6 2 0 1 3 5 4 6 0 2 1 3 5 4 6 1 2 0 3 5 4 6 1 2 3 0 5 4 6 1 2 3 4 5 0 6 1 2 3 4 5 6 0 val it = () : unit
11 手で解くことができました。実行時間は M.Hiroi のオンボロマシン (Windows95, Pentium 166 MHz) で約 4 秒でした。簡単に解けると思っていたのですが、けっこう時間がかかりますね。
時間がかかる理由の一つは、同一局面のチェックを行う関数 check_same_state にあります。線形探索は配列の要素を順番に比較していくため、その実行時間はデータ数に比例します。今回生成された局面は 2818 個だったのですが、一つの局面から複数の局面を生成し、それを検索するのですから、データの比較回数は相当の数になるでしょう。時間がかかるのは当然のことなのです。
このようなときの常套手段が、線形探索に代えて高速な検索アルゴリズムを使うことです。ハッシュ法や二分探索木など、優れたアルゴリズムを使うことで、実行時間を大幅に短縮することができます。ところが、幅優先探索の場合にはもう一つ方法があります。出発点から探索するだけではなくゴール地点からも探索を行うことで、生成される局面数を大幅に減らすことができるのです。
その理由を説明するために、簡単なシミュレーションをしてみましょう。たとえば、1 手進むたびに 3 つの局面が生成され、5 手で解けると仮定します。すると、n 手目で生成される局面は 3 の n 乗個になるので、初期状態から単純に探索すると、生成される局面の総数は、3 + 9 + 27 + 81 + 243 = 363 個となります。
これに対し、初期状態と終了状態から同時に探索を始めた場合、お互い 3 手まで探索した時点で同じ局面に到達する、つまり、解を見つけることができます。この場合、生成される局面の総数は 3 手目までの局面数を 2 倍した 78 個となります。
生成される局面数はぐっと少なくなりますね。局面数が減少すると同一局面の検索処理に有利なだけではなく、「キューからデータを取り出して新しい局面を作る」という根本的な処理の回数を減らすことになるので、処理速度は大幅に向上するのです。
それではプログラムを作りましょう。単純に考えると、2 つの探索処理を交互に行うことになりますが、そうするとプログラムの大幅な修正が必要になります。ここは、探索方向を示すフラグを用意することで、一つのキューだけで処理することにしましょう。メモリを余分に使うことになりますが、プログラムの修正は最小限で済みます。
(* 探索の方向 *) datatype direction = Forward | Backward val dir_table = Array.array( max_state, Forward )
探索方向を示すデータ型 direction を datatype で定義し、配列 dir_table に格納します。初期状態からの探索は Forward を、終了状態からの探索は Backward をセットします。探索プログラムは次のようになります
リスト : 6 パズルの解法 (2)
fun make_new_state( rear, front, nil ) = rear
| make_new_state( rear, front, x::xs ) =
let
val state = Array.sub( state_table, front )
val new_state = move_piece( List.nth( state, x ), state )
val dir = Array.sub( dir_table, front )
val pos = check_same_state( new_state, rear - 1 )
in
if pos <> ~1
then
if Array.sub( dir_table, pos ) <> dir
then (print_answer( front, pos ); raise Exit)
else make_new_state( rear, front, xs )
else (
Array.update( state_table, rear, new_state );
Array.update( prev_table, rear, front );
Array.update( dir_table, rear, dir );
Array.update( space_table, rear, x );
make_new_state( rear + 1, front, xs )
)
end
fun solve_b( front, rear ) =
if front = rear then ()
else solve_b( front + 1,
make_new_state( rear, front,
List.nth( adjacent, Array.sub( space_table, front ))))
fun solve(start, goal) = (
(* start *)
Array.update( state_table, 0, start );
Array.update( prev_table, 0, ~1 );
Array.update( dir_table, 0, Forward );
Array.update( space_table, 0, position_if( fn(x) => x = 0, start ) );
(* goal *)
Array.update( state_table, 1, goal );
Array.update( prev_table, 1, ~1 );
Array.update( dir_table, 1, Backward );
Array.update( space_table, 1, position_if( fn(x) => x = 0, goal ) );
(* 探索 *)
solve_b( 0, 2 ) handle Exit => ()
)
キューの初期化では最初に初期状態を、次に終了状態をセットします。2 つのデータをセットしたのですから、solve_b の引数 rear の値は 2 になります。最初に、初期状態から 1 手目の局面が生成され、次に終了状態から 1 手目の局面が生成されます。
駒の移動は同じなので説明は省略しますが、dir_table の値をセットする処理を追加していることに注意してください。配列 dir_table の値を比較するため、関数 check_same_state は見つけた局面の番号を返すように修正します。見つからない場合は -1 を返します。
同じ局面を見つけたとき、dir_table を比較して探索方向が異なっていれば、2 方向の探索で同一局面に到達したことがわかります。見つけた最短手順を print_answer で出力します。同じ探索方向であれば、キューへの追加は行いません。
手順の表示は探索方向によって処理が異なるので、print_answer で振り分けます。
リスト : 解の表示
(* 手順を表示する *)
fun print_answer_forward( n ) = (
if n > 0 then print_answer_forward( Array.sub( prev_table, n ) ) else ();
print_intlist( Array.sub( state_table, n ) ) )
fun print_answer_backward( ~1 ) = ()
| print_answer_backward( n ) = (
print_intlist( Array.sub( state_table, n ) );
print_answer_backward( Array.sub( prev_table, n ) ))
fun print_answer( n, m ) =
if Array.sub( dir_table, n ) = Forward
then (print_answer_forward( n ); print_answer_backward( m ))
else (print_answer_forward( m ); print_answer_backward( n ))
初期状態からの手順を表示する関数が print_answer_forward です。この処理は、今までの print_answer と同じです。終了状態までの手順を表示するのが print_answer_backward です。これは prev_table を順番にたどって表示するだけなので簡単です。
あとは特に難しいところはないでしょう。詳細は プログラムリスト２ をお読みください。
さっそく実行してみると、生成された局面数は 341 個で、実行時間は 0.11 秒でした。約 37 倍の高速化ですね。このように、双方向からの探索はとても効果が高い方法です。
(*
* six.sml : 6 パズルの解法(1)
*
* Copyright (C) 2005 Makoto Hiroi
*)
(* 例外の定義 *)
exception PuzError
exception Exit
fun position_if( f, l ) =
let
fun position_if_sub( _, nil ) = ~1
| position_if_sub( n, x::xs ) =
if f( x ) then n else position_if_sub( n + 1, xs )
in
position_if_sub( 0, l )
end
(* 隣接リスト *)
val 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 *)
(* キューの定義 *)
val max_state = 5040 (* 7! *)
val state_table = Array.array( max_state, nil: int list )
val prev_table = Array.array( max_state, 0 );
val space_table = Array.array( max_state, 0 );
(* 駒を動かす *)
fun move_piece( _, nil ) = nil
| move_piece( a, x::xs ) =
if x = a then 0 :: move_piece( a, xs )
else if x = 0 then a :: move_piece( a, xs )
else x :: move_piece( a, xs )
(* 同一局面のチェック：線形探索 *)
fun check_same_state( state, ~1 ) = false
| check_same_state( state, n ) =
if Array.sub( state_table, n ) = state
then true
else check_same_state( state, n - 1 )
(* int list の表示 *)
fun print_intlist( nil ) = print( "\n" )
| print_intlist( x::xs ) =
( print( Int.toString(x) ^ " " ); print_intlist( xs ) )
(* 手順を表示する *)
fun print_answer( n ) = (
if n > 0 then print_answer( Array.sub( prev_table, n ) ) else ();
print_intlist( Array.sub( state_table, n ) ) )
(* 新しい局面を作る *)
fun make_new_state( rear, front, goal, nil ) = rear
| make_new_state( rear, front, goal, x::xs ) =
let
val state = Array.sub( state_table, front )
val new_state = move_piece( List.nth( state, x ), state )
in
if check_same_state( new_state, rear - 1 )
then make_new_state( rear, front, goal, xs )
else (
Array.update( state_table, rear, new_state );
Array.update( prev_table, rear, front );
Array.update( space_table, rear, x );
if goal = new_state
then (print_answer( rear ); print(Int.toString(rear)^"\n");raise Exit)
else make_new_state( rear + 1, front, goal, xs )
)
end
(* 幅優先探索 *)
fun solve_b( front, rear, goal ) =
if front = rear then ()
else solve_b( front + 1,
make_new_state( rear, front, goal,
List.nth( adjacent, Array.sub( space_table, front ))),
goal )
fun solve(start, goal) = (
(* 初期化 *)
Array.update( state_table, 0, start );
Array.update( prev_table, 0, 0 );
Array.update( space_table, 0, position_if( fn(x) => x = 0, start ) );
solve_b( 0, 1, goal ) handle Exit => ()
)
fun solve_exe() =
let
val a = Timer.startRealTimer()
in
solve([1, 5, 2, 6, 3, 4, 0], [1, 2, 3, 4, 5, 6, 0]);
Timer.checkRealTimer( a )
end
(*
* six2.sml : 6 パズルの解法(2)
*
* Copyright (C) 2005 Makoto Hiroi
*)
(* 例外の定義 *)
exception PuzError
exception Exit
fun position_if( f, l ) =
let
fun position_if_sub( _, nil ) = ~1
| position_if_sub( n, x::xs ) =
if f( x ) then n else position_if_sub( n + 1, xs )
in
position_if_sub( 0, l )
end
(* 隣接リスト *)
val 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 *)
(* 探索方向の定義 *)
datatype direction = Forward | Backward
(* キューの定義 *)
val max_state = 5040 (* 7! *)
val state_table = Array.array( max_state, nil: int list )
val prev_table = Array.array( max_state, 0 )
val space_table = Array.array( max_state, 0 )
val dir_table = Array.array( max_state, Forward )
(* 駒の移動 *)
fun move_piece( _, nil ) = nil
| move_piece( a, x::xs ) =
if x = a then 0 :: move_piece( a, xs )
else if x = 0 then a :: move_piece( a, xs )
else x :: move_piece( a, xs )
(* 同一局面のチェック：線形探索 *)
fun check_same_state( state, ~1 ) = ~1
| check_same_state( state, n ) =
if Array.sub( state_table, n ) = state
then n
else check_same_state( state, n - 1 )
(* int list の表示 *)
fun print_intlist( nil ) = print( "\n" )
| print_intlist( x::xs ) =
( print( Int.toString(x) ^ " " ); print_intlist( xs ) )
(* 手順を表示する *)
fun print_answer_forward( n ) = (
if n > 0 then print_answer_forward( Array.sub( prev_table, n ) ) else ();
print_intlist( Array.sub( state_table, n ) ) )
fun print_answer_backward( ~1 ) = ()
| print_answer_backward( n ) = (
print_intlist( Array.sub( state_table, n ) );
print_answer_backward( Array.sub( prev_table, n ) ))
fun print_answer( n, m ) =
if Array.sub( dir_table, n ) = Forward
then (print_answer_forward( n ); print_answer_backward( m ))
else (print_answer_forward( m ); print_answer_backward( n ))
(* 新しい局面を作る *)
fun make_new_state( rear, front, nil ) = rear
| make_new_state( rear, front, x::xs ) =
let
val state = Array.sub( state_table, front )
val new_state = move_piece( List.nth( state, x ), state )
val dir = Array.sub( dir_table, front )
val pos = check_same_state( new_state, rear - 1 )
in
if pos <> ~1
then
if Array.sub( dir_table, pos ) <> dir
then (print_answer( front, pos ); raise Exit)
else make_new_state( rear, front, xs )
else (
Array.update( state_table, rear, new_state );
Array.update( prev_table, rear, front );
Array.update( dir_table, rear, dir );
Array.update( space_table, rear, x );
make_new_state( rear + 1, front, xs )
)
end
(* 幅優先探索 *)
fun solve_b( front, rear ) =
if front = rear then ()
else solve_b( front + 1,
make_new_state( rear, front,
List.nth( adjacent, Array.sub( space_table, front ))))
fun solve(start, goal) = (
(* start *)
Array.update( state_table, 0, start );
Array.update( prev_table, 0, ~1 );
Array.update( dir_table, 0, Forward );
Array.update( space_table, 0, position_if( fn(x) => x = 0, start ) );
(* goal *)
Array.update( state_table, 1, goal );
Array.update( prev_table, 1, ~1 );
Array.update( dir_table, 1, Backward );
Array.update( space_table, 1, position_if( fn(x) => x = 0, goal ) );
(* 探索 *)
solve_b( 0, 2 ) handle Exit => ()
)
fun solve_exe() =
let
val a = Timer.startRealTimer()
in
solve([1, 5, 2, 6, 3, 4, 0], [1, 2, 3, 4, 5, 6, 0]);
Timer.checkRealTimer( a )
end