経路の探索
今回は、地図上の A 地点から B 地点までの道順を求める、といった「経路の探索」と呼ばれる問題を取り上げます。「探索」にはいろいろな種類があります。拙作のページ バックトラック法 で取り上げた「８クイーン」のようなパズルの解法も、あらゆる可能性の中から正解に行き着く手順を探すことですから、探索の一つと考えることができます。そして、探索でよく用いられる最も基本的な方法が「バックトラック法」なのです。もちろん、経路の探索もバックトラック法で解くことができます。
●グラフ
まず最初に「グラフ (graph)」というデータ構造を説明します。一般にグラフというと、 円グラフや折れ線グラフといった図表を思い出す人が多いと思います。数学の「グラフ理論」では、いくつかの点とそれを結ぶ線でできた図形を「グラフ」といいます。次の図を見てください。
図 1 : グラフの例
図 1 に示すように、グラフは点とそれを接続する線から構成されています。点のことを「頂点 (vertex)」や「節点 (node)」と呼び、線のことを「辺 (edge)」や「弧 (arc)」と呼びます。また、グラフには 2 種類あって、辺に向きの無いグラフを「無向グラフ」といい、辺に向きがあるグラフを「有向グラフ」といいます。有向グラフは一方通行の道と考えればいいでしょう。 次の図を見てください。
図 2 : 有向グラフと無向グラフ
たとえば、図 2 (1) では A 地点から B 地点へ行くことができますが、一方通行のため B 地点から A 地点に戻ることはできません。これが有効グラフです。(2) の無効グラフでは、A 地点から B 地点へ行くことができるし、逆に B 地点から A 地点に戻ることもできます。
データ間のさまざまな関係を表す場合、グラフはとても役に立ちます。たとえば、下図のように経路をグラフで表すことができます。
図 3 : 経路図
図 3 ではアルファベットで頂点を表しています。この例では経路をグラフで表していますが、このほかにもいろいろな問題をグラフで表現することができます。
●隣接行列と隣接リスト
グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行列で表すことができます。図 3 の経路図を隣接行列で表すと次のようになります。
│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 図 4 : 隣接行列
A に接続している頂点は B と C なので、A 行の B と C に 1 をセットし、接続していない頂点には 0 をセットします。経路が一方通行ではない無向グラフの場合は、A 列の B と C にも 1 がセットされます。これを OCaml でプログラムすると、次のようになります。
リスト 1 : 隣接行列 let adjacent = [| [|0; 1; 1; 0; 0; 0; 0|]; (* A *) [|1; 0; 1; 1; 0; 0; 0|]; (* B *) [|1; 1; 0; 0; 1; 0; 0|]; (* C *) [|0; 1; 0; 0; 1; 1; 0|]; (* D *) [|0; 0; 1; 1; 0; 0; 1|]; (* E *) [|0; 0; 0; 1; 0; 0; 0|]; (* F *) [|0; 0; 0; 0; 1; 0; 0|]; (* G *) |]
頂点 A から G を数値 0 から 6 に対応させるところがポイントです。隣接行列は 2 次元配列 (OCaml では配列の配列) で表します。
隣接行列の欠点は、辺の数が少ない場合でも 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) 図 5 : 隣接リスト
これを OCaml でプログラムすると次のようになります。
リスト 2 : 隣接リスト let 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 に対応させます。この例では隣接リストを int list list で表しましたが、配列にリストを格納してもかまいません。この場合、データ型は int list array になります。
ところで、隣接リストにも欠点があります。たとえば、E と G が接続しているか調べるには、データを順番に調べていくしか方法がありません。このため、接続の判定に時間がかかることがあるのです。まあ、頂点に接続されている辺の数が少なければ、処理速度が極端に遅くなることはないでしょう。
●バックトラックによる探索
それでは隣接リストを使って、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]
逆順で管理する
図 6 : 経路の表し方
リストの最後尾にデータを追加するのは面倒なので、経路は上図のように逆順で管理することにします。プログラムは次のようになります。
リスト 3 : 深さ優先探索
(* 経路の表示 *)
let print_path path =
List.iter (fun x -> print_int x; print_string " ") path;
print_newline ()
(* 深さ優先探索 *)
let depth_first_search start goal =
let rec dfs path =
let p = List.hd path in
if p = goal then print_path (List.rev path)
else List.iter (fun x -> if not (List.mem x path) then dfs (x::path))
(List.nth adjacent p)
in
dfs [start]
関数 depth_first_search は start から goal までの経路を求めます。実際の処理は局所関数 dfs で行います。引数 path が経路を表します。最初に、path の先頭から現在地点 p を取り出します。そして、p がゴール goal かチェックします。これが再帰呼び出しの停止条件になります。ゴールに到達したら print_path で経路を表示します。ここで探索を終了することもできますが、バックトラックすることで全ての経路を見つけることができます。
ゴールに到達していない場合、隣接リストから次の頂点を選びます。関数 List.nth はリストから n 番目の要素を取り出します。nth はモジュール List に定義されている関数です。
List.nth : 'a list -> int -> 'a = <fun>
nth の場合、リストの先頭要素が 0 番目になります。簡単な使用例を示します。
# List.nth [1; 2; 3] 0;; - : int = 1 # List.nth [1; 2; 3] 2;; - : int = 3
頂点 p の隣接リストを nth で取り出します。そして、関数 List.iter でリストの要素を順番に取り出して、匿名関数の中で dfs を再帰呼び出しします。このとき、経路に含まれている頂点を選んではいけません。そうしないと、同じ道をぐるぐると回る巡回経路が発生し、ゴールまでたどり着くことができなくなります。このチェックを関数 List.mem で行います。経路 path の中に頂点 x がないことを確認してから、path に x を追加して dfs を再帰呼び出しします。
実行結果は次のようになります。
# depth_first_search 0 6;; 0 1 2 4 6 0 1 3 4 6 0 2 1 3 4 6 0 2 4 6 - : unit = ()
4 通りの経路を見つけることができました。バックトラックによる探索は、経路を先へ先へ進めるので、「縦形探索」とか「深さ優先探索」と呼ばれています。このため、結果を見てもわかるように、最初に見つかる経路が最短経路とは限りません。最短経路を求めるのに適したアルゴリズムが「幅優先探索」です。
●幅優先探索
バックトラックによる探索は「深さ優先探索」や「縦形探索」とも呼ばれるように、一つの経路を先へ先へと進めていきます。このため最初に見つかる経路が最短経路であるとは限りません。幅優先探索は全ての経路について平行に探索を進めていくため、最初に見つかる経路が最短経路となります。それでは、同じ経路図を使って幅優先探索を具体的に説明しましょう。
幅優先探索の様子を下図に示します。
図 7 : 幅優先探索
まず、出発点 A から一つ進んだ経路 (2 節点) を全て求めます。この場合は、[A; B] と [A; C] の 2 つあり、これを全て記憶しておきます。次に、これらの経路から一つ進めた経路 (3 節点) を全て求めます。経路 [A; B] は [A; B; C] と [A; B; D] へ進めることができますね。ほかの経路 [A; C] も同様に進めて、全ての経路を記憶します。あとはこの作業をゴールに達するまで繰り返せばいいのです。
上図では、4 節点の経路 [A; C; E; G] でゴールに達していることがわかります。このように幅優先探索では、最初に見つかった経路が最短距離 (または最小手数) となるのです。この性質は、全ての経路を平行に進めていく探索順序から考えれば当然のことといえるでしょう。このことからバックトラックの縦形探索に対して、幅優先探索は「横形探索」と呼ばれます。このあとも探索を繰り返せば全ての経路を求めることができます。
完成までの最小手数を求めるパズルを解く場合、幅優先探索を使ってみるといいでしょう。ただし、探索を進めるにしたがって、記憶しておかなければならないデータの総数が爆発的に増加する、つまりメモリを大量消費することに注意してください。
図 7 の場合ではメモリを大量消費することはありませんが、問題によってはマシンに搭載されているメモリが不足するため、幅優先探索を実行できない場合もあるでしょう。したがって、幅優先探索を使う場合は、メモリの消費量を抑える工夫も必要になります。
●経路の管理
経路の管理はキューを使うと簡単です。幅優先探索でのキューの動作を下図に示します。
図 8 : 幅優先探索とキューの動作
最初は、(1) のように出発点をキューにセットしておきます。次に、キューから経路を取り出し、(2) のように経路 [A] を一つ進めて、経路 [A; B] [A; C] を作り、それをキューに追加します。(3) では、経路 [A; B] を取り出して、一つ進めた経路 [A; B; C] と [A; B; D] をキューに追加します。あとはキューに経路がある間、探索処理を繰り返します。
キューは先入れ先出し (FIFO) の性質を持つデータ構造です。距離の短い経路から順番に処理されるため、幅優先探索として機能するわけです。
●幅優先探索のプログラム
それではプログラムを作りましょう。キューは OCaml の標準モジュール Queue を使います。プログラムは次のようになります。
リスト 4 : 幅優先探索
let breadth_first_search start goal =
let q = Queue.create () in
Queue.add [start] q;
while not (Queue.is_empty q) do
let path = Queue.take q in
let p = List.hd path in
if p = goal then print_path (List.rev path)
else List.iter (fun x -> if not (List.mem x path) then Queue.add (x::path) q)
(List.nth adjacent p)
done
最初に Queue.create で空のキューを生成し、変数 q にセットします。次に、関数 add でスタート地点の経路 [start] をキューに格納します。あとは、キューに経路がある間、while ループで探索を行います。
関数 take でキューから経路を取り出して path にセットします。そして、関数 hd でキューの先頭要素を求め、それを変数 p にセットします。p が goal と等しければ print_path で経路を表示します。
そうでなければ、経路を一つ進めます。この処理は深さ優先探索とほぼ同じですが、新しい経路を関数 add でキューに追加していくところが異なります。これで全ての経路を求めることができます。
それでは、実際に実行してみましょう。
# breadth_first_search 0 6;; 0 2 4 6 0 1 2 4 6 0 1 3 4 6 0 2 1 3 4 6 - : unit = ()
結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる経路が最長となります。当然ですが、経路の総数は 4 通りとなります。
ところで、幅優先探索は再帰定義でもプログラムすることができます。たとえば、拙作のページ モジュール で作成したキュー (Myqueue) は、参照型変数 (または mutable のレコード) を使っていません。このようなキューを用いる場合、キューを参照変数に格納するか、再帰定義でプログラムすることになります。この場合、再帰定義を使った方が関数型言語らしいプログラムになると思います。
プログラムは次のようになります。
リスト 5 : 幅優先探索 (2)
let breadth_first_search start goal =
let rec bfs q =
if Queue.is_empty q then ()
else
let path = Queue.top q in
let p = List.hd path in
if p = goal then print_path (List.rev path) else ();
bfs (List.fold_left
(fun q1 x -> if List.mem x path then q1
else Queue.enqueue (x::path) q1)
(Queue.dequeue q)
(List.nth adjacent p))
in
let q = Queue.create in
bfs goal (Queue.enqueue [start] q)
このプログラムのポイントは、新しい経路をキューに追加する処理を fold_left で行っているところです。fold_left に渡す初期値は、先頭の経路を取り除いたキューです。fold_left の場合、匿名関数の第 1 引数 q1 にキューが渡されるので、巡回経路にならなければ、新しい経路を追加したキューを返し、そうでなければ q1 をそのまま返します。これで、fold_left の返り値は新しい経路を追加したキューになります。あとは、その値を bfs に渡して再帰呼び出しするだけです。結果は同じなので省略します。
●探索の一般化
深さ優先探索と幅優先探索は、高階関数を使うと一般化することができます。次のリストを見てください。
リスト 6 : 探索の一般化
(* 探索 *)
let rec search func is_goal next_state combine = function
[] -> ()
| x::xs ->
if is_goal x then func x else ();
search
func is_goal next_state combine
(combine (next_state x) xs)
(* 深さ優先探索 *)
let depth_first_search func is_goal next_state ls =
search func is_goal next_state (@) ls
(* 幅優先探索 *)
let breadth_first_search func is_goal next_state ls =
search func is_goal next_state (fun x y -> y @ x) ls
関数 search はまだ調べていない局面 (state) を格納したリスト (state_list) を受け取り、その先頭から局面を取り出して新しい局面を生成することで探索を進めます。引数 func はゴールに到達したときに適用する関数、is_goal はゴールに到達したか調べる述語、next_state は現在の局面から新しい局面を生成してリストに格納して返す関数、combine は新しく生成した局面を state_list に連結する関数、最後の引数が state_list です。
最初に、state_list が空リストであれば探索を終了します。次に、先頭の局面 x を取り出して、ゴールに到達しているか is_goal でチェックします。is_goal が true であれば func x を評価し、そうでなければ何もしません。それから、search を再帰呼び出しします。このとき、x に next_state を適用して新しい局面を生成し、combine で xs に追加します。チェックした局面 x は state_list から取り除くことに注意してください。
もしも、解を一つ見つけるだけでよければ、if 文の else 節で search を評価してください。解を見つけたところで再帰呼び出しが停止するので探索を終了することができます。
深さ優先探索は経路を先へ先へと進めていく探索なので、state_list の先頭に新しい局面を追加することで実現できます。combine にはリストを連結する関数を渡します。演算子 @ をカッコで囲めばカリー化関数として渡すことができます。幅優先探索はすべての経路を並行に探索していくので、state_list の末尾に新しい局面を追加することで実現できます。combine には (fun x y -> y @ x) を渡します。
実際に関数を定義すると、次のように表示されます。
val search :
('a -> unit) ->
('a -> bool) -> ('a -> 'b) -> ('b -> 'a list -> 'a list) -> 'a list -> unit
val depth_first_search :
('a -> unit) -> ('a -> bool) -> ('a -> 'a list) -> 'a list -> unit
val breadth_first_search :
('a -> unit) -> ('a -> bool) -> ('a -> 'a list) -> 'a list -> unit
局面を表すデータ型を定義していませんが、OCaml の多相性によりプログラムをコンパイルすることができます。
それでは、実際に経路の探索を行ってみましょう。次のリストを見てください。
リスト 7 : 経路の探索 (keiro2.ml)
(* 新しい状態を作成する *)
let next_state path =
let p = List.hd path in
List.fold_left
(fun x y -> if List.mem y path then x else (y::path)::x)
[]
(List.nth adjacent p)
let () =
print_string "depth_first_search\n";
depth_first_search print_path (fun x -> (List.hd x) = 6) next_state [[0]];
print_string "breadth_first_search\n";
breadth_first_search print_path (fun x -> (List.hd x) = 6) next_state [[0]];
関数 next_state は畳み込み関数を使うと簡単です。引数 path は経路を表します。先頭の地点を取り出して変数 p にセットします。あとは fold_letf で生成した新しい経路をリストに格納していくだけです。ゴールのチェックは匿名関数で定義しました。state_list のデータ型は int list list になることに注意してください。
それでは実行結果を示します。
$ ocaml keiro2.ml depth_first_search 0 2 4 6 0 2 1 3 4 6 0 1 3 4 6 0 1 2 4 6 bread_first_search 0 2 4 6 0 1 3 4 6 0 1 2 4 6 0 2 1 3 4 6
深さ優先探索は、今までと経路を探索する順番が異なるため、たまたま最初に最短経路が表示されました。それ以外は今までと同じ結果になります。
●反復深化
幅優先探索は最短手数を求めるのに適したアルゴリズムですが、生成する局面数が多くなると大量のメモリを必要とします。このため、メモリが不足するときは、幅優先探索を使うことができません。深さ優先探索の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らないという問題点があります。
それでは、大量のメモリを使わずに最短手数を求める方法はないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限値を設定し、解が見つかるまで上限値を段階的に増やしていく、という方法です。
たとえば、1 手で解が見つからない場合は、2 手までを探索し、それでも見つからない場合は 3 手までを探索する、というように制限値を 1 手ずつ増やしていくわけです。このアルゴリズムを「反復深化 (iterative deeping)」といいます。
反復深化は最短手数を求めることができるアルゴリズムですが、幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。ただし、同じ探索を何度も繰り返すため実行時間が増大するという欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。
●反復深化のプログラム
それでは、同じ経路図を使って反復深化を具体的に説明しましょう。反復深化のプログラムはとても簡単です。設定した上限値まで深さ優先探索を行う関数を作り、上限値を１手ずつ増やしてその関数を呼び出せばいいのです。プログラムは次のようになります。
リスト 8 : 反復深化
let rec ids goal path limit =
let p = List.hd path in
if List.length path = limit then
if p = goal then print_path (List.rev path) else ()
else
List.iter (fun x -> if not (List.mem x path) then ids goal (x::path) limit)
(List.nth adjacent p)
let id_search start goal =
for limit = 1 to 7 do
Printf.printf "----- move %d -----\n" (limit - 1);
ids goal [start] limit
done
関数 ids の引数 limit が上限値を表します。経路の長さが上限値 limit に達したら探索を打ち切ります。このとき、ゴールに到達したかチェックします。あとは、limit の値を増やしながら ids を呼び出せばいいわけです。それでは実行結果を示しましょう。
# id_search 0 6;; ----- move 0 ----- ----- move 1 ----- ----- move 2 ----- ----- move 3 ----- 0 2 4 6 ----- move 4 ----- 0 1 2 4 6 0 1 3 4 6 ----- move 5 ----- 0 2 1 3 4 6 ----- move 6 ----- - : unit = ()
結果を見ればおわかりのように、最初に見つかる解が最短手数になります。このプログラムでは全ての経路を求めましたが、最短手数を求めるだけでよい場合は、解が見つかった時点で探索を終了すればいいでしょう。
●プログラムリスト１
リスト : 経路の探索
(* キュー Myqueue の定義 *)
module Myqueue:
sig
exception Empty
type 'a queue
val create : 'a queue
val enqueue : 'a -> 'a queue -> 'a queue
val dequeue : 'a queue -> 'a queue
val top : 'a queue -> 'a
val is_empty : 'a queue -> bool
end
= struct
(* 例外 *)
exception Empty
(* データ型の定義 *)
type 'a queue = Q of 'a list * 'a list
(* 空のキューを返す *)
let create = Q ([], [])
(* データの挿入 *)
let enqueue a = function Q (front, rear) -> Q (front, a::rear)
(* データの削除 *)
let rec dequeue = function
Q ([], []) -> raise Empty
| Q ([], rear) -> dequeue (Q (List.rev rear, []))
| Q (x::front, rear) -> Q (front, rear)
(* 先頭のデータを取得 *)
let rec top = function
Q ([], []) -> raise Empty
| Q ([], rear) -> top (Q (List.rev rear, []))
| Q (x::_, _) -> x
(* キューは空か *)
let is_empty q = q = create
end
(* 隣接リスト *)
let adjacent = [
[1; 2]; (* A *)
[0; 2; 3]; (* B *)
[0; 1; 4]; (* C *)
[1; 4; 5]; (* D *)
[2; 3; 6]; (* E *)
[3]; (* F *)
[4]] (* G *)
(* 経路の表示 *)
let print_path path =
List.iter (fun x -> print_int x; print_string " ") path;
print_newline ()
(* 深さ優先探索 *)
let depth_first_search start goal =
let rec dfs path =
let p = List.hd path in
if p = goal then print_path (List.rev path)
else List.iter (fun x -> if not (List.mem x path) then dfs (x::path))
(List.nth adjacent p)
in
dfs [start]
(* 幅優先探索 *)
let breadth_first_search start goal =
let q = Queue.create () in
Queue.add [start] q;
while not (Queue.is_empty q) do
let path = Queue.take q in
let p = List.hd path in
if p = goal then print_path (List.rev path)
else List.iter (fun x -> if not (List.mem x path) then Queue.add (x::path) q)
(List.nth adjacent p)
done
(* Myqueue を使う場合 *)
let breadth_first_search2 start goal =
let rec bfs q =
if Myqueue.is_empty q then ()
else
let path = Myqueue.top q in
let p = List.hd path in
if p = goal then print_path (List.rev path) else ();
bfs (List.fold_left
(fun q1 x -> if List.mem x path then q1
else Myqueue.enqueue (x::path) q1)
(Myqueue.dequeue q)
(List.nth adjacent p))
in
let q = Myqueue.create in
bfs (Myqueue.enqueue [start] q)
(* 反復深化 *)
let rec ids goal path limit =
let p = List.hd path in
if List.length path = limit then
if p = goal then print_path (List.rev path) else ()
else
List.iter (fun x -> if not (List.mem x path) then ids goal (x::path) limit)
(List.nth adjacent p)
let id_search start goal =
for limit = 1 to 7 do
Printf.printf "----- move %d -----\n" (limit - 1);
ids goal [start] limit
done
●プログラムリスト２
リスト : 探索の一般化
(* 隣接リスト *)
let adjacent = [
[1; 2]; (* A *)
[0; 2; 3]; (* B *)
[0; 1; 4]; (* C *)
[1; 4; 5]; (* D *)
[2; 3; 6]; (* E *)
[3]; (* F *)
[4]] (* G *)
(* 経路の表示 *)
let print_path path =
List.iter (fun x -> print_int x; print_string " ") path;
print_newline ()
(* 探索 *)
let rec search func is_goal next_state combine = function
[] -> ()
| x::xs ->
if is_goal x then func x else ();
search
func is_goal next_state combine
(combine (next_state x) xs)
(* 深さ優先探索 *)
let depth_first_search func is_goal next_state ls =
search func is_goal next_state (@) ls
(* 幅優先探索 *)
let breadth_first_search func is_goal next_state ls =
search func is_goal next_state (fun x y -> y @ x) ls
(* 新しい状態を作成する *)
let next_state path =
let p = List.hd path in
List.fold_left
(fun x y -> if List.mem y path then x else (y::path)::x)
[]
(List.nth adjacent p)
let () =
print_string "depth_first_search\n";
depth_first_search print_path (fun x -> (List.hd x) = 6) next_state [[0]];
print_string "breadth_first_search\n";
breadth_first_search print_path (fun x -> (List.hd x) = 6) next_state [[0]];