swi-prolog在析取(或)为第一个正确值后不会停止

问题描述 投票:0回答:1

我(Prolog绝对是新手,请尝试从Prolog讲起)。这是swi-prolog中的圣诞老人示例:

gives(santa,leonard,book).
gives(santa,adrian,game).
gives(santa,adrian,smartmax).

likes(leonard,lego).
likes(adrian,lego).
likes(adrian,book).

age(leonard,6).
age(adrian,4).

jealous(C1,C2) :- aggregate_all(count, gives(santa,C1,X), N1), 
  aggregate_all(count, gives(santa,C2,X), N2),
  N1 < N2,
  true.

jealous(C1,C2) :- findall(G, 
    (owns(C2,G), 
     likes(C1,G), 
     not(owns(C1,G))
    ), 
    Gifts),
  length(Gifts,NGifts),
  NGifts > 0,
  true.

这按预期工作:

?- jealous(adrian,leonard).
true.

但是,当我在代码中颠倒两个jealous谓词的顺序时:

?- jealous(adrian,leonard).
true ;
false.

这很奇怪:我认为jealous子句的行为会是“或”:只要其中一个结果为真,就不应再进行任何处理。所以我想知道:如何使它真正表现为“或”:如果任何jealous规则为真,则应返回true,在所有其他情况下为false 。我不希望“下一个结果”。我只需要1个结果:truefalse

我在做什么错? (可能有几件事,所以请启发我:))。

Thx。

prolog prolog-toplevel
1个回答
0
投票

按照子句的顺序,Prolog的搜索首先尝试匹配第一个子句:

jealous(C1,C2) :- aggregate_all(count, gives(santa,C1,X), N1), 
  aggregate_all(count, gives(santa,C2,X), N2),
  N1 < N2.
  % the final true is unnecessary

该子句计算出adrian有2个礼物和leonard 1,因此N1

?- jealous(adrian,leonard).
true.

至此,所有子句都已尝试,没有其他替代路径可尝试解析查询,因此在这里结束。

如果子句被颠倒,则首先尝试成功的子句,并给出解决方案:

?- jealous(adrian,leonard).
true

但是存在尚未尝试的第二个子句,因此搜索算法为您提供了返回以穷尽该第二个选项的选项。您要执行的操作:

;
false.

尝试第二个子句并像以前一样失败,但是在第一个子句已经解决了查询之后才这样做。

行为上的差异也归因于该算法如何优化其选择点记录。回溯是资源密集型的,Prolog算法通过从选择点堆栈中丢弃确定性解决方案来对此进行优化。也就是说,如果某处有一个声明

NGifts > 0

显然,如果知道NGifts,只有一个可能的解决方案(无关紧要),此时的回溯不会以其他证明返回。因此,该语句是确定性的,因此从选择堆栈中将其丢弃-已探索了其唯一的解决方案。

当按照您的问题对子句进行排序时,在都对这两个子句进行研究并给出解决方案时,堆栈中没有选择点,因此定理证明者退出。但是,如果您交换它们,则在尝试第二个子句之前会在第一个子句中找到解决方案,因此,存在第二个嫉妒子句会为您提供一个探索的选择点。]

[如果您需要控制这种行为,并且不需要确定小男孩相互嫉妒的情况,则可以强制Prolog'删除'选择点:

jealous(C1,C2) :-
  findall(G, 
    (owns(C2,G), 
     likes(C1,G), 
     not(owns(C1,G))
    ), 
    Gifts),
  length(Gifts,NGifts),
  NGifts > 0,
  !. % cut: if this clause gets so far, later clauses do not need to be explored

jealous(C1,C2) :-
  aggregate_all(count, gives(santa,C1,X), N1), 
  aggregate_all(count, gives(santa,C2,X), N2),
  N1 < N2.

在此示例中,这会使两个程序的行为相同。我将“谨慎对待削减”的讨论留给评论和其他问题。

热门问题
推荐问题
最新问题