3

我有这个例子：

descend(X,Y)  :-  child(X,Y). 
descend(X,Y)  :-  child(X,Z), descend(Z,Y).

child(anne,bridget). 
child(bridget,caroline). 
child(caroline,donna).

它很好用，我理解。这是一个小练习的解决方案。我的解决方案是相同的，但正在改变：

下降（X，Y）：-下降（X，Z），下降（Z，Y）。

也就是说，在第二条规则中改变childfor 。descenddescend

如果我descend(X, Y).在第一个解决方案中查询，我会得到：

?- descend(X, Y).
X = anne,
Y = bridget ;
X = bridget,
Y = caroline ;
X = caroline,
Y = donna ;
X = anne,
Y = caroline ;
X = anne,
Y = donna ;
X = bridget,
Y = donna ;
false.

哪个是对的。但是，如果我使用相同的解决方案进行查询，我会得到：

?- descend(X, Y).
X = anne,
Y = bridget ;
X = bridget,
Y = caroline ;
X = caroline,
Y = donna ;
X = anne,
Y = caroline ;
X = anne,
Y = donna ;
ERROR: Out of local stack

它没有说X = bridget,Y = donna ;，它也溢出。我明白为什么它会溢出。我不明白的是为什么它没有找到最后的关系。是因为溢出吗？如果是这样，为什么？（为什么知识库这么小，堆栈那么大？）。

如果我查询descend(bridget, donna)它的答案yes。

我在想象探索树时遇到问题......

除了那个问题，我猜原来的解决方案效率更高（忽略我的最后进入无限循环的事实），不是吗？

谢谢！

4

1 回答 1

6

我在想象探索树时遇到问题......

是的，这在 Prolog 中相当困难。如果你有一个更大的数据库，那就更糟了！但大多数时候没有必要设想非常精确的搜索树。相反，您可以使用几个非常强大的概念。

记住您是如何制定查询的。您一个接一个地查看了一个解决方案。但是您真正感兴趣的是查询是否终止的问题。您可以在不查看解决方案的情况下添加false.

?- 下降（X，Y），假。
错误：超出本地堆栈

这个查询永远不会是真的。它可能失败、溢出或循环，或产生另一个错误。剩下的是一个非常有用的概念：通用终止或在这种情况下不终止。

这可以扩展到您的实际程序：

下降（X，Y）：-假，孩子（X，Y）。
下降（X，Y）：-下降（X，Z），假，下降（Z，Y）。

如果这个称为没有终止，那么您的原始程序也不会终止。看看你程序的这个悲惨的剩余部分！甚至child/2不再存在。因此我们可以得出结论，child/2不影响不终止！Y只发生一次。并且X永远不会导致失败。从而永不descend/2终止！

所以这个结论比仅仅关于特定搜索树的陈述要笼统得多。这是关于他们所有人的声明。

如果您仍然想推理解决方案的非常精确的顺序，您将不得不进入实际执行的非常血腥的过程。但是为什么要打扰呢？它非常复杂，特别是如果您的child/2关系包含循环。很有可能你会混淆事物并建立不准确的理论（至少我做过）。不需要另一个货物崇拜。一方面，我已经放弃“逐步了解”如此无数的细节。我不会错过它。

于 2017-03-12T15:35:20.780 回答