4.6 応用: 簡単な探索問題

最後に次節に述べる負荷分散制御への理解を深めるために, 非常に良く似た探索問題を優先度制御を利用してプログラム化してみよう. 探索問題は, 探索木の各ノー ドを探索して解の含まれているリーフ(葉)を見つける問題である. 探索する 順序には関係なく, 最悪全てのリーフを探索すれば答えは見つかる. しかし, 探索問題の多くのものは経験的に木の左の方とか右の方とか, どのあたりに解 が含まれている確率が高いかわかっているものが多い. ここでは, そのよう なヒューリスティックを適用できる探索問題を考えてみる.

なお, 同期制御を行なえば木の左から探索するようにプログラムを書く事は可 能であるが, それでは逐次実行しかできない. ここでは, 並列実行ができか つヒューリスティックを適用するように, 優先度制御を使ってみよう.

図4.16に示されるような2分探索木があった時, アトムを含 むリーフを1つ見つけるプログラムを書け.

  
図 4.16: 探索木

図4.16において四角はノードを表わし, 楕円はリーフを表わす. また, ノードには a から l の名前が付けてあり, リーフは整数 或いはアトムを値として持つ. この探索木をここでは次の様なリストデータ で表わす事にする.

     [[[1,[here,[2,here]]],[here,here]],[[[3,[4,5]],6],[[here,7],8]]]

ではまず, ヒューリスティクを用いずにこの探索問題を解くプログラムをみて みよう. ここでは, アトムが見つかったらそのアトムを要素とするリス トを返し, 見つからなかったら空リストを返すようにプログラムしてある. また, 探索を行なうプロセスは一斉に生成する. 解を一つ見つけたプロセス は, 探索中の他のプロセスに対してこれ以上探索しなくてもよい旨を通知する. なお, 一斉に通知するために全ての探索プロセスは同一の制御用変数を持ち廻 る. 各探索プロセスは, この変数の値が決まるのを alternatively の機能を 使ってチェックする.

:- module simple_search.

        search(Tree,Output):- true |               %(1)
                control(Result,Output,Cont),       %(2)
                fork(Tree,Result,Cont).            %(3)
        fork(_,R,stop):-   true | R=[].            %(4)
    alternatively.                                 %(5)
        fork(H,R,Cont):- integer(H) |R=[].         %(6)
        fork(H,R,Cont):- atom(H)    |              %(7)
                R=[H].                             %(8)
        fork([TL,TR],R,Cont):-                     %(9)
                merge:in(R0,R1,R),                 %(10)
                fork(TL,R0,Cont),                  %(11)
                fork(TR,R1,Cont).                  %(12)
        control([H|_],Output,Cont):- wait(H) |     %(13) 
                Output = [H], Cont=stop.           %(14) 
        control([], Output, Cont):- true |         %(15)
                Output = [] .                      %(16) 

:- module merge.

        in([E|In1],In2,Out) :-                     %(17)
                Out = [E|OutT], in(In1,In2,OutT).  %(18)
        in(In1,[E|In2],Out) :-                     %(19)
                Out = [E|OutT], in(In1,In2,OutT).  %(20)
        in([],In2,Out) :-  Out = In2.              %(21)
        in(In1,[],Out) :-  Out = In1.              %(22)

メインプログラム例
:- module main.

        main :-                                    %(23)
           Tree=[[[1,[here,[2,here]]],[here,here]],
                [[[3,[4,5]],6],[[here,7],8]]],
               simple_search:search(Tree,Out),     %(24)
               klicio:klicio([stdout(Result)]),    %(25)
               wait_open(Result, Out).             %(26)
        wait_open(normal(STDOUT), Out) :-          %(27)
           STDOUT=[ putt(Out), nl ].               %(28)
        wait_open(abnormal, _) :- unix:exit(1).    %(29)

では, プログラムの説明を行なう.

search

このプログラムのトップレベルの述語である. 解が 1 つ見つかった時に探索 を終了するための制御を行なうプロセス control と探索を行なうプロ セス fork を生成する.

fork

クローズ (4) では, 変数 Cont の値がアトム stop に決まった らそれ以降の探索を中止する. Alternatively を用いており, このクローズ は必ず最初に選択される. Cont の値が決まっていなかったら, (6) 以 降のクローズの選択を行なう.

fork

クローズ (6) では, H が整数ならばそれはリーフなのでそれ以上探索 は行なわない. また, それは解ではないので解を集めるストリームには [] を流す.

fork

クローズ (8) では, H が アトムなら, それはリーフなのでそれ 以上探索は行なわない. また, それは解なのでストリームにはそのアトム自 身を流す.

fork

クローズ (9) では, 探索木が 2 要素のリストで各ノードを表わしている場 合に, その左の探索木 TL と 右の探索木 TRのそれぞれを探索す るプロセスを (11) と (12) で生成している. なお, (10) の部分ではここで 生成した2つのプロセスから返ってくる解のストリーム R0 と R1 をマージインしている.

control

クローズ (13) では, 解を集めるストリーム Output に解が1つでも見 つかった時に, 他の探索を行なうプロセスを中止するために変数 Cont の値を stop に決めている.

in

クローズ (17), (19), (21),(22) で標準的な 2 入力のマージプロセスを 実現している.

main

クローズ (23) にて計算を行なっている. [here] が印刷される.

ここで, fork プロセスを生成する部分 (11) と (12) をみてみよう. (11) はノードの左を探索するプロセスを生成しており, (12) ではノードの右 を探索するプロセスを生成している. このプログラムを実行すると, もしか したら右側の探索が優先的に実行され, 例えばノード c の下の探索ば かりが実行されるかも知れないが, この下には解が1つしかないので効率は良 くない.

では, 幅優先のヒューリスティクスを, ゴールの優先度制御を用いて このプログラムに適用してみよう. 優先度を付ける戦略としては, 探索木の 探索するゴール (11) および (12) を呼び出す枝より優先度を低くする. すると別の枝の同じ深さのゴールがあった場合は, そちらが優先的に 実行される.

例えば探索ルートの優先度を 4000 とし, このアルゴリズムに従って優先度を みてみると, 探索木の各ノード及びリーフに おけるプロセス fork の優先度は図4.17のよう になる. 図中, 各ノード及びリーフの右肩或いは左肩の数字は優先度を表わ す. また, 続けてプログラムをみてみよう.

  
図 4.17: 探索木の各ノードプロセスの優先度

:- module search_pri.

        search(Tree,Output):- true |                    %(1)
                control(Results,Output,Cont),           %(2)
                fork(Tree,Results,Cont)@priority(4000). %(3)
        fork(_,R,stop):- true | R=[].                   %(4)
        alternatively.                                  %(5)
        fork(H,R,_):- integer(H) | R=[].                %(6)
        fork(H,R,Cont):- atom(H) |                      %(7)
                R=[H].                                  %(8)
        fork([TL,TR],R,Cont):-true |                    %(9)
                merge:in(R0,R1,R),                      %(10)
                fork(TL,R0,Cont)@lower_priority,        %(11)
                fork(TR,R1,Cont)@lower_priority.        %(12)
        control([H|_],Output,Cont):- wait(H) |          %(13)
                Output=[H], Cont=stop.                  %(14)
        control([],Output,Cont):- true | Output=[].     %(15)

先のプログラムから変更した部分は, 次の通りである.

search 引数を2つ増やして, 探索を行なうプロセスが使う 最高優先度を指定した.

fork (11)と(12)の部分で探索するプロセスを生成する際, 優 先度を下げている.

なお, この例では探索がある程度以上深くなると優先度はこれ以上低くできな くなるが, 優先度制御を行なう事によってプログラムは効率的に動く事は分かっ たであろう.