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 人乗りボートを使って， 右岸に渡るにはどうすれば良いでしょうか? ただし土人の人数が宣教師の人数よりも多くなると， 宣教師は喰われてしまいます．
左岸 | 川 | 右岸 | | ○○○ |【＞ | ●●● | | | |
左岸 | 川 | 右岸 | | | 【＞| ○○○ | | ●●● | |
これは一種の経路探索問題と考えることができます． つまり次のように考えるわけです．
ただ 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)] ?
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).
最初に戻る
前へ
次へ