Category Archives: PROLOG

[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).

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

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.

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]演算子のカンマとそうでないカンマ、ドット演算子と演算子でないドット（ピリオド）

[Prolog]存在記号∃を表現する

2 Replies

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の後ろに添え字を追加し、述語ごとにユニークにする必要があるでしょう。

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

[Prolog]動的に述語定義する

Leave a reply

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

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

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

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

動的に
test(X):- X1 is X+1, X2 is X1+1, write(X2).
という述語を作成したい場合（意味無いけど）


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


		
		
			This entry was posted in PROLOG on 2016年10月19日 by koyahata.



	
				
			
						
				[prolog]attributed_variable に関して
			
										
					Leave a reply				

					


				
			prologは基本的には自由変数には1度しか値を入力できず、処理の途中で書き換えることはできない。
唯一書き換えられるタイミングはバックトラックで、バックトラックが発生するとchoice point以降の処理で設定した自由変数が全て未設定の状態になる。
しかし、attributed variableという、自由変数の属性値のような変数があり、これは変更が可能なようだ。

これは結び付けられた自由変数が設定されるとunify_hookというゴールが駆動されるようになっているようだ。

しかもattributed variableは変更の履歴情報を持っており、バックトラックで以前の値が復活されるような感じらしい。

ちょっとまだ仕組みが良く分からないが、clpfdライブラリのソースをみるとこの仕組みが多用されているのがわかる。
他にfreeze,meltという述語があり、これも自由変数に値を設定するとfreezeにより結び付けられたgoalが自動的に実行されるような仕組みになっている。whenとかいう述語はfreezeの条件付バージョンのようだ。
freeze,meltは30年くらい前の書籍であるart of prologにも記述があるので、かなり歴史のある述語のようだ。

freeze,meltはclpfdのソースでは使っていないようだ(→改めてgrepしてみると使ってる場所ありました 2016/10/04）
clpfdのソースは自分にとってはかなり難解で、Prologの基本レベルの文法を押さえただけではまったく理解することが出来ない。

気長に解析していこうと思う。
					

		
		
			This entry was posted in PROLOG on 2016年9月30日 by koyahata.								

	


	
				
			
						
				[PROLOG] compound term
			
										
					Leave a reply				

					


				
			Art of Prolog を読んでいて、Equation Solver（方程式ソルバー）を作るという記事があり、ふむふむと読んでいた。
その中で、Prologを勉強している人には常識かもしれないのですが、以下の様な記述があり「？？」となった
方程式を解く際の移項を行う術語定義で

ikou(A+B=C,A=C-B).
などの記載や、
T=a*b^c
など。
例えば後者のTには一体何が入っているのか？
[a , * , b , ^ , c]

というリストなのか？
実際にSWI-PROLOGで問い合わせて調べてみた。
3 ?- T = a*b^c,atomic(T).

false.
atomicではない。
4 ?- T = a*b^c,atom(T).

false.
atomではない
5 ?- T = a*b^c,var(T).

false.
変数ではない。
8 ?- T = a*b^c,string(T).

false.
stringではない
10 ?- T = a*b^c,compound(T).

T = a*b^c.
というわけで、compound(複合項)らしい。
ちなみに
14 ?- T = a*b^c,T = [First|Rest].

false.
15 ?- T = a*b^c,T = [].

false.
リストへのマッチングが失敗するので、リストではない。
また、
16 ?- T = a*b^c,callable(T).

T = a*b^c.
callableが成功するので、実行可能な述語として認識されている。
それでは　複合項をリストに変換する =.. を使用して調べてみよう。
18 ?- T = a*b^c,T=..List.

T = a*b^c,

List = [*, a, b^c].
Listにした場合、　「*」 「a」   「b^c」  の３つの要素を持つリストとなる。
というわけで a*b^c　という記述は 「*という演算子の引数として aとb^c を渡した*(a,b^c)みたいな複合項」 という

意味だということがわかった。
演算子の優先順位は

* 400

^ 200

で ^ のほうが高いため * のほうが外側の演算子ということで b^c はくっついているのであろう。

さらにb^cも枝の部分の複合項として認識されるので、

a*b^c = T という記述は、自動的に *(a, ^(b,c)) みたいな木構造の複合項として認識されているということがわかった。

どちらの演算子が親になるかはおそらく演算子の優先順位で決まるのであろう（実験およびマニュアル確認はしてません）
ちなみに、以下のようにした場合は
21 ?- T=a+b+c+d,T=..List.

T = a+b+c+d,

List = [+, a+b+c, d].
となるので、あくまで一番上位のレベルでは最後の演算子のみ認識され、それ以前の要素は枝として認識されている。

演算子の引数は２つのみということだろう。
これを利用して、以下のように 微分の導関数を求める述語も作れるようだ（実際はsin(x)の微分の定義など他のいろいろな述語定義が追加されます）
d( U^C, X, C*A*U^(C-1) ):-

   atomic(C),

   C\=X,

   d( U, X, A ).            
prolog derivative で検索するといくつかサンプルのソースがヒットするので興味のある人は探してみてください。
自分も興味を持ったので微分をする述語を作ってみようと思います。

完成したらこのブログに書きます（挫折するかも…）
					

		
		
			This entry was posted in PROLOG on 2016年9月26日 by koyahata.								

	


	
				
			
						
				Art of Prolog
			
										
					Leave a reply				

					


				
			Art of Prologをちまちまと読んでいます。
邦訳の「Prologの技芸」は高価かつレアでなかなか手に入りませんが、英語版は検索するとpdfが無料でダウンロードできます。
PrologのDCGは多分必須の知識だと思うけど、自分が調べた限りでは日本語のwebの情報はなく英語の解説サイトを読んで勉強しました。
このArt of PrologにもDCGのことが書いてありました。日本語でDCGのこと勉強したい人は「Prologの技芸」以外の資料は多分、ない（2016年5月現在）
希望する人がいれば僕が解説書いても良いです。
Prologは大学のとき授業でやってぜんぜんわからず憧れだけあって社会人になって真剣に勉強し始めましたが、現在は

CLPFDやAttributed VariableやCHRなど、大学の授業で学んだときより格段にパワーアップしている印象です。しかし日本ではPrologは超下火なので全然情報がない。必然的に英語を読まねばなりません。
Prolog好きな人たち（理屈っぽい文法オタクな人ではなく、Prologだとすごくパワフルに扱える事象に興味がある人）とつながりたいものだ。
					

		
		
			This entry was posted in PROLOG on 2016年5月17日 by koyahata.								

	


	
				
			
						
				簡単な巡回セールスマン問題をPrologで解く
			
										
					Leave a reply				

					


				
			「鉄道のスケジューリングアルゴリズム」という本を買って読んでいます。

その中で以下のような簡単な巡回セールスマン問題があったのでPrologでさくっと解いてみました。
あなたの会社は東京にある。札幌、大阪、博多、那覇にそれぞれクライアントを抱えており、それぞれの都市間の距離は以下である。

東京から出発してクライアント全員を１回づつ訪問し、東京に戻らなければいけない。このとき、移動距離の総和が2900km以下であるような経路は存在するだろうか？
sapporo-tokyo,511km

sapporo-osaka,667km

sapporo-hakata,883km

sapporo-naha,1398km

tokyo-osaka,278km

tokyo-hakata,566km

tokyo-naha,984km

osaka-hakata,289km

osaka-naha,740km

hakata-naha,537km
プログラム


		
		
			
			

			
			distance(sapporo,tokyo,511):-!.
distance(sapporo,osaka,667):-!.
distance(sapporo,hakata,883):-!.
distance(sapporo,naha,1398):-!.
distance(tokyo,osaka,278):-!.
distance(tokyo,hakata,566):-!.
distance(tokyo,naha,984):-!.
distance(osaka,hakata,289):-!.
distance(osaka,naha,740):-!.
distance(hakata,naha,537):-!.
distance(X,Y,Dist):-distance(Y,X,Dist),!.

solve_salesman:-
	Cities = [sapporo,osaka,hakata,naha],
	make_houmonjun(Cities,HoumonLstInit),
	append([tokyo],HoumonLstInit,HoumonLst2),
	append(HoumonLst2,[tokyo],HoumonLst3),
	calc_distance(HoumonLst3,Distance),
	write(HoumonLst3),write('    '),write(Distance),nl,
	Distance =< 2900,
	write('Success! Houmonjun:'),write(HoumonLst),write('   distance:'),write(Distance).
	
make_houmonjun([],[]):-!.
make_houmonjun(Cities,[SelectedCity|RestSelected]):-
	select(SelectedCity,Cities,RestCities),
	make_houmonjun(RestCities,RestSelected).
	
calc_distance([_],0):-!.
calc_distance([FirstCity,SecondCity | RestCities],DistSum):-
	!,
	distance(FirstCity,SecondCity,CurrentDistance),
	calc_distance([SecondCity | RestCities],OtherDistSum),
	DistSum is CurrentDistance + OtherDistSum.
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
				
						distance(sapporo,tokyo,511):-!.
distance(sapporo,osaka,667):-!.
distance(sapporo,hakata,883):-!.
distance(sapporo,naha,1398):-!.
distance(tokyo,osaka,278):-!.
distance(tokyo,hakata,566):-!.
distance(tokyo,naha,984):-!.
distance(osaka,hakata,289):-!.
distance(osaka,naha,740):-!.
distance(hakata,naha,537):-!.
distance(X,Y,Dist):-distance(Y,X,Dist),!.
 
solve_salesman:-
	Cities = [sapporo,osaka,hakata,naha],
	make_houmonjun(Cities,HoumonLstInit),
	append([tokyo],HoumonLstInit,HoumonLst2),
	append(HoumonLst2,[tokyo],HoumonLst3),
	calc_distance(HoumonLst3,Distance),
	write(HoumonLst3),write('    '),write(Distance),nl,
	Distance =< 2900,
	write('Success! Houmonjun:'),write(HoumonLst),write('   distance:'),write(Distance).
	
make_houmonjun([],[]):-!.
make_houmonjun(Cities,[SelectedCity|RestSelected]):-
	select(SelectedCity,Cities,RestCities),
	make_houmonjun(RestCities,RestSelected).
	
calc_distance([_],0):-!.
calc_distance([FirstCity,SecondCity | RestCities],DistSum):-
	!,
	distance(FirstCity,SecondCity,CurrentDistance),
	calc_distance([SecondCity | RestCities],OtherDistSum),
	DistSum is CurrentDistance + OtherDistSum.
					
				
			
		

 
実行結果


		
		
			
			

			
			[4] 27 ?- solve_salesman.
 3 ?- solve_salesman.
[tokyo,sapporo,osaka,hakata,naha,tokyo]    2988
[tokyo,sapporo,osaka,naha,hakata,tokyo]    3021
[tokyo,sapporo,hakata,osaka,naha,tokyo]    3407
[tokyo,sapporo,hakata,naha,osaka,tokyo]    2949
[tokyo,sapporo,naha,osaka,hakata,tokyo]    3504
[tokyo,sapporo,naha,hakata,osaka,tokyo]    3013
[tokyo,osaka,sapporo,hakata,naha,tokyo]    3349
[tokyo,osaka,sapporo,naha,hakata,tokyo]    3446
[tokyo,osaka,hakata,sapporo,naha,tokyo]    3832
[tokyo,osaka,hakata,naha,sapporo,tokyo]    3013
[tokyo,osaka,naha,sapporo,hakata,tokyo]    3865
[tokyo,osaka,naha,hakata,sapporo,tokyo]    2949
[tokyo,hakata,sapporo,osaka,naha,tokyo]    3840
[tokyo,hakata,sapporo,naha,osaka,tokyo]    3865
[tokyo,hakata,osaka,sapporo,naha,tokyo]    3904
[tokyo,hakata,osaka,naha,sapporo,tokyo]    3504
[tokyo,hakata,naha,sapporo,osaka,tokyo]    3446
[tokyo,hakata,naha,osaka,sapporo,tokyo]    3021
[tokyo,naha,sapporo,osaka,hakata,tokyo]    3904
[tokyo,naha,sapporo,hakata,osaka,tokyo]    3832
[tokyo,naha,osaka,sapporo,hakata,tokyo]    3840
[tokyo,naha,osaka,hakata,sapporo,tokyo]    3407
[tokyo,naha,hakata,sapporo,osaka,tokyo]    3349
[tokyo,naha,hakata,osaka,sapporo,tokyo]    2988
false.
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
				
						[4] 27 ?- solve_salesman.
 3 ?- solve_salesman.
[tokyo,sapporo,osaka,hakata,naha,tokyo]    2988
[tokyo,sapporo,osaka,naha,hakata,tokyo]    3021
[tokyo,sapporo,hakata,osaka,naha,tokyo]    3407
[tokyo,sapporo,hakata,naha,osaka,tokyo]    2949
[tokyo,sapporo,naha,osaka,hakata,tokyo]    3504
[tokyo,sapporo,naha,hakata,osaka,tokyo]    3013
[tokyo,osaka,sapporo,hakata,naha,tokyo]    3349
[tokyo,osaka,sapporo,naha,hakata,tokyo]    3446
[tokyo,osaka,hakata,sapporo,naha,tokyo]    3832
[tokyo,osaka,hakata,naha,sapporo,tokyo]    3013
[tokyo,osaka,naha,sapporo,hakata,tokyo]    3865
[tokyo,osaka,naha,hakata,sapporo,tokyo]    2949
[tokyo,hakata,sapporo,osaka,naha,tokyo]    3840
[tokyo,hakata,sapporo,naha,osaka,tokyo]    3865
[tokyo,hakata,osaka,sapporo,naha,tokyo]    3904
[tokyo,hakata,osaka,naha,sapporo,tokyo]    3504
[tokyo,hakata,naha,sapporo,osaka,tokyo]    3446
[tokyo,hakata,naha,osaka,sapporo,tokyo]    3021
[tokyo,naha,sapporo,osaka,hakata,tokyo]    3904
[tokyo,naha,sapporo,hakata,osaka,tokyo]    3832
[tokyo,naha,osaka,sapporo,hakata,tokyo]    3840
[tokyo,naha,osaka,hakata,sapporo,tokyo]    3407
[tokyo,naha,hakata,sapporo,osaka,tokyo]    3349
[tokyo,naha,hakata,osaka,sapporo,tokyo]    2988
false.
					
				
			
		

 
2900km以下の経路は存在しないようですね。
今回は経路が4!とおりで網羅が簡単だったけど、実際の問題はこれよりうんと複雑だろう。

自分は健康診断の会社で９年間働いていたのですが、いろいろな会社を回る健診バスの運行経路を決めるのは道路状況やリソース(人、機械)の問題もありかなり複雑そうでした。
					

		
		
			This entry was posted in PROLOG on 2016年5月2日 by koyahata.								

	


	
				
			
						
				小町算のパズルを制約論理プログラムとＤＣＧを使用して解く
			
										
					Leave a reply				

					


				
			自分がPrologの勉強のために参考にしているM.Hiroiさんのページで掲載されている小町算の問題を、広井さんの解法とは異なり制約論理プログラミングと最近勉強したDCGを使用して解いてみました。

(参照：http://www.geocities.jp/m_hiroi/prolog/prolog14.html)
問題：

小町算

1 から 9 までの数字を順番に並べ、間に + と – を補って 100 になる式を作ってください。

例：1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100
プログラム


		
		
			
			

			
			:-use_module(library(clpfd)).

solve_komachi:-
	phrase(komachi(RetNumList),[1,2,3,4,5,6,7,8,9],[]),
	length(RetNumList,Len),
	length(SignLst,Len),
	SignLst ins -1\/1,
	SignLst = [1 | Rest],
	maplist(mul,RetNumList,SignLst,SignedNumList),
	sum(SignedNumList,#=,100),
	label(SignedNumList),
	write(SignedNumList),nl.
	 
mul(A,B,C):-
	C #= A*B.
	
komachi([])-->[].
komachi([LeftListNum|RestNumList])-->{between(1,9, Len),length(LeftList,Len)},LeftList,{tonum(LeftList,LeftListNum)},komachi(RestNumList).

tonum(List,Num):- 
	length(List,Digit),
	tonum(List,Num,Digit).

tonum([Num],Num,1).
tonum([First|Rest],Num,Digit):-
	ThisDigitNum is First * 10 ^(Digit - 1),
	NextDigit is Digit - 1,
	tonum(Rest,RestNum,NextDigit),
	Num is ThisDigitNum + RestNum.
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
				
						:-use_module(library(clpfd)).
 
solve_komachi:-
	phrase(komachi(RetNumList),[1,2,3,4,5,6,7,8,9],[]),
	length(RetNumList,Len),
	length(SignLst,Len),
	SignLst ins -1\/1,
	SignLst = [1 | Rest],
	maplist(mul,RetNumList,SignLst,SignedNumList),
	sum(SignedNumList,#=,100),
	label(SignedNumList),
	write(SignedNumList),nl.
	 
mul(A,B,C):-
	C #= A*B.
	
komachi([])-->[].
komachi([LeftListNum|RestNumList])-->{between(1,9, Len),length(LeftList,Len)},LeftList,{tonum(LeftList,LeftListNum)},komachi(RestNumList).
 
tonum(List,Num):- 
	length(List,Digit),
	tonum(List,Num,Digit).
 
tonum([Num],Num,1).
tonum([First|Rest],Num,Digit):-
	ThisDigitNum is First * 10 ^(Digit - 1),
	NextDigit is Digit - 1,
	tonum(Rest,RestNum,NextDigit),
	Num is ThisDigitNum + RestNum.
					
				
			
		

 
実行結果


		
		
			
			

			
			[7] 35 ?- solve_komachi.
[1,2,3,-4,5,6,78,9]
[1,2,34,-5,67,-8,9]
[1,23,-4,5,6,78,-9]
[1,23,-4,56,7,8,9]
[12,-3,-4,5,-6,7,89]
[12,3,4,5,-6,-7,89]
[12,3,-4,5,67,8,9]
[123,-4,-5,-6,-7,8,-9]
[123,4,-5,67,-89]
[123,45,-67,8,-9]
[123,-45,-67,89]
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
				
						[7] 35 ?- solve_komachi.
[1,2,3,-4,5,6,78,9]
[1,2,34,-5,67,-8,9]
[1,23,-4,5,6,78,-9]
[1,23,-4,56,7,8,9]
[12,-3,-4,5,-6,7,89]
[12,3,4,5,-6,-7,89]
[12,3,-4,5,67,8,9]
[123,-4,-5,-6,-7,8,-9]
[123,4,-5,67,-89]
[123,45,-67,8,-9]
[123,-45,-67,89]
					
				
			
		


					

		
		
			This entry was posted in PROLOG on 2016年4月27日 by koyahata.								

	


	
				
			
						
				広井さんのページ
			
										
					Leave a reply				

					


				
			自分はM.hiroiさんのページでPrologの基礎を学びその後Swi-Prologの英文マニュアルを読み制約論理プログラミングなど知ったのですが、広井さんにメールで制約論理プログラミングを紹介したら広井さんも興味を持たれたようで早速ホームページで取り上げられていました。
http://www.geocities.co.jp/SiliconValley-Oakland/1680/memo.html
僕の名前も紹介者として掲載されてました。ﾜｰｲ
					

		
		
			This entry was posted in PROLOG on 2016年4月27日 by koyahata.								

	

			
				Post navigation
				← Older posts
				Newer posts →




			
			
				
					検索:
					
					
				
			
				最近の投稿
		
					
				AWS Lightsail で tftp接続を行う
						
					
				Now I’m searching for remote jobs of overseas which can be done while living in Japan
						
					
				ECLiPSe CLPで2次元の板取り問題(2d cutting stock problem)を解く
						
					
				ECLiPSe CLPで美術館の警備員配置問題を解く
						
					
				PrologのLogical Loopの解説
						
					
				ECLiPSe CLPで輸送問題を解く
						
					
				ECLiPSe でユーザー定義の算術演算子を定義する
						
					
				ECLiPSe CLPで最小全域木を求める
						
					
				ECLiPSeで分枝限定法(branch and bound)ライブラリを用いてナップサック問題を解く
						
					
				ECLiPSe CLPのsearch/6のChoiceの実験
						
					
				ECLiPSe CLP の EPLEX ライブラリを用いて混合整数線形計画問題を解く
						
					
				ECLiPSe CLP の EPLEX ライブラリを用いて線形計画法の問題を解く
						
					
				機械の買い替え問題（Renewal Plan Problem)を解くプログラム
						
					
				グラフの最小カット(the Minimum Cut)を求める
						
					
				最大流問題(Maximum flow Problem)を解く
						
					
				Bellman-Ford’sアルゴリズムを用いてグラフの最短経路木(shortest path tree)を求める
						
					
				グラフの最短経路木(shortest path tree)を求める
						
					
				[Debian]LinuxでECLiPSe CLPをビルドする
						
					
				ECLiPSe の Nonogram Solver の解説
						
					
				Prologの差分リスト(difference list)に関して
						
					
				Project Euler 46
						
					
				CHRをGPUで実行させる論文を読みました。
						
					
				labelingに関して
						
					
				DOMINO PUZZLEソルバーの解説
						
					
				四角に切れ（パズル）を解くプログラム
						
					
				RUSH HOUR(パズル)を解くプログラム
						
					
				ペントミノを解くプログラム
						
					
				数独を解くプログラム
						
					
				Project Euler Problem 62
						
					
				Project Euler Problem 59
						
					
				Project Euler Problem 52
						
					
				Project Euler Problem79
						
					
				ドローン
						
					
				[Prolog] DCGで双方向性のある述語を作成
						
					
				[Prolog]最近の勉強
						
					
				C#のWPD(MTP)操作
						
					
				PrologでForループ
						
					
				発見
						
					
				Probrem 185 Number Mind
						
					
				Problem2　偶数のフィボナッチ数
						
					
				Problem 9 特別なピタゴラス数
						
					
				Problem 8 数字列中の最大の積
						
					
				Problem 7 10001番目の素数
						
					
				Problem 68 Magic 5-gon ring
						
					
				Problem 6 ２乗和の差
						
					
				Problem 5 最小公倍数
						
					
				Problem 44　五角数
						
					
				Problem 4 最大回文積
						
					
				Problem 35 循環素数
						
					
				Problem 3 最大の素因数
						
					
				Problem 11 格子内の最大の積
						
					
				Problem 10 二百万以下の素数の和
						
					
				Problem 1 3と5の倍数
						
					
				[Prolog]制約論理プログラミングへの条件追加と速度の向上に関して
						
					
				[Prolog]川渡り問題を解く
						
					
				[Prolog]演算子のカンマとそうでないカンマ、ドット演算子と演算子でないドット（ピリオド）
						
					
				[Prolog]存在記号∃を表現する
						
					
				[Prolog]動的に述語定義する
						
					
				[prolog]attributed_variable に関して
						
					
				[PROLOG] compound term
						
					
				Art of Prolog
						
					
				簡単な巡回セールスマン問題をPrologで解く
						
					
				小町算のパズルを制約論理プログラムとＤＣＧを使用して解く
						
					
				広井さんのページ
						
					
				前回からの続き　Zebra Puzzleを制約論理プログラミングで解く2
						
					
				ゼブラパズル(Zebra Puzzle)を制約論理プログラミングで解く
						
					
				前回から続き　リードリレーの実験
						
					
				中国の安い対局時計の手番スイッチの仕組み
						
					
				みなみとかおりの数字当て問題を制約論理プログラミングで解く
						
					
				うそつき娘問題を制約プログラミングで解く
						
					
				SWI-Prologの制約論理ライブラリ
						
					
				地球の丸さを知覚できるか
						
					
				ubuntuにopen-cvを入れる
						
					
				MS-ACCESSの新規案件対応中
						
					
				不動産プラグイン
						
					
				mod_rewriteが効かない
						
					
				ブログ開始