获得谓词解析的顺序

问题描述 投票：5回答：4

看看以下目标（我使用来自Markus Triska的clpfd的swi-prolog）：

result(Input,Result) :-
    Input #> 10,
    Result=decline.
result(Input,Result) :-
    Input in 0..20,
    Result=offer.

可能的查询如下所示：

?- result(15,B).
B = decline ;
B = offer.

我想添加订单或某种解决方案优先级。如果“下降”是对Input=15的有效回应，则不应再考虑第二个目标，因此只有B=decline是解决方案而不是B=offer。

我知道我可以添加一个!/0然后反过来不会工作。给我这个谓词的所有可能答案。

考虑到这个例子，Result=offer应该只适用于Input 0..10，因为否则较高的先前下降目标应该触发。

当我尝试在谓词中考虑订单时，我是否认为太迫切了？

prolog clpfd
4个回答
6
投票

这里有几个问题，让我们先从最明显的开始：

建模问题

你有一个关系（result/2可能不是最好的名字），这个关系应该在decline和当offer应该是真的时建模。在阅读你的课程之前，我更喜欢问Prolog：

?- result(X, decline), result(X, offer).
X in 11..20 ;
false.

因此，对于从11到20的值，您的关系是模糊的。如果您想做出决定，请先修复此关系。实际上，我会先说

  • 关系的更好名称，表明它是一种关系
  • 没有必要的措辞（如Input或命令）
  • 更紧凑的配方，你的程序中不需要这么多的(=)/2目标。相反，你可以这样写：
heigth_decision(I, decline) :-
   I #< 10.

CLP中的答案和成功与解决方案

然后还有另一个更基本的问题。这实际上要严重得多，因为到目前为止给出的所有SO答案完全忽略了这一方面。它是关于答案和成功的概念，另一方面是解决方案的概念。

当您在Prolog中询问查询时 - 您得到的是一个答案。这样的答案可能包含解决方案，如答案L = [_,_]，其中包含无限多的解决方案。或者答案可能只包含一个像Decision = decline这样的解决方案。但是如果你使用像library(clpfd)这样的约束，那么还有更多。

您现在可以获得有限的许多解决方案：

?- abs(X) #< 3.
X in -2..2.

或无限多：

?- X #> Y.
Y#=<X+ -1.

但是你也可以得到一个解决方案，它看起来不像一个：

?- 2^X #= 1.
2^X#=1.

所以，重申一下：我们在整数中只有一个解决方案，但对于Prolog来说，这太复杂了。我们得到的答案是：答案是：是的，这一切都是真的，只要这一切都是真实的。

更糟糕的是，有时我们会得到不包含任何解决方案的答案。

?- X^X#=0.
X^X#=0.

如果Prolog足够聪明，它会回答false。但它并不总是那么聪明，仅仅因为你可以很容易地制定不可判定的问题。这样的答案有时被称为不一致。德国概念Scheinlösung（假的解决方案，但具有较少的负面含义）传达了这个想法更好一点。

所以答案可能包含解决方案，但有些答案根本不包含解决方案。因此，目标的成功不能被视为解决方案的存在！也就是说，所有SO-answers建议某种提交为（;）/ 2 - if-then-else，一次/ 1或！/ 0都是不正确的，如果他们将成功作为解决方案。要看到这一点，请尝试使用：

?- X^X#=0, result(X,decline).
X in 11..sup,
X^X#=0 ;
false.

?- X^X#=0, result(X,offer).
X in 0..20,
X^X#=0.

那你怎么能确定什么呢？

  • 你可以依靠目标的失败。
  • 你可以试试labeling/2，但这只适用于有限域。
  • 您可以使用call_residue_vars/2和copy_term/3来确定是否存在“悬挂”的限制
  • 不幸的是，你不能完全依赖于SWI的顶层，它隐藏了与答案中的变量无关的约束。只有SICStus才能正确显示它们。
2
投票

困扰我的部分是当你说“反过来不行”时。你为什么要反过来？

这是确定性搜索的一个明显案例，在Prolog中这样做的方法就是削减。如果满足第一条规则，则不要保持其他分支机构打开。或者，您可以使您检查的范围相互排斥。

如果您不仅仅是搞乱并且您正在尝试实施严肃的事情，我建议您阅读优先级规则和远程反应规则。您应该能够找到构建在Prolog之上的框架，可以用来解决您的问题，而无需重新发明轮子。

1
投票

谓词顺序它是Prolog程序的重要组成部分。那是因为证明搜索以严格定义的顺序进行，应用SLD resolution。

你的谓词给出了合理的结果：

?- result(X,Y).
Y = decline,
X in 11..sup ;
Y = offer,
X in 0..20.

而不是切入结果/ 2，你可以在调用时使用一次/ 1，保留适用于一般用途的定义。

?- once(result(X,Y)).
Y = decline,
X in 11..sup.
0
投票

建设性否定的一些想法可以在这里提供帮助。

理论

有一种简单的方法可以进行逻辑切割。特别是对于约束，因为约束通常是否定完成。因此，如果您有约束C，您可以通常使用以下属性找到约束C'：

C' <=> ~C

在两个条款中强加优先权，内容如下：

p :- C, q.
p :- r

只需执行以下操作：

p :- C, q.
p :- C', r.

如果您的约束求解器提供了一个具体化的否定，例如(#\)/1，您甚至可以为此定义一个运算符：

:- op(1050,xfy,#?).
:- op(1100,xfy,#:).
(A #? B #: C) :- (A, B); (#\ A, C).

然后写下面的内容：

p :- C #? q #: r.

让我们将此策略应用于您的示例：

例

您的代码目前如下所示：

result(Input, Result) :-
    Input #> 10,
    Result = decline.
result(Input, Result) :-
    Input in 0..20,
    Result = offer.

然后执行以下操作：

result(Input, Result) :-
    Input #> 10,
    Result = decline.
result(Input, Result) :-
    Input #=< 10, Input in 0..20,
    Result = offer.

这是一个示例运行：

?- result(15, X).
X = decline ;
false.

?- result(8, X).
X = offer.

现在使用(#?)/2，例如可以在SWI-Prolog中使用，因为CLP（FD）库支持具体化。假设我们已经咨询了CLP（FD）库，然后如上所述定义了(#:)/2：

 result(Input, Result) :-
    Input #> 10 
    #? 
       Result = decline 
    #: 
       Input in 0..20,
       Result = offer.

这是一个示例运行：

?- result(15, X).
X = decline ;
false.

?- result(8, X).
X = offer.

放弃

(#?)/2和(#:)/2的后来语法受Java if-then-else运算符(?)/2和(:)/2的启发。由于我们无法覆盖或扩展定义(;)/2，因此无法使用更多Prolog启发的语法。

有关具体化的更多信息，请参阅here部分A.8.4具体化。我们没有做的是在CLP（FD）if-then-else的定义中重新理解连接和析取，从那以后，其他部分可能包含其他目标，然后是CLP（FD）约束。

再见

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.