Prologプログラミング: 探索問題


Prolog のバックトラック (後戻り) 機能を使うと, 数多くの可能性の中から解を探索するプログラムを簡単に作れます.

グラフの経路探索

有向グラフの経路 (path) を探索するプログラムを作って見ましょう. まず,次のような有向グラフが与えられているとします. v1, v2, v3, v4, v5 は頂点 (vertex), a1, a2, a3, a4, a5 は弧 (arc) の名前です.
             a1 
        v1 ──→ v2
        ↑        │
        │a4      │a2
        │        ↓
        v4 ←── v3 ──→ v5
             a3        a5
このグラフは次のように Prolog の事実の集まりで表現できます. ここで arc(A, U, V) は, A が U から V への弧であることを表します.

    arc(a1, v1, v2).
    arc(a2, v2, v3).
    arc(a3, v3, v4).
    arc(a4, v4, v1).
    arc(a5, v3, v5).
では,与えられた頂点 U から V への歩道 (walk) が存在するかどうかを 調べるプログラムを書いて見ましょう.

    walk(U, U).
    walk(U, V) :- arc(_, U, U1), walk(U1, V).
実行して見ると, v1 から v4 などについてはちゃんと yes と表示されますが v1 から v5 は答が出ません. これは, v1 → v2 → v3 → v4 → v1 → … となり, プログラムが無限ループしているためです. 無限ループを止めるには C-c (コントロールC) を入力してから a を入れます.

    | ?- walk(v1, v4).
    yes
    | ?- walk(v1, v5).
    C-cを入力
    Prolog interruption (h for help)? a
    { Execution aborted }
    | ?- 
無限ループを避けるために,1 度通った頂点はもう通らないようにします. すなわち道 (path) を探すように書換えます.

    path(U, U, _).
    path(U, V, L) :-
        arc(_, U, U1),
        \+ member(U1, L),
        path(U1, V, [U1|L]).
L はこれまでに通ってきた頂点のリストです. \+ は否定を表す組込述語で, \+ member(U1, L) は U1 が L の要素でないときに成功します.

    | ?- path(v1, v5, [v1]).
    yes
このままでは,どの弧を通ってきたかわからないので, 通ってきた弧のリストを返すようにプログラムを変更します.

    path(U, U, _, []).
    path(U, V, L, [A|P]) :-
        arc(A, U, U1),
        \+ member(U1, L),
        path(U1, V, [U1|L], P).
最後に,次のようなプログラムを付け加えて完成です.

    path_find(U, V, P) :- path(U, V, [U], P).
これを実行してみます.

    | ?- path_find(v1, v5, P).
    P = [a1,a2,a5] ? 

宣教師と人喰い土人のパズル

次のようなパズルを解くプログラムを考えてみましょう.

3 人の宣教師と 3 人の人喰い土人が川の左岸にいます. 1 隻の 2 人乗りボートを使って, 右岸に渡るにはどうすれば良いでしょうか? ただし土人の人数が宣教師の人数よりも多くなると, 宣教師は喰われてしまいます.

最初の状態 ( ○: 宣教師, ●: 人喰い土人, 【>: ボート )

        左岸   |    川   |   右岸
               |         |
        ○○○ |【>     |
        ●●● |         |
               |         |
     
目標の状態

        左岸   |    川   |   右岸
               |         |
               |     【>| ○○○
               |         | ●●●
               |         |
     
最初にボートに乗るのは ○, ●, ○○, ○●, ●● の 5 通りの場合があります (ボートは 2 人乗りです). ○● が移った場合について考えてみます. 次のステップでは ○ か ● かのどちらかが 右岸から左岸にボートに乗って戻ってくることになります. このように考えていって,うまく全員が右岸に行くことができるでしょうか?

これは一種の経路探索問題と考えることができます. つまり次のように考えるわけです.

すると,堂々巡りを避けるということは, 同じ頂点を 2 度と通らないということになります. したがって,上で説明した経路探索プログラム path_find が そのまま使えるわけです.

ただ path_find を使うためには,次の事を決めておかなければいけません.

左岸にいる ○ と ● の数がわかれば,右岸にいる数もすぐわかりますし, ボートについても左岸にあるかどうかがわかれば良いので, 頂点 (つまり状態) を以下のようなリストで表すことにします.

        [ B, M, C ]
ただし,B, M, C は以下の通りです.

        B : ボートが左岸にあれば 1, 右岸にあれば 0
        M : 左岸にいる ○ の数 (0〜3)
        C : 左岸にいる ● の数 (0〜3)
弧は, 1 ステップの動作を表すので,以下のような項で表すことにします.

        move(M, C) : ○ M人, ● C人を左岸から右岸へ移動
        back(M, C) : ○ M人, ● C人を右岸から左岸へ移動
すると,弧を表す述語 mc_arc1 は次のように書けます.

mc_arc1(move(1,0), [1,M0,C0], [0,M,C]) :- M is M0-1, C is C0.
mc_arc1(move(0,1), [1,M0,C0], [0,M,C]) :- M is M0,   C is C0-1.
mc_arc1(move(2,0), [1,M0,C0], [0,M,C]) :- M is M0-2, C is C0.
mc_arc1(move(0,2), [1,M0,C0], [0,M,C]) :- M is M0,   C is C0-2.
mc_arc1(move(1,1), [1,M0,C0], [0,M,C]) :- M is M0-1, C is C0-1.

mc_arc1(back(1,0), [0,M0,C0], [1,M,C]) :- M is M0+1, C is C0.
mc_arc1(back(0,1), [0,M0,C0], [1,M,C]) :- M is M0,   C is C0+1.
mc_arc1(back(2,0), [0,M0,C0], [1,M,C]) :- M is M0+2, C is C0.
mc_arc1(back(0,2), [0,M0,C0], [1,M,C]) :- M is M0,   C is C0+2.
mc_arc1(back(1,1), [0,M0,C0], [1,M,C]) :- M is M0+1, C is C0+1.
これだけだと ○ や ● の数が負になったりすることがあるので, そのチェックと, 土人に食べられてしまう場合を除くためのチェックを 加えると以下のようになります.

    mc_arc(Move, U, V) :-
	mc_arc1(Move, U, V),
	V = [_,M,C],
	M >=0, C >=0, 
	not_eaten(M, C),
	M1 is 3-M, C1 is 3-C,
	M1 >=0, C1 >=0, 
	not_eaten(M1, C1).
4, 5 行目は左岸についてのチェック, 6, 7, 8 行目は右岸についてのチェックを行っています. 述語 not_eaten は次のようになります.

    not_eaten(0, _) :- !.
    not_eaten(_, 0) :- !.
    not_eaten(M, C) :- M >= C.
○ か ● が 0 であれば OK. ともに 0 でなければ ○ が ● 以上でなければいけません.

最後に path_find と同様のプログラムを付け加えれば完成です.


    mc_puzzle(U, V, P) :- mc_puzzle(U, V, [U], P).

    mc_puzzle(U, U, _, []).
    mc_puzzle(U, V, L, [A|P]) :-
        mc_arc(A, U, U1),
        \+ member(U1, L),
        mc_puzzle(U1, V, [U1|L], P).
実行して見ると以下のような解が得られます.

    | ?- mc_puzzle([1,3,3], [0,0,0], P).
    P = [move(0,2),back(0,1),move(0,2),back(0,1),move(2,0),back(1,1),
         move(2,0),back(0,1),move(0,2),back(1,0),move(1,1)] ? 

整数の分割

正の整数 N を,M 個の正の整数の和の形に表すことを考えます. すなわち次の条件を満たす正の整数のリスト [ X1, X2, ..., XM ] を見つけるという問題です.
N = X1 + X2 + … + XM
再帰的に考えると,以下のようになります.
  1. 整数 N (N≧1) の長さ1のリストへの分割は,[N]
  2. 整数 N (N≧1) の長さ M (M≧2) のリストへの分割は, 1≦I≦N-M+1 なる各 I について, 整数 N-I の長さ M-1 のリストへの分割を L とすると, [I|L] である.
これをプログラムにすると,以下のようになります.

    part(N, 1, [N]).
    part(N, M, [I|L]) :-
        M >= 2,
        I1 is N-M+1,
        for(I, 1, I1),
        N1 is N-I,
        M1 is M-1,
        part(N1, M1, L).

    for(N, N, M) :- N =< M.
    for(I, N, M) :- N =< M, N1 is N+1, for(I, N1, M).

N-クイーン問題

作成中

覆面算

作成中

練習問題

mc_puzzle を参考にして,次のパズルを解くプログラムを作りなさい.
狼とヤギとキャベツを持った百姓が,丸木橋を渡ります. 丸木橋を渡るときは,多くて 1 つのものしか運べません. また百姓がいないと,狼はヤギを,ヤギはキャベツを食べてしまいます. どのような順序で運べば良いでしょうか.

最初に戻る 前へ 次へ