カテゴリー: PROLOG

ネットで見つけた以下の川渡り問題をPrologで解いてみました。

おなじみのやつですね。

Art of Prologとかm.hiroiさんのホームページでも載っていました。

問題：

ある家族がいて、舟を使って川を向こう岸へ渡ろうとしています。
この家族は父、母、息子１、息子２、娘１、娘２、メイド、犬、じっちゃん、
赤ん坊の１０人家族(犬も１人と数えます)です。
舟は１艘(そう)しかなく、１度に２人まで乗ることができます。
また、この舟をこげるのは父と母とメイドとじっちゃんの４人です。

父は、母がいなくなると娘を殺してしまいます。
母は、父がいなくなると息子を殺してしまいます。
じっちゃんは、親がいないと息子や娘、赤ん坊を殺してしまいます。
息子や娘は、親がいないと赤ん坊を殺してしまいます。
犬は、メイドがいないと家族をみんな殺してしまいます。

みんなが無事に川を渡り切るには、どのような手順で渡ればよいでしょうか？

プログラム解説：

盤面生成→チェック → 再帰で次の盤面生成 → チェック → … → クリアするまで繰り返し
失敗すれば バックトラックで次の選択肢を試す
Prologで何も考えずに深さ優先探索で解いています。
枝刈りを行っていず効率の悪いプログラムですが、この程度の問題だと全然問題ないようです。

現在の状態は以下の形式のcompound termで表しています。

state(左岸にいる人のリスト,船に乗っている人のリスト,右岸にいる人のリスト,船の位置(left , right , crossing のいずれか))

assertで生成したstateを登録するようにして、登録済のstateには遷移しないようにしています(意味のない行ったり来たりを防ぐ)

assertする際 順列ではなく組み合わせで登録したいため、リスト内をソートしてから登録しています。

この程度のプログラムだとあまり考えず機械的作業で量産できるようになってきた。

プログラム：

main:-
	retractall(state(_,_,_,_)), % assertされた全stateの初期化
	A=state([father,mother,son,son,daughter,daughter,maid,dog,granpa,baby],[],[],left), % Initial State
	sort_state(A,A1),
	assert(A1), 
	solve(A1).

% クリア
solve(state([],[],_,right)):-
	write('cleared!').

% 次の盤面の生成、リストの並び替え、生成した盤面が問題ないかチェック、問題なければ登録、再帰呼び出しにより次のステップへ
solve(A):-
	nextstate(A,A1),
	sort_state(A1,A2),
	chk(A2),
	assert(A2),
	solve(A2),
	nl,
	write(A2).

% 盤面の各リストを並び替える
sort_state(state(Left,Ship,Right,Pos),state(Left1,Ship1,Right1,Pos)):-
	msort(Left,Left1),
	msort(Ship,Ship1),
	msort(Right,Right1).

% 盤面のチェック
chk(state(Left,Ship,Right,Pos)):-
	not(state(Left,Ship,Right,Pos)),% 生成された state がまだassertされていないことを確認
	not(chk_kill(Left)), 			% 左岸で殺される人がいないかチェック
	not(chk_kill(Ship)), 			% 船で殺される人がいないかチェック
	not(chk_kill(Right)), 			% 右岸で殺される人がいないかチェック
	chk_ship(Ship).					% 船に運転できる人が乗っているかチェック
	
% 父は、母がいなくなると娘を殺してしまいます。
chk_kill(List):-
	memberchk(father,List),
	memberchk(daughter,List),
	not(memberchk(mother,List)).
	
% 母は、父がいなくなると息子を殺してしまいます。
chk_kill(List):-
	memberchk(mother,List),
	memberchk(son,List),
	not(memberchk(father,List)).
	
% じっちゃんは、親がいないと息子や娘、赤ん坊を殺してしまいます。
chk_kill(List):-
	memberchk(granpa,List),
	(memberchk(son,List);memberchk(daughter,List);memberchk(baby,List)),
	not(memberchk(father,List)),
	not(memberchk(mother,List)).

% 息子や娘は、親がいないと赤ん坊を殺してしまいます。
chk_kill(List):-
	memberchk(baby,List),
	(memberchk(son,List);memberchk(daughter,List)),
	not(memberchk(father,List)),
	not(memberchk(mother,List)).

% 犬は、メイドがいないと家族をみんな殺してしまいます。
chk_kill(List):-
	memberchk(dog,List),
	not(memberchk(maid,List)),
	(	memberchk(son,List);
		memberchk(daughter,List);
		memberchk(baby,List);
		memberchk(father,List);
		memberchk(mother,List);
		memberchk(granpa,List)
	).
	
% この舟をこげるのは父と母とメイドとじっちゃんの４人
chk_ship([]).
chk_ship(List):-
	(
		memberchk(father,List);
		memberchk(mother,List);
		memberchk(maid,List);
		memberchk(granpa,List)
	).
		
% 左岸から２人を選んで船に乗せる
nextstate(state(Left,[],Right,left),NextState):-
	select(Sel1,Left,Left1),
	select(Sel2,Left1,Left2),
	NextState=state(Left2,[Sel1,Sel2],Right,crossing).
	
% 左岸から１人を選んで船に乗せる
nextstate(state(Left,[],Right,left),NextState):-
	select(Sel1,Left,Left1),
	NextState=state(Left1,[Sel1],Right,crossing).

% 右岸から２人を選んで船に乗せる
nextstate(state(Left,[],Right,right),NextState):-
	select(Sel1,Right,Right1),
	select(Sel2,Right1,Right2),
	NextState=state(Left,[Sel1,Sel2],Right2,crossing).

% 右岸から１人を選んで船に乗せる
nextstate(state(Left,[],Right,right),NextState):-
	select(Sel1,Right,Right1),
	NextState=state(Left,[Sel1],Right1,crossing).

% 船に乗っている人を左岸に降ろす
nextstate(state(Left,Ship,Right,crossing),NextState):-
	append(Left,Ship,Left1),
	NextState=state(Left1,[],Right,left).
	
% 船に乗っている人を右岸に降ろす
nextstate(state(Left,Ship,Right,crossing),NextState):-
	append(Right,Ship,Right1),
	NextState=state(Left,[],Right1,right).

実行結果：
（下から上に答えに近づいていきます）

4 ?- time(main).
cleared!
state([],[],[baby,daughter,daughter,dog,father,granpa,maid,mother,son,son],right)
state([],[dog,maid],[baby,daughter,daughter,father,granpa,mother,son,son],crossing)
state([dog,maid],[],[baby,daughter,daughter,father,granpa,mother,son,son],left)
state([dog],[maid],[baby,daughter,daughter,father,granpa,mother,son,son],crossing)
state([dog],[],[baby,daughter,daughter,father,granpa,maid,mother,son,son],right)
state([dog],[maid,son],[baby,daughter,daughter,father,granpa,mother,son],crossing)
state([dog,maid,son],[],[baby,daughter,daughter,father,granpa,mother,son],left)
state([son],[dog,maid],[baby,daughter,daughter,father,granpa,mother,son],crossing)
state([son],[],[baby,daughter,daughter,dog,father,granpa,maid,mother,son],right)
state([son],[father,son],[baby,daughter,daughter,dog,granpa,maid,mother],crossing)
state([father,son,son],[],[baby,daughter,daughter,dog,granpa,maid,mother],left)
state([son,son],[father],[baby,daughter,daughter,dog,granpa,maid,mother],crossing)
state([son,son],[],[baby,daughter,daughter,dog,father,granpa,maid,mother],right)
state([son,son],[father,granpa],[baby,daughter,daughter,dog,maid,mother],crossing)
state([father,granpa,son,son],[],[baby,daughter,daughter,dog,maid,mother],left)
state([father,son,son],[granpa],[baby,daughter,daughter,dog,maid,mother],crossing)
state([father,son,son],[],[baby,daughter,daughter,dog,granpa,maid,mother],right)
state([father,son,son],[dog,maid],[baby,daughter,daughter,granpa,mother],crossing)
state([dog,father,maid,son,son],[],[baby,daughter,daughter,granpa,mother],left)
state([dog,maid,son,son],[father],[baby,daughter,daughter,granpa,mother],crossing)
state([dog,maid,son,son],[],[baby,daughter,daughter,father,granpa,mother],right)
state([dog,maid,son,son],[father,granpa],[baby,daughter,daughter,mother],crossing)
state([dog,father,granpa,maid,son,son],[],[baby,daughter,daughter,mother],left)
state([father,granpa,son,son],[dog,maid],[baby,daughter,daughter,mother],crossing)
state([father,granpa,son,son],[],[baby,daughter,daughter,dog,maid,mother],right)
state([father,granpa,son,son],[baby,mother],[daughter,daughter,dog,maid],crossing)
state([baby,father,granpa,mother,son,son],[],[daughter,daughter,dog,maid],left)
state([baby,father,granpa,son,son],[mother],[daughter,daughter,dog,maid],crossing)
state([baby,father,granpa,son,son],[],[daughter,daughter,dog,maid,mother],right)
state([baby,father,granpa,son,son],[dog,maid],[daughter,daughter,mother],crossing)
state([baby,dog,father,granpa,maid,son,son],[],[daughter,daughter,mother],left)
state([baby,dog,father,maid,son,son],[granpa],[daughter,daughter,mother],crossing)
state([baby,dog,father,maid,son,son],[],[daughter,daughter,granpa,mother],right)
state([baby,dog,father,maid,son,son],[granpa,mother],[daughter,daughter],crossing)
state([baby,dog,father,granpa,maid,mother,son,son],[],[daughter,daughter],left)
state([baby,dog,father,granpa,maid,son,son],[mother],[daughter,daughter],crossing)
state([baby,dog,father,granpa,maid,son,son],[],[daughter,daughter,mother],right)
state([baby,dog,father,granpa,maid,son,son],[daughter,mother],[daughter],crossing)
state([baby,daughter,dog,father,granpa,maid,mother,son,son],[],[daughter],left)
state([baby,daughter,father,granpa,mother,son,son],[dog,maid],[daughter],crossing)
state([baby,daughter,father,granpa,mother,son,son],[],[daughter,dog,maid],right)
state([baby,daughter,father,granpa,mother,son,son],[daughter,maid],[dog],crossing)
state([baby,daughter,daughter,father,granpa,maid,mother,son,son],[],[dog],left)
state([baby,daughter,daughter,father,granpa,mother,son,son],[maid],[dog],crossing)
state([baby,daughter,daughter,father,granpa,mother,son,son],[],[dog,maid],right)
state([baby,daughter,daughter,father,granpa,mother,son,son],[dog,maid],[],crossing)
% 85,495 inferences, 0.031 CPU in 0.031 seconds (100% CPU, 2740207 Lips)
true ;
% 32,876 inferences, 0.031 CPU in 0.031 seconds (100% CPU, 1053711 Lips)
false.

Prologではプログラムのほとんどの記述は演算子を用いて記述され、言語全体を通して一貫している。

例えば、以下のようなリストの長さを返す述語my_lengthがあるとする。

my_length([],0).
my_length([_|Rest],Cnt):- my_length(Rest,Cnt0),Cnt is Cnt0 + 1.


このとき、下の方のclauseを例とすると、使用されている記号

「:-」 「|」 「,」 「+」 「is」

はどれも組み込みの優先度付き演算子として定義されていて、節全体がPrologの内部表現としては下の図のような木構造で表されている。

ここで、ボディの規則が「,」という演算子で結ばれていることがわかる。
演算子は1項及び2項なので、カンマで3つ以上の規則をつなげた規則a,規則b,規則c のような場合は、演算子の xfy の定義により

‘,'(規則a, ‘,'(規則b,規則c))

というような右方向に入れ子となる木構造として表現される。

Swi-Prologのプロンプトでの実験

6 ?- Test=(a,b,c),Test=..List.
Test = (a, b, c),
List = [',', a, (b, c)].


ここで、abc(prm1,prm2) などの compound term の引数で使われているカンマに関して考えてみると、これは実は演算子ではない。

例えば、少し無理やりですが、以下のプロンプトの実験はマッチング失敗します。

8 ?- abc(','(prm1,prm2)) = abc(prm1,prm2).
false.


しかし右辺のprm1,prm2をさらにカッコでくくるとマッチング成功します。

10 ?- abc(','(prm1,prm2))=abc((prm1,prm2)).
true.

これは(prm1,prm2)とだけ書いた表現が、「カンマ演算子の引数としてprm1、prm2を渡したもの」を表していることを意味している。

そして、[a,b,c,d,e]などのリストで使用されているカンマはそのまま演算子として使用されるのではなく、ドット演算子に変換されます。

プロンプトでの実験

7 ?- [a,b,c]=R,R=..Y.
R = [a, b, c],
Y = ['.', a, [b, c]].


はじめに紹介したmy_lengthの木構造で [_|Rest] の部分が ピリオドに変わっていますが、これもドット演算子で、ドット演算子はPrologのリストを Lisp の car と cdr のように「最初の要素」と「残りのリスト(空リスト含む)」に分けます。

プロンプトでの実験

4 ?- [First|Rest]='.'(First,Rest).
true.

6 ?- [a,b,c,d,e]=','(a,(b,c,d,e)).
false.


上記で分かる通り、Prologでは同じカンマでも「演算子のカンマ」と「演算子でないカンマ（term の引数のカンマ、ドット演算子に変換されるカンマ）」が混在していることになる。

誰かのブログで、Prologの構文をいじれるとしたらterm(prm1,prm2)のカンマをスペースにしたいと書いている人がいて、はじめなぜそうしたいのか意味がわからなかったけど、「演算子ではないカンマは空白にしたい」という意味として考えると、なるほど混乱を避けるためにはその方が良いかもと思うようになった。そうするとリストの要素を分けるカンマも手を付けたほうが良い？

ドット演算子と述語の終わりを意味するピリオドも同じ文字だが全然意味が違い、厳密性を考えるとこれも紛らわしいような気がする。
述語の終わりのピリオドは一体演算子なのかちょっと確認できなかったのですが、多分違うと思います（詳細を知っている方いらっしゃいましたらぜひ教えてください）

Prologで述語論理の存在記号∃をどうやって表現するのか？

Prologは一階述語論理をベースに作られているから、論理学の色々な記号を表すのは得意だろう、それなら存在記号∃を表すことも出来るのではないだろうかと思いいろいろ調べていたのですが、文法にはそれっぽいのなく、う～んできないのかな…と悩んでいました。

存在記号というのは

「人間の中には血液型がA型の人間が存在する」

などを表す記号です。

もうひとつ「全称記号∀」というのがあるのですが、これは「すべての」を表す記号で、例えば

「すべての人間は、呼吸をする」

などを表す記号です。

これはPrologで表すのは簡単で、

breathe(A):-human(A). % Aが人間であれば呼吸をするという述語

で表すことが出来ます。
Aというのが自由変数になっていてどのような対象にもマッチングするので、「すべての」が表現できるのです。

このプログラムに、例えば

human(taro). % taroは人間であるという記述

と追記し、プロンプトで

breathe(A).

と入力すると

A = taro.

（呼吸するのはtaro）
という返答が返ってきます。

そして始めの疑問に戻りますが、
上記の存在記号∃バージョンは果たしてどのように記述するのか。

「人間の中には血液型がA型の人間が存在する」

はどうPrologで記述するのか。

yahooの知恵袋や外国のstackoverflowで英語で質問してみたのですが、回答が得られず、あきらめかけていたのですが、以下のページを見てやっとわかりました。

Convert first-order logic expressions to normal form

このページの

4. Somebody has a car.

が

person(sk10).
car(sk11).
has(sk10, sk11).


に変換されているのを見てやっと分かりました

「なんでもいいから、何か」を登録すれば良いのです

human(someone).
bloodtype_A(someone).

これでOKです。

someoneというのはいったい誰なのか、それは自分もわからない。
とにかくそれは人間です。
そして、bloodtype_A(_)を満たす人間someoneが、間違いなく存在する。
これで∃の条件は満たされます。
ここで引数に自由変数を使ってしまうと、上で述べた「すべての」になってしまうのでアウトです。

さらにいうと、色々な述語をつくるときに、この someone という同じアトムを使いまわすとおかしくなる
（someoneは血液型がAでしかもBでとかになる）
ので、someoneの後ろに添え字を追加し、述語ごとにユニークにする必要があるでしょう。

気付けば単純なことなんだけど、なかなか思い至らなかった。

以下のように記述すると動的に任意の述語を定義できる。カンマで区切って複数述語呼び出すようなものもできる。

javascriptも文字列から関数定義とかできるけど、そんな感じに使えそうだ。

こういう機能は普通は使わないけどしかるべき時に使うとすごいプログラムが書けると思う。

セキュリティホールになりそうな気も、、、

動的に

test(X):-
X1 is X+1,
X2 is X1+1,
write(X2).

という述語を作成したい場合（意味無いけど）