1

我是 Prolog 编程的新手。所以我想知道以下。我知道在 Prolog 中使用 Cut (!)。有人可以解释一下，Prolog 中 Not 的使用，何时以及如何使用 Not 以及如何在不使用 Cut 的情况下重写以下内容并避免回溯。（仅使用谓词）

choose (0,_,[]) :- !.
choose (N,[H|T], [H|R]) :- M is N-1, Choose (M,T,R).
choose(N, [_|T],R) :- Choose(N,T,R)

并解释我如何重写以下内容（仅使用谓词）

chooseAll(N,L,Res) :-
    chooseAll(N,L,[],Res).

chooseAll(N,L,Seen,Res):-
    choose(N,L,R),
    not(member(R,Seen)),
    !,
    chooseAll(N,L,[R|Seen],Res).
chooseAll(_,_,Res,Res).
4

2 回答 2

3

not/1是一个带有一个参数的谓词：目标（在您的示例中member(R,Seen)）。

它根据否定作为有限失效原理工作。这意味着not(P)成功，因为 Prolog无法满足P. 换句话说，如果您P直接查询 Prolog，它将返回false. 然而，如果 Prolog 进入无限循环P，它也将永远循环在not(P).

另一方面，如果P成功（无论是否统一），not(P)都会失败。

P由于只有在is时才成功false，所以不会在 中进行统一not。如果P成功，not(P)则失败，因此所做的任何统一都将撤消。

所以not(member(R,Seen))检查是否R不是的成员Seen。如果Seen是变量，not(member(R,Seen))将失败。GivenR是一个变量，如果不是一个空列表，not(member(R,Seen))就会成功。Seen

另一方面，削减!与 无关not/1。在您的示例中，它仅意味着如果not(member(R,Seen)成功，将执行剪切，因此chooseAll/1在这种情况下不会完成最后的重做。

那么chooseAll/4谓词是如何工作的呢？它被称为Seen空列表。在第一个子句中，我们首先调用choose(N,L,R)which 生成一个数字组合到一个列表中R。我们希望防止一次又一次地生成相同的列表，因此接下来使用not(member(R,Seen))调用来检查是否R已经在Seen. 对于第一个结果，情况并非如此，因此我们 cut!以防止系统回溯并选择最后一个子句和 next 我们chooseAll递归调用但R添加到Seen列表中。

在递归调用中，我们再次choose/3要求生成一个组合R并将其添加到已看到的列表中。但现在它将生成与第一次相同的结果：choose/3将为每个呼叫创建以相同顺序的答案。所以这意味着 Prolog 将回溯not(member(R,Seen))并要求choose/3生成下一个组合。该组合不会成为 的一部分Seen，因此会成功，因此我们将再次剪切并使用added tonot(member(R,Seen))进行递归调用。RSeen

这将继续进行，直到choose/3完全用尽并且无法提出R尚不属于Seen. 在这种情况下，Prolog 将回溯chooseAll/4谓词并执行最后一个谓词，从而将结果Res与Seen列表统一起来。

然而，这是一种低效的方法：对于我们生成的每个答案，我们将再次调用谓词，直到它生成一个新的答案。因此一个ISO谓词findall/3谓词。它会将谓词的所有结果放在一个列表中（而不是相反的顺序）。我们可以像这样使用它：

chooseAll(N,L,Res) :-
    findall(R,choose(N,L,R),Res).

注意：作为文档not/1指定：

如果Goal无法证明，则为真。保留仅用于兼容性。新代码应该使用\+/1.

所以你最好使用\+ member(R,Seen)它，因为它更容易记忆。

于 2017-08-04T19:06:50.363 回答
2

请让我们退后一步，考虑一些比如何使用一个或两个特定谓词（例如!/0or ）更普遍的问题not/1。

首先，让我们修复一些语法问题，并让您的原始代码如下所示：

选择（0，_，[]）：-！。
选择（N，[H|T]，[H|R]）：- M 是 N-1，选择（M，T，R）。
选择（N，[_|T]，R）：-选择（N，T，R）。

全选（N，L，Res）：-
    全选(N,L,[],Res)。

全选（N，L，Seen，Res）：-
    选择（N，L，R），
    不是（成员（R，Seen）），
    ！，
    全选(N,L,[R|Seen],Res)。
全选(_,_,Re​​s,Res)。

从这里开始，我应用了以下两个小改动：

  • 而不是not/1, 我使用,(\+)/1因为(\+)/1是 ISO 但不是.not/1
  • 而不是(is)/2，我使用 CLP(FD) 约束(#=)/2来宣传更新的语言结构，并明确说明在这种情况下我们仅对整数进行推理，而不是例如浮点数或其他类型的数字。将此视为保证额外的类型安全性。

我们获得了这两个小变化：

选择（0，_，[]）：-！。
选择（N，[H|T]，[H|R]）：- M #= N-1，选择（M，T，R）。
选择（N，[_|T]，R）：-选择（N，T，R）。

全选（N，L，Res）：-
    全选(N,L,[],Res)。

全选（N，L，Seen，Res）：-
    选择（N，L，R），
    \+ 成员（R，Seen），
    ！，
    全选(N,L,[R|Seen],Res)。
全选(_,_,Re​​s,Res)。

现在让我们开始吧！我渴望通过询问来尝试主要谓词：到底有哪些解决方案？

为了找出答案，我发布了所谓的最通用查询，其中所有参数都是新变量：

?- 全选(X, Y, Z)。
X = 0,
Z = [[]]。

什么？这个谓词只有一个解，对吧？正确的？

可能不是。

所以，我想得到更多关于这些基本问题的答案。为了获得它们，我进行了以下附加更改：

  • 我删除!/0.
  • 我曾经dif/2说过两个术语是不同的。
  • 我稍微重新排列了条款。
  • 我为那些仅在大于 0N #> 0时才适用的子句添加了约束。N

所以，我们有：

选择（0，_，[]）。
选择（N，[H|T]，[H|R]）：- N #> 0，M #= N-1，选择（M，T，R）。
选择（N，[_|T]，R）：- N＃> 0，选择（N，T，R）。

全选（N，L，Res）：-
    全选(N,L,[],Res)。

全选(_,_,Re​​s,Res)。
全选（N，L，Seen，Res）：-
    选择（N，L，R），
    maplist(dif(R), Seen),
    全选(N,L,[R|Seen],Res)。

现在我们有例如：

?- 全选(X, Y, Z)。
Z = [];
X = 0,
Z = [[]] ;
X = 1,
Y = [_1966|_1968]，
Z = [[_1966]] ;
X = 1,
Y = [_3214, _3220|_3222],
Z = [[_3220]，[_3214]]，
差异（_3220，_3214）；
X = 1,
Y = [_3560, _3566, _3572|_3574],
Z = [[_3572]，[_3566]，[_3560]]，
差异（_3572，_3560），
差异（_3572，_3566），
差异（_3566，_3560）。
X = 0,
Z = [[]]。

我把它作为一个练习来确定这个程序现在是否过于笼统、过于具体或两者兼而有之，并添加或删除必要的约束以仅获得所需的答案。

我想说明的要点是，坚持纯谓词可以帮助您获得更通用的程序。使用!/0and(\+)/1并没有帮助。为了避免在特定情况下回溯，同时保持谓词的通用性，例如使用新的谓词 if_/3。

于 2017-08-06T16:01:47.303 回答