待ち行列 (キュー)
待ち行列といえば、チケットなどを買うとき窓口にできる長い列のことですが、プログラムの「待ち行列 (キュー)」もそれと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。一番後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。
図 : 待ち行列
このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造が「キュー (queue)」なのです。キューは「先入れ先出し (FIFO : first-in, first-out)」[*1] とも呼ばれます。Prolog の場合、差分リストを使ってキューを簡単に実現することができます。
[*1] キューと対になるデータ構造が「スタック (stack)」です。スタックは後ろから入れたデータから取り出されるので、後入れ先出し (LIFO : last-in, first-out) と呼ばれます。
●差分リストによるキューの実装
キューの基本的な操作は、データをキューに追加する enqueue と、キューからデータを取り出す dequeue があります。それから、キューにデータがあるか調べる述語 empty を作りましょう。
- enqueue(Item, Queue, NewQueue)
キュー Queue にデータ Item を追加する。 - dequeue(Item, Queue, NewQueue)
キュー Queue からデータ Item を取り出す。 - empty(Queue)
キューにデータがあれば成功、なければ失敗する。
Prolog の場合、マッチングした変数の値を書き換えることはできません。したがって、enqueue と dequeue のどちらの操作にしても、キューの新しい状態は NewQueue になることに注意してください。プログラムは次のようになります。
リスト : キューの操作 enqueue(Item, [Qh, [Item | Qt]], [Qh, Qt]). dequeue(Item, [[Item | Qh], Qt], [Qh, Qt]). empty([X, Y]) :- X == Y.
差分リストを使ってキューを表すので、キューが空の状態は [ Q, Q ] となります。これにデータ a を追加してみましょう。マッチングは次のように行われます。
enqueue(a, [ Q, Q ], NewQ). [ Q, Q ] = [ Qh, [ a | Qt ] ] NewQ = [Qh, Qt] Q = Qh Q = [ a | Qt ] => Qh = [ a | Qt ] NewQ = [ [ a | Qt ], Qt ]
差分リスト [ Q , Q ] の場合、Q は自由変数であることに注意してください。Q と Qh はお互い自由変数なのでマッチングに成功しますが、Q と [ a | Qt ] もマッチングに成功するのです。したがって、Qh は [ a | Qt ] となり、NewQ は [ [ a | Qt ] , Qt ] になります。これで、空のキュー（差分リスト [ Q , Q ] ）に a が追加されました。
続いて、このキューにデータ b を追加しましょう。マッチングは次のように行われます。
enqueue(b, [ [ a | Q ], Q ], NewQ). [ [ a | Q ], Q ] = [ Qh, [ b | Qt ] ] NewQ = [Qh, Qt] [ a | Q ] = Qh Q = [ b | Qt ] => Qh = [ a | [ b | Qt ] ] => [ a, b | Qt ] NewQ = [ [ a. b | Qt ], Qt ]
今度は [ a | Q ] と Qh がマッチングし、Q と [ b | Qt ] がマッチングします。したがって、Qh は [ a | [ b | Qt ] ] = [ a , b | Qt ] になり、NewQ は [ [ a , b | Qt ] , Qt ] となります。確かに、データ b がキューに追加されていますね。マジックのように思われるかもしれませんが、これが「差分リスト」の面白いところです。
データの追加に比べて、データの削除はとても簡単です。dequeue のマッチングは次のように行われます。
dequeue(X, [ [ a, b | Q ], Q ], NewQ). X = Item [ [ a, b | Q ], Q ] = [ [ Item | Qh ], Qt ] NewQ = [ Qh, Qt ] Item = a Qh = [ b | Q ] Qt = Q X = Item = a NewQ = [ [ b | Q ], Q ]
差分リストの先頭からデータを取り出せばいいわけですから、キューと [ [ Item | Qh ] , Qt ] をマッチングさせれば、Item に先頭データを取り出すことができます。この場合、[ a , b | Q ] とマッチングするので、Item の値は a になり、Qh は [ b | Q ] となります。したがって、NewQ の値はデータを取り出したあとのキューは、[ Qh , Qt ] = [ [ b | Q ] , Q ] になります。
empty も簡単です。キューが空の状態は [ Q, Q ] ですから、差分リストの要素を取り出して、同じ値であることを述語 == を使って確認すればいいわけです。
●キューと幅優先探索
それでは、キューを実際に使ってみましょう。経路図と各地点の隣接関係は、前回と同じプログラムを使います。プログラムリストを再度掲載します。
リスト : 隣接の定義 neighbor(a, b). neighbor(a, f). neighbor(a, e). neighbor(b, f). neighbor(b, c). neighbor(c, d). neighbor(c, g). neighbor(e, f). neighbor(e, h). neighbor(f, g). neighbor(f, i). neighbor(f, j). neighbor(g, j). neighbor(h, i). neighbor(i, j). neighbor(j, k). /* X の隣を求める */ next(X, Y) :- neighbor(X, Y). next(X, Y) :- neighbor(Y, X).
幅優先探索でのキューの動作は、次のようになります。
最初は、(1) のように出発点をキューにセットしておきます。次に、キューから経路を取り出し、(2) のように経路 [a] を一つ延ばして、経路 [a,b] [a,f] [a,e] を作り、それをキューに追加します。(3) では経路 [a,b] を取り出して、一つ延ばした経路 [a,b,c] と [a,b,f] をキューに追加します。
あとは、キューに経路がある間、処理を繰り返せばいいわけです。キューは先入れ先出し (FIFO) の性質を持つデータ構造なので、距離の短い経路から順番に処理されるため、幅優先探索として機能するのです。
●末尾再帰による実装
Prolog の場合、繰り返しは「末尾再帰」か「失敗駆動ループ」を使って実現します。最初に末尾再帰を使ってプログラムを作りましょう。幅優先探索を行う述語 breadth_first_search は次のようになります。
リスト : キューを使った幅優先探索
breadth_first_search(Goal, Q) :-
not(empty(Q)),
dequeue([Node | Path], Q, Q1),
findall(Next, next(Node, Next), NextList),
add_path(Goal, [Node | Path], NextList, Q1, Q2),
breadth_first_search(Goal, Q2).
Goal がゴール地点、Q がキューを表します。キューにはあらかじめ出発点 [a] を格納しておきます。まず、キューにデータがあるか empty で調べます。これが繰り返しの停止条件となります。そして、dequeue で経路を一つ取り出します。今回はわかりやすさを優先してキューの操作述語 empty, dequeue, enqueue を使いますが、キュー（差分リスト）を直接操作した方が実践的でしょう。
次に、集合述語 findall で Node に隣接している地点をすべて求めます。そして、add_path で経路を延ばしてキューに格納します。dequeu によりキューの状態は Q1 に変わっているので、add_path には Q1 を渡します。そして、新しい経路を追加したキューを Q2 で受け取ります。
最後に、breadth_search を再帰呼び出しします。このとき、キューには Q2 を渡すことをお間違えなく。breadth_search は末尾再帰になっているので、SWI-Prolog では末尾再帰最適化により繰り返しに変換されます。
次に add_path を作ります。これも再帰呼び出しを使います。
リスト : 経路を延ばしてキューに追加する
add_path(_, _, [], Q, Q).
add_path(Goal, Path, [Goal | Rest], Q, Qe) :-
reverse([Goal | Path], NewPath), write(NewPath), nl, !,
add_path(Goal, Path, Rest, Q, Qe).
add_path(Goal, Path, [Next | Rest], Q, Qe) :-
(member(Next, Path) -> Qn = Q ; enqueue([Next | Path], Q, Qn)),
add_path(Goal, Path, Rest, Qn, Qe).
add_path はリスト NextList に格納された隣接地点を取り出し、経路 Path を延ばしてキューに格納します。このとき、ゴール地点のチェックも行います。最初の規則が隣接地点をすべて取り出した場合です。これが再帰呼び出しの停止条件となります。第 3 引数には経路を追加したキューがセットされているので、これを第 4 引数にマッチングさせます。
次の規則がゴールに到達した場合です。経路を表示するだけで、キューには格納しません。Prolog の場合、失敗したときには再試行するので、最後の規則を実行しないようにカットを使っています。ここでカットを使いたくない場合は、breadth_search の再帰呼び出しの手前にカットを入れてください。
そして、最後の規則で経路を延ばしてキューに追加します。Next が Path に含まれていないか member でチェックし、含まれていなければ enqueue でキューに追加します。含まれている場合はキューに追加しないで Qn と Q をマッチングさせます。あとは、add_path を再帰呼び出しするだけです。このとき、キューは Qn を渡すことをお間違いなく。
最後に breadth_first_search を呼び出すプログラムを作ります。
リスト : 幅優先探索の実行
keiro(Start, Goal) :-
enqueue([Start], [Q, Q], Qn), breadth_first_search(Goal, Qn).
breadth_first_search を呼び出す前に、最初の経路 [Start] をキューに追加します。それでは実行してみましょう。
?- keiro(a, k). [a,f,j,k] [a,b,f,j,k] [a,f,g,j,k] [a,f,i,j,k] [a,e,f,j,k] [a,b,f,g,j,k] [a,b,f,i,j,k] [a,b,c,g,j,k] [a,e,f,g,j,k] [a,e,f,i,j,k] [a,e,h,i,j,k] [a,b,c,g,f,j,k] [a,f,b,c,g,j,k] [a,f,e,h,i,j,k] [a,e,h,i,f,j,k] [a,b,f,e,h,i,j,k] [a,b,c,g,f,i,j,k] [a,e,f,b,c,g,j,k] [a,e,h,i,f,g,j,k] [a,b,c,g,f,e,h,i,j,k] [a,e,h,i,f,b,c,g,j,k] false. ?-
正常に動作していますね。
●失敗駆動ループによる実装
今度は失敗駆動ループを使ってプログラムを作ってみましょう。再試行する場合、Prolog はマッチングした変数を自由変数に戻すため、キューを変数に格納しておくことはできません。このため、失敗駆動ループでキューを使う場合、キューの状態を節に格納しておく必要があります。今回は節 queue にキューを格納することにしましょう。キューを操作する述語は次のようになります。
リスト : キューの操作 (その２)
% キューの初期化
make_queue :- assert(queue([Q, Q])).
% データを追加
enqueue(Item) :-
queue([Qh, [Item | Qt]]),
retractall(queue(_)),
assert(queue([Qh, Qt])).
% データを取り出す
dequeue(Item) :-
queue([[Item | Qh], Qt]),
retractall(queue(_)),
assert(queue([Qh, Qt])).
% キューにデータがある間繰り返す
repeat_queue :-
repeat, queue([Qh, Qt]), (Qh == Qt -> (!, fail) ; true).
enqueue と dequeue は節 queue からキューを取り出し、retractall で古い状態を削除してから assert で新しい状態を格納します。このプログラムで重要な働きをする述語が repeat_queue です。この述語はキューにデータがあると成功し、なければ失敗します。
次に、述語 repeat を使って失敗駆動ループを形成します。データがないときは、カットを使って失敗駆動ループから脱出することをお忘れなく。
次は経路を延ばしてキューに加える述語 add_one_path を作ります。
リスト : 経路を延ばす
add_one_path(Goal, [Goal | Node]) :-
reverse([Goal | Node], Path), write(Path), nl, !, fail.
add_one_path(Goal, [Node | Rest]) :-
next(Node, Next),
not(member(Next, Rest)),
enqueue([Next, Node | Rest]),
fail.
add_one_path は、経路の探索(2) : 幅優先探索 で作成した述語 extend_one_path とほとんど同じです。extend_one_path では経路を節 path に記憶しましたが、add_one_path では経路をキューに格納します。違いはこれだけです。add_one_path は失敗駆動ループで使うため、必ず失敗することに注意してください。
最後に、幅優先探索を行う breadth_first_search を作ります。
リスト : 幅優先探索
breadth_first_search(Start, Goal) :-
% 初期化
make_queue, enqueue([Start]),
% 繰り返し
repeat_queue, dequeue(Path), add_one_path(Goal, Path).
これは簡単ですね。make_queue でキューを初期化し、出発点をキューにセットします。あとは、キューにデータがある間、dequeue で経路を取り出して、add_one_path で経路を延ばします。
それでは実行してみましょう。
?- breadth_first_search(a, k). [a, f, j, k] [a, b, f, j, k] [a, f, g, j, k] [a, f, i, j, k] [a, e, f, j, k] [a, b, f, g, j, k] [a, b, f, i, j, k] [a, b, c, g, j, k] [a, e, f, g, j, k] [a, e, f, i, j, k] [a, e, h, i, j, k] [a, b, c, g, f, j, k] [a, f, b, c, g, j, k] [a, f, e, h, i, j, k] [a, e, h, i, f, j, k] [a, b, f, e, h, i, j, k] [a, b, c, g, f, i, j, k] [a, e, f, b, c, g, j, k] [a, e, h, i, f, g, j, k] [a, b, c, g, f, e, h, i, j, k] [a, e, h, i, f, b, c, g, j, k] false. ?-
正常に動作していますが、実行時間は末尾再帰版よりも遅くなりました。キューの状態を格納している節 queue を頻繁に書き換えるので、実行時間が遅くなるのは仕方がないのでしょう。キューを使う場合は、末尾再帰と組み合わせた方がよさそうです。
改訂 2023 年 4 月 22 日