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

Question

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

subset([], []).

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

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

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

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

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

这将是最有帮助的。

标签： prologsubsetbacktracking

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([], []).- 这终止了深度优先搜索，现在它返回调用堆栈构建结果X- 这是[1|[2|[3|[]]]]or [1, 2, 3]。

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

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

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

最终你会得到这个结果：

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