Prolog如何使用回溯来寻找解决方案？

Question

我有这个生成子集的序言代码。

subset([], []).

subset([E|Tail], [E|NTail]):-
     subset(Tail, NTail).

subset([_|Tail], NTail):-
     subset(Tail, NTail).

代码有效，但我不明白如何。我曾尝试使用跟踪来了解它如何找到解决方案，但我根本不明白。

如果有人可以一步一步地告诉我 prolog 如何为一个简单的查询找到解决方案，例如

subset([1,2,3],X).

那将是最有帮助的。

Answer 1

Prolog 试图证明 subset([1,2,3],X). 是一个事实。它通过尝试查看是否有任何谓词支持此目标来做到这一点。

最初它尝试 subset([], []). - 但没有成功，因为 [1,2,3] 无法与 [] 统一。

然后它会尝试 subset([E|Tail], [E|NTail]):- subset(Tail, NTail).。它可以与头部统一，所以现在它试图证明尾部。它试图证明 subset([2,3], NTail).

这导致证明 subset([3], NTail)（不同的 NTail）然后 subset([], NTail)（再次不同的 NTail）。现在它成功 subset([], []). - 终止 depth-first-search 现在它返回调用堆栈构建 X 的结果 - 即 [1|[2|[3|[]]]] 或 [1, 2, 3] .

结果是目标 ?- subset([1,2,3],X). 成功 [1, 2, 3]。

现在，如果您要求 Prolog 提供第二个答案，它会查看最后一个成功的谓词并假设它失败了。这就是目标 subset([], NTail)。没有可以成功实现该目标的谓词，因此它又返回了一步。它用 subset([E|Tail], [E|NTail]):- subset(Tail, NTail). 证明了 subset([3], NTail) 但现在它假设失败了所以它继续并尝试 subset([_|Tail], NTail):- subset(Tail, NTail). 成功了，并有效地删除了 3，所以它然后像以前一样继续继续证明目标。它最终导致 [1, 2].

如果您向 Prolog 询问另一个答案，它会继续使用这种方法，返回并找到最后成功的事情并假设它失败并继续。

最终你会得到这个结果：

[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]

Prolog如何使用回溯来寻找解决方案？

How does prolog uses backtracking to find solutions?

prolog

subset

backtracking