-1

我正在使用 SWI Prolog 为大学考试学习 Prolog，我对以下问题的两种不同解决方案之间的差异有一些疑问：

定义子句count(X, L, NumX)，其中 X 是一个原子，L 是一个列表，NumX 是 X 在 L 中出现的次数。

这是第一个解决方案：

count0(_,[],0).

count0(A, [A|Tail], N) :-
            count0(A,Tail,N1), % L'elemento cercato appare N1 volte nella sottolista
                N is N1+1.     % N vale N1+1

count0(A, [B|Tail], N) :-
            A\=B,            % A è diverso da B
        count0(A,Tail,N). % N è il numero di occorrenze di A nella sottolista

这是第二种解决方案：

count1(_,[],0).

count1(A, [A|Tail], N) :- !,
                      count1(A, Tail, N1),
              N is N1+1.

count1(A, [_|Tail], N) :- count1(A, Tail, N).

我的问题是我不明白 CUT 在第二个版本中扮演什么角色

我知道 CUT 可以防止在放置 CUT 的特定点回溯。

程序的第一个版本在第二条规则中检查 A 是否与 B 不同（我需要这个吗？如果第一条规则失败，则意味着 A 不与列表的 HEAD 统一，因此列出它与 A 中的元素不同）

第二个版本不在第二条规则中执行此检查，而是在第一条规则中进行了删减......

这可能取决于（在第二个版本中）如果我不阻止回溯发生的事实：在那之后，Prolog 给我第一个（正确的）响应，如果我强制回溯使用 ; 发生使用第二条规则：

count1(A, [_|Tail], N) :- count1(A, Tail, N).

在计算中采用不同的分支，在那个分支中我没有 N 是 N+1 吗？

4

1 回答 1

1

第一个版本在第二个子句中留下一个选择点，而第二个版本在进入第二个子句时提交（带有剪切）该子句。

第一个版本需要明确检查该项目与列表头部不同，因为在回溯时，无论第二个子句之前是否成功，都会执行第三个子句。

如果您使用一个简单的输入列表（比如 1 个元素）来跟踪这两个过程，您可以自己看到它。

?- count0(a,[a], Count).

您的程序的第一个版本将项目与列表的头部匹配，并执行递归。但是，如果需要，它将在那里留下一个选择点以查看其他替代方案。然后递归由于基本情况（空列表）而结束，你得到Count=1的结果。

如果您现在向 prolog 询问其他替代方案，它仍然具有该选择点，因此它将尝试 thirc 子句。如果您不明确检查 A 和 B 是否不同，它将递归调用自身（再次使用空列表）并返回Count=0这是错误的答案！

现在，您的程序的第二个版本（使用剪辑的那个）。当 prolog 进入带有 item a 的第二个子句时，它与 cut 一起提交，因此它不会留下选择点。现在您进行递归并以Count=1的正确结果结束。

如果你现在向 prolog 询问其他替代方案，它会说没有什么需要检查的了。作为剪切的结果，不再需要检查 A 和 B 是否不同，因为您确定它们会不同，否则第二个子句将被提交，而第三个子句将不会被测试。

于 2013-04-10T16:00:20.237 回答