在Jess in Action - Rule-Based Systems in Java(写于 10 多年前;我认为 Drools 是今天使用的系统?)一书中,Ernest Friedman-Hill 使用 Jess(一种 OPS5 风格)解决了下面给出的约束问题用Java编写的前向链生产系统。我想用 Prolog 解决它。
问题是:我能正确解决它吗?
问题
四个高尔夫球手站在发球台前,从左到右排成一排。每个高尔夫球手都穿着不同颜色的裤子;一个穿着红色裤子。美联储右边的高尔夫球手穿着蓝色裤子。乔排在第二位。鲍勃穿着格子裤。汤姆不在一号或四号位,他也没有穿那条丑陋的橙色裤子。
四个高尔夫球手将按什么顺序开球,每个高尔夫球手的裤子是什么颜色的?
这是斑马拼图的一个实例。另请参阅此演示文稿,以获得更复杂的解决方案的精美插图。
使用 Jess,作者 Ernest Friedman-Hill
使用 Jess 生产系统,代码如下。这来自上述书籍,为清楚起见,对变量进行了重命名。
工作记忆充满了从高尔夫球手到他们可能的位置和裤子颜色的 32 个链接。该find-solution
规则为满足约束的链接集触发。
这似乎很难考虑,因为人们不会测试“可能的世界”是否满足约束条件,而是选择一组满足约束条件的链接。目前尚不清楚这确实是一个人在寻找什么。
;; Templates for working memory, basically the links golfer<->pantscolor,
;; and golfer<->position.
(deftemplate pants-color (slot of) (slot is))
(deftemplate position (slot of) (slot is))
;; Generate all possible 'pants-color' and 'position' facts
;; 4 names, each with 4 pants-color: 16 entries
;; 4 names, each with 4 positions: 16 entries
;; This gives the 32 facts describing the links
(defrule generate-possibilities
=>
(foreach ?name (create$ Fred Joe Bob Tom)
(foreach ?color (create$ red blue plaid orange)
(assert (pants-color (of ?name) (is ?color))))
(foreach ?position (create$ 1 2 3 4)
(assert (position (of ?name) (is ?position))))))
;; The “find solution” rule forward-chains and prints out a solution
(defrule find-solution
;; There is a golfer named Fred, whose position is ?p_fred and
;; pants color is ?c_fred
(position (of Fred) (is ?p_fred))
(pants-color (of Fred) (is ?c_fred))
;; The golfer to Fred's immediate right (who is not Fred) is wearing
;; blue pants.
(position (of ?n&~Fred) (is ?p&:(eq ?p (+ ?p_fred 1))))
(pants-color (of ?n&~Fred) (is blue&~?c_fred))
;; Joe is in position #2
(position (of Joe) (is ?p_joe&2&~?p_fred))
(pants-color (of Joe) (is ?c_joe&~?c_fred))
;; Bob is wearing the plaid pants (so his position is not “n” either
;; because “n” has blue pants)
(position (of Bob) (is ?p_bob&~?p_fred&~?n&~?p_joe))
(pants-color (of Bob&~?n) (is plaid&?c_bob&~?c_fred&~?c_joe))
;; Tom isn't in position 1 or 4 and isn't wearing orange (and not blue
;; either)
(position (of Tom&~?n) (is ?p_tom&~1&~4&~?p_fred&~?p_joe&~?p_bob))
(pants-color (of Tom) (is ?c_tom&~orange&~blue&~?c_fred&~?c_joe&~?c_bob))
=>
(printout t Fred " " ?p_fred " " ?c_fred crlf)
(printout t Joe " " ?p_joe " " ?c_joe crlf)
(printout t Bob " " ?p_bob " " ?c_bob crlf)
(printout t Tom " " ?p_tom " " ?c_tom crlf crlf))
我在 Prolog 中的第一个解决方案
事实证明这是不优雅和笨拙的(见其他答案)
让我们寻找一个数据结构来描述解决方案,如下所示:选择一个列表,在每个位置都有一个“golfer”,具有“Name”和“Pants Color” [golfer(N0,C0),golfer(N1,C1),golfer(N2,C2),golfer(N3,C3)]
:。每个高尔夫球手也有列表中实际位置给出的从 0 到 3 的开球位置;位置没有像 中那样明确给出golfer(Name,Color,Position)
。
solution(L) :-
% select possible pants colors which must be pairwise different; for
% fast fail, we check often
is_pants_color(C0),
is_pants_color(C1),are_pairwise_different([C0,C1]),
is_pants_color(C2),are_pairwise_different([C0,C1,C2]),
is_pants_color(C3),are_pairwise_different([C0,C1,C2,C3]),
% select possible golfer names which must be pairwise different; for
% fast fail, we check often
is_name(N0),
% we know that joe is second in line, so we can plonck that condition
% in here immediately
N1 = joe,
is_name(N1),are_pairwise_different([N0,N1]),
is_name(N2),are_pairwise_different([N0,N1,N2]),
is_name(N3),are_pairwise_different([N0,N1,N2,N3]),
% instantiate the solution in a unique order (we don't change the order
% as we permute exhuastively permute colors and names)
L = [golfer(N0,C0),golfer(N1,C1),golfer(N2,C2),golfer(N3,C3)],
% tom is not in position one or four; express this clearly using
% "searchWithPosition" instead of implicitly by unification with L
search(tom,L,golfer(_,_,TomPosition)),
TomPosition \== 0,
TomPosition \== 3,
% check additional constraints using L
rightOf(fred,L,golfer(_,blue)),
search(bob,L,golfer(_,plaid,_)),
\+search(tom,L,golfer(_,hideous_orange,_)).
% here we stipulate the colors
is_pants_color(red).
is_pants_color(blue).
is_pants_color(plaid).
is_pants_color(hideous_orange).
% here we stipulate the names
is_name(joe).
is_name(bob).
is_name(tom).
is_name(fred).
% helper predicate
are_pairwise_different(L) :- sort(L,LS), length(L,Len), length(LS,Len).
% Search a golfer by name in the solution list, iteratively.
% Also return the position 0..3 for fun and profit (allows to express the
% constraint on the position)
% We "know" that names are unique, so cut on the first clause.
search(Name,L,golfer(Name,C,Pos)) :-
searchWithPosition(Name,L,golfer(Name,C,Pos),0).
searchWithPosition(Name,[golfer(Name,C)|_],golfer(Name,C,Pos),Pos) :- !.
searchWithPosition(Name,[_|R],golfer(Name,C,PosOut),PosIn) :-
PosDown is PosIn+1, searchWithPosition(Name,R,golfer(Name,C,PosOut),PosDown).
% Search the golfer to the right of another golfer by name in the list,
% iteratively. We "know" that names are unique, so cut on the first clause
rightOf(Name,[golfer(Name,_),golfer(N,C)|_],golfer(N,C)) :- !.
rightOf(Name,[_|R],golfer(N,C)) :- rightOf(Name,R,golfer(N,C)).
让我们运行这个:
?:- solution(L).
L = [golfer(fred, hideous_orange),
golfer(joe, blue),
golfer(tom, red),
golfer(bob, plaid)]