Prolog:如何判断谓词是否是确定性的 [英] Prolog: How to tell if a predicate is deterministic or not

问题描述

因此，根据我对确定性谓词的了解，

So from what I understand about deterministic predicates:

确定性谓词= 1个解决方案

Deterministic predicate = 1 solution

不确定性谓词=多个解决方案

关于如何检测谓词是一个还是另一个，是否有任何类型的规则?就像看着搜索树，等等.

Are there any type of rules as to how you can detect if the predicate is one or the other? Like looking at the search tree, etc.

推荐答案

对于这些概念尚无明确的，普遍接受的共识.但是，它们通常是基于观察到的答案，而不是基于解决方案的数量.在某些情况下，这些概念与实现非常相关. 不确定"可能意味着:让选择点保持开放状态.有时是确定性的意思:甚至不会创建选择点.

There is no clear, generally accepted consensus about these notions. However, they are usually based rather on the observed answers and not based on the number of solutions. In certain contexts the notions are very implementation related. Non-determinate may mean: leaves a choice point open. And sometimes determinate means: never even creates a choice point.

要查看差异，请考虑目标length(L, 1).它有多少解决方案? L = [a]是一个，L = [23]是另一个...，但是所有这些解决方案都用一个答案替换紧凑地表示:L = [_]因此包含无限多个解决方案. 无论如何，在我所知道的所有实现中，length(L, 1)是一个确定的目标.

To see the difference, consider the goal length(L, 1). How many solutions does it have? L = [a] is one, L = [23] another... but all of these solutions are compactly represented with a single answer substitution: L = [_] which thus contains infinitely many solutions. In any case, in all implementations I know of, length(L, 1) is a determinate goal.

现在考虑目标repeat，该目标只有一个解决方案，但是答案很多.该目标被认为是不确定的.

Now consider the goal repeat which has exactly one solution, but infinitely many answers. This goal is considered non-determinate.

如果您对约束感兴趣，事情会变得更加进化.在library(clpfd)中，目标X #> Y, Y #> X没有解决方案，但仍然是一个答案.将此与repeat结合使用:无限多的答案，没有解决方案.

In case you are interested in constraints, things become even more evolved. In library(clpfd), the goal X #> Y, Y #> X has no solution, but still one answer. Combine this with repeat: infinitely many answers and no solution.

此外，目标append(Xs, Ys, [])仅有一个解决方案，也只有一个答案，尽管如此，在许多实现中它仍被认为是不确定的，因为在这些实现中，它留下了一个选择点.

Further, the goal append(Xs, Ys, []) has exactly one solution and also exactly one answer, nevertheless it is considered non-determinate in many implementations, since in those implementations it leaves a choice point open.

在理想的实现中，没有解决方案就不会有答案(false除外)，并且只有在有多个答案的情况下才会有不确定性.但是，在一般情况下，所有这些几乎都是无法决定的.

In an ideal implementation, there would be no answers without solutions (except false), and there would be non-determinism only when there is more than one answer. But then, all of this is mostly undecidable in the general case.

因此，每当您使用这些概念时，请确保其含义是什么级别.确切地说，是:多个答案，多个解决方案，不会让(不必要的)选择点敞开.

So, whenever you are using these notions make sure on what level things are meant. Rather explicitly say: multiple answers, multiple solutions, leaves no (unnecessary) choice point open.

这篇关于Prolog:如何判断谓词是否是确定性的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！