今回は、地図上の A 地点から B 地点までの道順を求める、といった「経路の探索」と呼ばれる問題を取り上げます。「探索」にはいろいろな種類があります。「ちょっと寄り道」で取り上げた 8 クイーン のようなパズルの解法も、あらゆる可能性の中から正解に行き着く手順を探すことですから、探索の一つと考えることができます。そして、探索でよく用いられる最も基本的な方法が「バックトラック」なのです。もちろん、経路の探索もバックトラックで解くことができます。
このほかに、もう一つ基本的な方法として「幅優先探索」があります。バックトラックの場合、失敗したら後戻りして別の道を選び直しますが、幅優先探索の場合は、全ての経路について並行に探索を進めていきます。今回は、この 2 つの方法で問題を解いてみましょう。
簡単な例題として、次に示す経路を考えてみます。
Ｂ------Ｄ------Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ------Ｅ------Ｇ
図 :経路図
点とそれを接続する線からなる図形を「グラフ (graph) 」といいます。点のことを「頂点 (vertex) 」とか「節 (node) 」と呼び、線のことを「辺 (edge) 」とか「弧 (arc) 」と呼びます。グラフには 2 種類あって、辺に向きがないものを「無向グラフ」といい、向きがあるものを「有向グラフ」といいます。有向グラフは一方通行の道と考えるとわかりやすいでしょう。上図ではアルファベットで頂点を表しています。今回は経路をグラフで表していますが、このほかにもいろいろな問題をグラフで表現することができます。
グラフをプログラムする場合、よく使われる方法が「隣接行列」と「隣接リスト」です。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行列で表すことができます。上図を隣接行列で表すと、次のようになります。
| A B C D E F G
-+--------------
A| 0 1 1 0 0 0 0
B| 1 0 1 1 0 0 0
C| 1 1 0 0 1 0 0
D| 0 1 0 0 1 1 0
E| 0 0 1 1 0 0 1
F| 0 0 0 1 0 0 0
G| 0 0 0 0 1 0 0
図 :隣接行列
A に接続している頂点は B と C なので、A 行の B と C に 1 をセットし、接続していない頂点には 0 をセットします。経路が一方通行ではない無向グラフの場合は、A 列の B と C にも 1 がセットされます。
隣接行列の欠点は、辺の数が少ない場合でも N 行 N 列の行列が必要になることです。つまり、ほとんどの要素が 0 になってしまい、メモリを浪費してしまうのです。この欠点を補う方法に隣接リストがあります。これは、つながっている頂点を格納する方法です。次の図を見てください。
A => [B, C] B => [A, C, D] C => [A, B, E] D => [B, E, F] E => [C, D, G] F => [D] G => [E] 図 : 隣接リスト
上図は、頂点とそこに接続されている頂点を => と [ ] で表しています。これを SML/NJ で表すと、次のようになります。
リスト : 隣接リスト (1) val adjacent = [ [1, 2], (* A *) [0, 2, 3], (* B *) [0, 1, 4], (* C *) [1, 4, 5], (* D *) [2, 3, 6], (* E *) [3], (* F *) [4]]; (* G *) };
リスト : 隣接リスト (2) val adjacent = #[ #[1, 2], (* A *) #[0, 2, 3], (* B *) #[0, 1, 4], (* C *) #[1, 4, 5], (* D *) #[2, 3, 6], (* E *) #[3], (* F *) #[4]]; (* G *) };
頂点 A から G を数値 0 から 6 に対応させるところがポイントです。すると、隣接リスト adjacent は int list list で表すことができます。リストのほかに、「ベクタ (vector) 」を使うこともできます。SML/NJ のベクタは、値を書き換えることができない 1 次元配列のことです。ベクタは #[ ... ] で生成することができます。次の例を見てください。
- #[1, 2, 3]; val it = #[1,2,3] : int vector - #[[1, 2], [3, 4, 5]]; val it = #[[1,2],[3,4,5]] : int list vector - #[#[1, 2], #[3, 4, 5]]; val it = #[#[1,2],#[3,4,5]] : int vector vector
ベクタは配列と同様に多相的なデータなので、型は 'a vector で表されます。int を格納するベクタは int vecotor になり、int list を格納するベクタは int list vector になります。もちろん、int vector を格納することもできます。その場合は int vector vector になります。隣接リスト (2) は int vector vector で隣接リストを表しています。
ベクタの操作関数はストラクチャ Vector に定義されています。ベクタの操作は配列とほとんど同じです。ただし、値を書き換える操作はありません。ベクタの要素は配列と同様に関数 sub で取り出すことができますが、ベクタの要素を書き換える関数 update はありません。
ところで、隣接リストにも欠点があります。たとえば、E と G が接続しているか調べるには、
データを順番に調べていくしか方法がありません。このため、接続の判定に時間がかかることがあるのです。まあ、頂点に接続されている辺の数が少なければ、処理速度が極端に遅くなることはないでしょう。今回は隣接リスト (1) を使って、A から G までの経路をバックトラックで求めます。バックトラックを再帰呼び出しで実現する場合、経路を「進む」ことを再帰呼び出しに対応させるのがポイントです。たとえば、経路を探索する関数を search としましょう。search は引数として現在地点の頂点を受け取ることにします。最初は search(A) と呼び出します。そして、A から B へ進むには search(B) と呼び出します。これで B へ進むことができます。
それでは、A に戻るにはどうしたらいいのでしょう。search(B) は search(A) から呼び出されたので、search(B) の実行を終了すれば、呼び出し元である search(A) に戻ることができます。つまり、関数の実行を終了すれば、一つ手前の地点にバックトラックできるのです。このように再帰呼び出しを使うと、進むことと戻ることを関数呼び出しで簡単に実現することができます。
それでは具体的に説明しましょう。経路はリストに頂点を格納して表すことにします。次の図を見てください。
A - B - D ─→ [0, 1. 3] ==> [3, 1, 0]
A - B - C - E ─→ [0, 1, 2, 4] ==> [4, 2, 1, 0]
逆順で管理する
図 : 経路の表し方
リストの最後尾にデータを追加するのは面倒なので、経路は上図のように逆順で管理することにします。
経路の探索を行う関数 search は、次のように定義します。
val search = fn : int * int list -> unit
search の第 1 引数がゴール、第 2 引数が経路を表すリストです。リストの先頭要素が現在地点の頂点になります。search は現在地点に隣接している頂点を一つ選び、経路を進めていきます。A から Gまでの経路を求めるには、次のように呼び出します。
(* A から G までの経路を求める *) search( 6, [0] );
search は出発点 A をリストにセットし、A に接続されている頂点を選びます。隣接リストから順番に選ぶことにすると、次の頂点は B となります。B へ進むためには、次のように search を再帰呼び出しします。
(* B へ進む時の再帰呼び出し *) search( 6, [1, 0] );
この関数の実行を終了すると、呼び出し元の関数である頂点 A の処理に戻ります。プログラムは次のようになります。
リスト : 深さ優先探索
fun print_intlist( nil ) = print( "\n" )
| print_intlist( x::xs ) =
( print( Int.toString(x) ^ " " ); print_intlist( xs ) )
fun check( x, nil ) = true
| check( x, y::ys ) = if x = y then false else check( x, ys )
fun search( goal, path as x::xs ) =
if x = goal
then print_intlist( rev path )
else app (fn(y) => if check( y, path ) then search( goal, y::path ) else ())
(List.nth( adjacent, x ));
fun solve() = search( 6, [0] );
関数 search を見てください。最初に、現在地点 x がゴール goal かチェックします。これが再帰呼び出しの停止条件になります。ゴールしたら print_intlist で経路を表示します。ここで探索を終了することもできますが、バックトラックすることで全ての経路を見つけることができます。パズルを解く場合、解の総数を求めることが多いので、全ての解をもれなく探索する必要があります。バックトラックを使えば、このような要求も満たすことができます。
ゴールしていない場合は、隣接リストから次の頂点を選びます。関数 nth はリストから n 番目の要素を取り出します。nth はストラクチャ List に定義されている関数です。
nth list n
nth の場合、リストの先頭要素が 0 番目になります。簡単な使用例を示します。
- val a = [1, 2, 3]; val a = [1,2,3] : int list - List.nth( a, 0 ); val it = 1 : int - List.nth( a, 2 ); val it = 3 : int
頂点 x の隣接リストを nth で取り出します。そして、関数 app でリストの要素を順番に取り出して、匿名関数の中で search を再帰呼び出しします。このとき、経路に含まれている頂点を選んではいけません。そうしないと、同じ道をぐるぐると回る巡回経路が発生し、ゴールまでたどり着くことができなくなります。このチェックを関数 check で行います。経路 path の中に頂点 y がないことを確認してから、経路に y を追加して search を再帰呼び出しします。
実行結果は次のようになります。
- solve(); 0 1 2 4 6 0 1 3 4 6 0 2 1 3 4 6 0 2 4 6 val it = () : unit
4 通りの経路を見つけることができました。バックトラックによる探索は、経路を先へ先へ進めるので、「縦形探索」とか「深さ優先探索」と呼ばれています。このため、結果を見てもわかるように、最初に見つかる経路が最短経路とは限りません。最短経路を求めるのに適したアルゴリズムが「幅優先探索」です。
バックトラックによる探索は「深さ優先探索」や「縦形探索」とも呼ばれるように、一つの経路を先へ先へと進めていきます。このため最初に見つかる経路が最短経路であるとは限りません。幅優先探索は全ての経路について平行に探索を進めていくため、最初に見つかる経路が最短経路となります。それでは、同じ経路図を使って幅優先探索を具体的に説明しましょう。
Ｂ------Ｄ------Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ------Ｅ------Ｇ
図 : 経路図
幅優先探索の様子を下図に示します。
[A] ─┬─ [A,B] ─┬─ [A,B,C] ・・・・
│ └─ [A,B,D] ─┬─ [A,B,D,F] 行き止まり
│ └─ [A,B,D,E]
└─ [A,C] ─┬─ [A,C,B] ・・・・
└─ [A,C,E] ─┬─ [A,C,E,G] GOAL
└─ [A,C,E,D]
（出発点） （２節点） （３節点） （４節点）
図 : 幅優先探索
まず、出発点 A から一つ進んだ経路 (2 節点) を全て求めます。この場合は、[A, B] と [A, C] の 2 つあり、これを全て記憶しておきます。次に、これらの経路から一つ進めた経路 (3 節点) を全て求めます。経路 [A, B] は [A, B, C] と [A, B, D] へ進めることができますね。ほかの経路 [A, C] も同様に進めて、全ての経路を記憶します。あとはこの作業をゴールに達するまで繰り返せばいいのです。
上図では、4 節点の経路 [A, C, E, G] でゴールに達していることがわかります。このように幅優先探索では、最初に見つかった経路が最短距離 (または最小手数) となるのです。この性質は、全ての経路を平行に進めていく探索順序から考えれば当然のことといえるでしょう。このことからバックトラックの縦形探索に対して、幅優先探索は「横形探索」と呼ばれます。このあとも探索を繰り返せば全ての経路を求めることができます。
完成までの最小手数を求めるパズルを解く場合、幅優先探索を使ってみるといいでしょう。ただし、探索を進めるにしたがって、記憶しておかなければならないデータの総数が爆発的に増加する、つまりメモリを大量消費することに注意してください。
上図の場合ではメモリを大量消費することはありませんが、問題によってはマシンに搭載されているメモリが不足するため、幅優先探索を実行できない場合もあるでしょう。したがって、幅優先探索を使う場合は、メモリの消費量を抑える工夫も必要になります。
経路の管理はキューを使うと簡単です。幅優先探索でのキューの動作を下図に示します。
(1) ───── QUEUE ──────
┌── [A]
│ ───────────────
│
└─→ キューからデータを取り出す
(2) ───── QUEUE ──────
←─┐
─────────────── │
│
[A] の経路を進め [A,B] ───┤
キューに追加する [A,C] ───┘
(3) ───── QUEUE ──────
┌── [A,B] [A,C] ←─┐
│ ─────────────── │
│ │
└─→ [A,B] の経路を進めキューに追加 │
[A,B,C] [A,B,D] ────────┘
(4) ───── QUEUE ──────
┌── [A,C] [A,B,C] [A,B,D] ←─┐
│ ─────────────── │
│ │
└─→ キューに経路がある間繰り返す ──┘
図 : 幅優先探索とキューの動作
最初は、(1) のように出発点をキューにセットしておきます。次に、キューから経路を取り出し、(2) のように経路 [A] を一つ進めて、経路 [A, B] [A, C] を作り、それをキューに追加します。(3) では、経路 [A, B] を取り出して、一つ進めた経路 [A, B, C] と [A, B, D] をキューに追加します。あとはキューに経路がある間、処理を繰り返せばいいわけです。
キューは先入れ先出し (FIFO) の性質を持つデータ構造です。距離の短い経路から順番に処理されるため、幅優先探索として機能するわけです。
それではプログラムを作りましょう。経路図は深さ優先探索と同じく隣接リスト (1) で表します。キューは モジュール (3) で作成したファンクタ makeQueue を使って生成します。プログラムは次のようになります。
リスト : 幅優先探索 (1)
(* ストラクチャの生成 *)
structure PathQueue = makeQueue( type item = int list )
open PathQueue
(* 探索 *)
fun search_b(goal) =
let
val q = ref create
val path = ref (nil : int list)
in
q := enqueue( !q, [0] );
while not( isEmpty( !q ) ) do (
path := front( !q );
q := dequeue( !q );
if goal = hd( !path ) then print_intlist( rev( !path ) )
else app (fn(y) => if check( y, !path )
then q := enqueue( !q, y::(!path) ) else ())
(List.nth(adjacent, hd( !path )))
)
end
最初にストラクチャ PathQueue をファンクタ makeQueue で生成します。makeQueue の引数は、経路のデータ型 int list を指定します。幅優先探索を行う関数が search_b です。幅優先探索は繰り返しを使うと簡単にプログラムできます。create で空のキューを生成して ref 変数 q にセットし、経路を格納する ref 変数 path を用意します。
次に、関数 enqueue でスタート地点の経路 [0] をキューに格納します。あとは、キューに経路がある間、while ループで探索を行います。関数 front でキューから経路を求めて path にセットし、関数 dequeue でキューから経路を削除します。関数 hd でキューの先頭要素を求め、それが goal と等しければ print_intlist で経路を表示します。
そうでなければ、経路を一つ進めます。この処理は深さ優先探索とほぼ同じですが、新しい経路を enqueu でキューに追加していくところが異なります。これで全ての経路を求めることができます。
それでは、実際に実行してみましょう。
- search_b( 6 ); 0 2 4 6 0 1 2 4 6 0 1 3 4 6 0 2 1 3 4 6 val it = () : unit 実行結果
結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる経路が最長となります。当然ですが、経路の総数は 4 通りとなります。
ちなみに、再帰定義で幅優先探索をプログラムすると次のようになります。
リスト : 幅優先探索 (2)
fun make_new_path( q, _, nil ) = q
| make_new_path( q, path, x::xs ) =
if check( x, path )
then make_new_path( enqueue( q, x::path ), path, xs )
else make_new_path( q, path, xs )
fun search_b1(goal, q) =
if isEmpty( q ) then ()
else
let
val path = front( q )
in
if goal = hd( path ) then print_intlist( rev path ) else ();
search_b1( goal, make_new_path(dequeue( q ), path, List.nth(adjacent, hd( path ))))
end
fun solve_b1() = search_b1( 6, enqueue( create, [0] ) )
こちらの方が関数型言語らしいプログラムかもしれません。ご参考までに。
幅優先探索は最短手数を求めるのに適したアルゴリズムですが、生成する局面数が多くなると大量のメモリを必要とします。このため、メモリが不足するときは、幅優先探索を使うことができません。深さ優先探索の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らないという問題点があります。
それでは、大量のメモリを使わずに最短手数を求める方法はないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限値を設定し、解が見つかるまで上限値を段階的に増やしていく、という方法です。
たとえば、1 手で解が見つからない場合は、2 手までを探索し、それでも見つからない場合は 3 手までを探索する、というように制限値を 1 手ずつ増やしていくわけです。このアルゴリズムを「反復深化 (iterative deeping)」といいます。
反復深化は、最短手数を求めることができるアルゴリズムですが、幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。ただし、同じ探索を何度も繰り返すため実行時間が増大するという欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。
それでは、同じ経路図を使って反復深化を具体的に説明しましょう。
Ｂ------Ｄ------Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ------Ｅ------Ｇ
図 : 経路図
反復深化のプログラムはとても簡単です。設定した上限値まで深さ優先探索を行う関数を作り、上限値を１手ずつ増やしてその関数を呼び出せばいいのです。プログラムは次のようになります。
リスト : 反復深化
fun search_id( n, limit, goal, path ) =
if n = limit
then if hd( path ) = goal then print_intlist( rev path ) else ()
else app (fn(x) => if check(x, path)
then search_id(n + 1, limit, goal, x::path) else ())
(List.nth( adjacent, hd( path ) ));
fun solve_id() =
let
val i = ref 1
in
while !i < 7 do (
print(Int.toString(!i) ^ " moves\n" );
search_id( 0, !i, 6, [0] );
i := !i + 1
)
end
関数 search_id の引数 limit が上限値を表します。関数 search_id は limit まで深さ優先探索を行います。引数 n が経路の長さを表し、これが上限値 limit に達したら探索を打ち切ります。このとき、ゴールに到達したかチェックします。あとは、関数 solve_id で limit の値を増やしながら search_id を呼び出せばいいわけです。それでは実行結果を示しましょう。
- solve_id(); 1 moves 2 moves 3 moves 0 2 4 6 4 moves 0 1 2 4 6 0 1 3 4 6 5 moves 0 2 1 3 4 6 6 moves val it = () : unit
結果を見ればおわかりのように、最初に見つかる解が最短手数になります。このプログラムでは全ての経路を求めましたが、最短手数を求めるだけでよい場合は、解が見つかった時点で探索を終了すればいいでしょう。
(*
* 経路の探索
*
* Copyright (C) 2005 Makoto Hiroi
*)
(* ファンクタの定義 *)
functor makeQueue( type item ) = struct
abstype 'a queue = Q of 'a list * 'a list with
exception EmptyQueue
val create = Q(nil: item list, nil: item list)
fun enqueue( Q(front, rear), x ) = Q(front, x::rear)
fun dequeue( Q(nil, nil) ) = raise EmptyQueue
| dequeue( Q(nil, rear) ) = dequeue( Q(rev rear, nil) )
| dequeue( Q(x::xs, rear) ) = Q(xs, rear)
fun front( Q(nil, nil) ) = raise EmptyQueue
| front( Q(nil, rear) ) = front( Q(rev rear, nil) )
| front( Q(x::xs, _) ) = x
fun isEmpty( Q(nil, nil) ) = true
| isEmpty( _ ) = false
end
end
(* ストラクチャの生成 *)
structure PathQueue = makeQueue( type item = int list )
open PathQueue
(* 隣接リスト *)
val adjacent = [
[1, 2], (* 0 *)
[0, 2, 3], (* 1 *)
[0, 1, 4], (* 2 *)
[1, 4, 5], (* 3 *)
[2, 3, 6], (* 4 *)
[3], (* 5 *)
[4]]; (* 6 *)
(* int list の表示 *)
fun print_intlist( nil ) = print( "\n" )
| print_intlist( x::xs ) =
( print( Int.toString(x) ^ " " ); print_intlist( xs ) )
(* 同じ頂点が含まれているか *)
fun check( x, nil ) = true
| check( x, y::ys ) = if x = y then false else check( x, ys );
(* 深さ優先探索 *)
fun search( goal, path as x::xs ) =
if x = goal
then print_intlist( rev path )
else app (fn(y) => if check(y, path) then search(goal, y::path) else ())
(List.nth( adjacent, x ));
(* 探索の実行 *)
fun solve() = search( 6, [0] );
(* 幅優先探索 *)
fun search_b(goal) =
let
val q = ref create
val path = ref (nil : int list)
in
q := enqueue( !q, [0] );
while not( isEmpty( !q ) ) do (
path := front( !q );
q := dequeue( !q );
if goal = hd( !path ) then print_intlist( rev( !path ) )
else app (fn(y) => if check( y, !path ) then q := enqueue( !q, y::(!path) ) else ())
(List.nth(adjacent, hd( !path )))
)
end
(* 繰り返しを使わない場合 *)
fun make_new_path( q, _, nil ) = q
| make_new_path( q, path, x::xs ) =
if check( x, path )
then make_new_path( enqueue( q, x::path ), path, xs )
else make_new_path( q, path, xs )
fun search_b1(goal, q) =
if isEmpty( q ) then ()
else
let
val path = front( q )
in
if goal = hd( path ) then print_intlist( rev path ) else ();
search_b1( goal, make_new_path(dequeue( q ), path, List.nth(adjacent, hd( path ))))
end
(* 探索の実行 *)
fun solve_b1() = search_b1( 6, enqueue( create, [0] ) )
(* 反復深化 *)
fun search_id( n, limit, goal, path ) =
if n = limit
then if hd( path ) = goal then print_intlist( rev path ) else ()
else app (fn(x) => if check(x, path)
then search_id(n + 1, limit, goal, x::path) else ())
(List.nth( adjacent, hd( path ) ));
(* 探索の実行 *)
fun solve_id() =
let
val i = ref 1
in
while !i < 7 do (
print(Int.toString(!i) ^ " moves\n" );
search_id( 0, !i, 6, [0] );
i := !i + 1
)
end
SML/NJ の場合、単純な繰り返しは「末尾再帰」で実現できますが、手続き型言語のように while と ref 変数を使って実現することもできます。そこで、どちらが速いか実際に試してみました。次のリストを見てください。
リスト : 末尾再帰と繰り返し
fun foo( 0, a ) = a
| foo( n, a ) = foo( n - 1, a + 1 )
fun bar( n, m ) =
let
val i = ref n
val a = ref m
in
while !i > 0 do (
a := !a + 1;
i := !i - 1
);
!a
end
fun solve_exe( f ) =
let
val a = Timer.startRealTimer()
in
f( 10000000, 0 );
Timer.checkRealTimer( a )
end
関数 foo と bar は 1 を n 回足し算します。n 回の繰り返しを関数 foo は末尾再帰で、関数 bar は while と ref 変数でプログラムしています。時間の計測は関数 solve_exe で行います。M.Hiroi のオンボロマシン (Windows 95, Pentium 166 MHz) で実行したところ、結果は次のようになりました。
foo : 1.48 [sec] bar : 2.96 [sec]
bar の実行時間は foo の 2 倍になりました。末尾再帰の方が高速ですね。この結果には M.Hiroi も驚きました。SML/NJ の場合、ref 変数の更新に時間がかかるのかもしれません。興味のある方は、ご自分の環境で試してみてください。