3

首先,很抱歉发布整个程序,但我不知道问题是我不知道哪些部分是不相关的。这是 SWI-Prolog 中相同逻辑难题的两种略有不同的实现,第一个成功,第二个失败,我找不到失败的原因。

谜题:

4 persons are having a diner:
Donna, Doreen, David, Danny

the woman (Donna,Doreen) are sitting vis-a-vis.
the men (David,Danny) are sitting vis-a-vis.

Each of them picked a unique meal and beverage.

1) Doreen sits next to the person that ordered risotto.
2) the salad came with a coke.
3) the person with the lasagna sits vis-a-vis the person with the milk.
4) david never drinks coffee.
5) donna only drinks water.
6) danny had no appetite for risotto.

who ordered the pizza?

我选择以下方法

table with positions:

  1
4 O 2
  3

domain: positions{1,2,3,4}
variables: persons, meals, beverages

首先是低效的后续实现:

solution(Pizza, Doreen, Donna, David, Danny) :-

    % assignment of unique positions to the variables
    unique(Doreen,Donna,David,Danny),
    unique(Lasagna,Pizza,Risotto,Salad),
    unique(Water,Coke,Coffee,Milk),

    % general setting
    vis_a_vis(Donna,Doreen),
    vis_a_vis(David,Danny),

    % the six constraints
    next_to(Doreen,Risotto),
    Salad = Coke,
    vis_a_vis(Lasagna,Milk),
    \+ David = Coffee,
    Donna = Water,
    \+ Danny = Risotto.



unique(X1,X2,X3,X4) :-
    pos(X1),
    pos(X2),
    \+ X1 = X2,
    pos(X3),
    \+ X1 = X3, \+ X2 = X3,
    pos(X4),
    \+ X1 = X4, \+ X2 = X4, \+ X3 = X4.

right(1,2).
right(2,3).
right(3,4).
right(4,1).

vis_a_vis(1,3).
vis_a_vis(3,1).
vis_a_vis(2,4).
vis_a_vis(4,2).

next_to(X,Y) :- right(X,Y).
next_to(X,Y) :- right(Y,X).

pos(1).
pos(2).
pos(3).
pos(4).

这有效并给出了正确的结果。但是当我尝试重新排序解决方案过程的条款以提高效率时(这是第二个实现)

solution(Pizza, Doreen, Donna, David, Danny) :-

    % general setting
    vis_a_vis(Donna,Doreen),
    vis_a_vis(David,Danny),

    % the six constraints
    Salad = Coke,
    vis_a_vis(Lasagna,Milk),
    \+ David = Coffee,
    Donna = Water,
    \+ Danny = Risotto,

    % assignment of unique positions to the variables
    unique(Doreen,Donna,David,Danny),
    unique(Lasagna,Pizza,Risotto,Salad),
    unique(Water,Coke,Coffee,Milk).

    %% all other predicates are like the ones in the first implementation

尝试加载文件时收到未分配的变量警告:

Warning: /home/pizza.pl:28:
Singleton variable in \+: Coffee

并且计算返回false。但它不应该返回相同的结果吗?我看不出有什么区别...

4

1 回答 1

1

警告是由于执行否定时 Coffe 和 Risotto 未绑定。如果您替换\+ David = Coffee,David \= Coffee,您将避免警告,但解决方案不能不会被计算。确实应该清楚的是,由于 Coffee 是未绑定的,所以 David \= Coffee 总是会失败。您可以使用 dif/2,该解决方案将起作用并且效率更高。我将 solution1/2 命名为您的第一个片段,并将 solution2/5 这个片段命名为(使用 dif/2):

solution2(Pizza, Doreen, Donna, David, Danny) :-

    % general setting
    vis_a_vis(Donna,Doreen),
    vis_a_vis(David,Danny),

    % the six constraints
    next_to(Doreen,Risotto), % note: you forgot this one
    Salad = Coke,
    vis_a_vis(Lasagna,Milk),
    dif(David, Coffee),
    Donna = Water,
    dif(Danny, Risotto),

    % assignment of unique positions to the variables
    unique(Doreen,Donna,David,Danny),
    unique(Lasagna,Pizza,Risotto,Salad),
    unique(Water,Coke,Coffee,Milk).

一个小测试:

?- time(aggregate_all(count,solution1(P,A,B,C,D),N)).
% 380,475 inferences, 0.058 CPU in 0.058 seconds (100% CPU, 6564298 Lips)
N = 8.

?- time(aggregate_all(count,solution2(P,A,B,C,D),N)).
% 10,626 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 4738996 Lips)
N = 8.
于 2014-11-16T16:23:13.750 回答