Prolog - 回溯

在本章中，我们将讨论 Prolog 中的回溯。回溯是一个过程，其中 prolog 通过检查不同谓词是否正确来搜索它们的真值。回溯术语在算法设计和不同的编程环境中非常常见。在 Prolog 中，在到达正确的目的地之前，它会尝试原路返回。当找到目的地时，它就会停下来。

让我们看看如何使用一棵树状结构进行回溯 -

假设A到G是一些规则和事实。我们从A出发，想要到达G。正确的路径是ACG，但一开始会从A到B，然后从B到D。当它发现D不是目的地时，它回溯到B，然后到E，再回溯到B，由于B没有其他孩子，则回溯到A，从而寻找G，最终在路径ACG中找到G。（虚线表示回溯。）所以当它找到 G 时，它就停止。

回溯如何运作？

现在我们知道了，Prolog 中的回溯是什么。让我们看一个例子，

注意- 当我们运行一些 prolog 代码时，回溯期间可能会有多个答案，我们可以按分号(;) 逐一获取下一个答案，这有助于回溯。否则，当我们得到一个结果时，它就会停止。

现在，考虑一种情况，两个人X和Y可以互相付款，但条件是男孩可以向女孩付款，所以X将是男孩，Y将是女孩。因此，对于这些，我们定义了一些事实和规则 -

知识库

boy(tom).
boy(bob).
girl(alice).
girl(lili).

pay(X,Y) :- boy(X), girl(Y).

以下是上述场景的说明 -

由于X将是一个男孩，所以有两个选择，每个男孩有两个选择爱丽丝和莉莉。现在让我们看看输出，回溯是如何工作的。

输出

| ?- [backtrack].
compiling D:/TP Prolog/Sample_Codes/backtrack.pl for byte code...
D:/TP Prolog/Sample_Codes/backtrack.pl compiled, 5 lines read - 703 bytes written, 22 ms

yes
| ?- pay(X,Y).

X = tom
Y = alice ?

(15 ms) yes
| ?- pay(X,Y).

X = tom
Y = alice ? ;

X = tom
Y = lili ? ;

X = bob
Y = alice ? ;

X = bob
Y = lili

yes
| ?- trace.
The debugger will first creep -- showing everything (trace)

(16 ms) yes
{trace}
| ?- pay(X,Y).
   1 1 Call: pay(_23,_24) ?
   2 2 Call: boy(_23) ?
   2 2 Exit: boy(tom) ?
   3 2 Call: girl(_24) ?
   3 2 Exit: girl(alice) ?
   1 1 Exit: pay(tom,alice) ?
   
X = tom
Y = alice ? ;
   1 1 Redo: pay(tom,alice) ?
   3 2 Redo: girl(alice) ?
   3 2 Exit: girl(lili) ?
   1 1 Exit: pay(tom,lili) ?
   
X = tom
Y = lili ? ;
   1 1 Redo: pay(tom,lili) ?
   2 2 Redo: boy(tom) ?
   2 2 Exit: boy(bob) ?
   3 2 Call: girl(_24) ?
   3 2 Exit: girl(alice) ?
   1 1 Exit: pay(bob,alice) ?
   
X = bob
Y = alice ? ;
   1 1 Redo: pay(bob,alice) ?
   3 2 Redo: girl(alice) ?
   3 2 Exit: girl(lili) ?
   1 1 Exit: pay(bob,lili) ?
X = bob
Y = lili

yes
{trace}
| ?-

防止回溯

到目前为止我们已经了解了回溯的一些概念。现在让我们看看回溯的一些缺点。有时，当我们的程序需要时，我们会多次编写相同的谓词，例如编写递归规则或制定一些决策系统。在这种情况下，不受控制的回溯可能会导致程序效率低下。为了解决这个问题，我们将使用Prolog 中的Cut。

假设我们有一些规则如下 -

双步功能

规则 1 &minnus; 如果 X < 3，则 Y = 0
规则 2 + 如果 3 <= X 且 X < 6 则 Y = 2
规则 3 &minnus; 如果 6 <= X 则 Y = 4

在 Prolog 语法中我们可以这样写：

f(X,0) :- X < 3. % 规则 1
f(X,2) :- 3 =< X, X < 6. % 规则 2
f(X,4) :- 6 =< X. % 规则 3

现在，如果我们提出一个问题 f (1,Y), 2 < Y。

第一个目标 f(1,Y) 将 Y 实例化为 0。第二个目标变为 2 < 0，失败。Prolog 尝试回溯两个没有成果的替代方案（规则 2 和规则 3）。如果我们看得更近，我们可以观察到 -

这三个规则是互斥的，最多其中一个会成功。
一旦其中一个成功，尝试利用其他人就毫无意义，因为他们注定会失败。

所以我们可以使用cut来解决这个问题。可以使用感叹号来表示剪切。序言语法如下 -

f (X,0) :- X < 3, !. ％规则1
f (X,2) :- 3 =< X, X < 6, !。% 规则 2
f (X,4) :- 6 =< X. % 规则 3

现在，如果我们使用相同的问题， ?- f (1,Y), 2 < Y。Prolog 选择规则 1，因为 1 < 3 并且失败，目标 2 < Y 失败。Prolog 将尝试回溯，但不会超出标记的点！程序中不会生成规则2和规则3。

让我们在下面的执行中看到这一点 -

程序

f(X,0) :- X < 3.              % Rule 1
f(X,2) :- 3 =< X, X < 6.   % Rule 2
f(X,4) :- 6 =< X.             % Rule 3

输出

| ?- [backtrack].
compiling D:/TP Prolog/Sample_Codes/backtrack.pl for byte code...
D:/TP Prolog/Sample_Codes/backtrack.pl compiled, 10 lines read - 1224 bytes written, 17 ms

yes
| ?- f(1,Y), 2<Y.

no
| ?- trace
.
The debugger will first creep -- showing everything (trace)

yes
{trace}
| ?- f(1,Y), 2<Y.
   1 1 Call: f(1,_23) ?
   2 2 Call: 1<3 ?
   2 2 Exit: 1<3 ?
   1 1 Exit: f(1,0) ?
   3 1 Call: 2<0 ?
   3 1 Fail: 2<0 ?
   1 1 Redo: f(1,0) ?
   2 2 Call: 3=<1 ?
   2 2 Fail: 3=<1 ?
   2 2 Call: 6=<1 ?
   2 2 Fail: 6=<1 ?
   1 1 Fail: f(1,_23) ?
   
(46 ms) no
{trace}
| ?-

让我们看看使用 cut 的相同效果。

程序

f(X,0) :- X < 3,!.            % Rule 1
f(X,2) :- 3 =< X, X < 6,!. % Rule 2
f(X,4) :- 6 =< X.             % Rule 3

输出

| ?- [backtrack].
   1 1 Call: [backtrack] ?
compiling D:/TP Prolog/Sample_Codes/backtrack.pl for byte code...
D:/TP Prolog/Sample_Codes/backtrack.pl compiled, 10 lines read - 1373 bytes written, 15 ms
   1 1 Exit: [backtrack] ?
(16 ms) yes
{trace}
| ?- f(1,Y), 2<Y.
   1 1 Call: f(1,_23) ?
   2 2 Call: 1<3 ?
   2 2 Exit: 1<3 ?
   1 1 Exit: f(1,0) ?
   3 1 Call: 2<0 ?
   3 1 Fail: 2<0 ?
no
{trace}
| ?-

否定即失败

这里我们将在条件不满足时执行失败。假设我们有一个陈述，“玛丽喜欢除了蛇之外的所有动物”，我们将在 Prolog 中表达这一点。

如果陈述是“玛丽喜欢所有动物”，那就非常简单直接了。在这种情况下，我们可以写“如果 X 是动物，玛丽喜欢 X”。在序言中，我们可以将此语句写为 likes(mary, X) := Animal(X)。

我们的实际陈述可以表示为 -

如果 X 是蛇，那么“玛丽喜欢 X”就不是真的
否则，如果 X 是动物，那么玛丽喜欢 X。

在序言中我们可以将其写为 -

喜欢（玛丽，X）：- 蛇（X），！，失败。
喜欢（玛丽，X）：- 动物（X）。

“失败”语句导致失败。现在让我们看看它在 Prolog 中是如何工作的。

程序

animal(dog).
animal(cat).
animal(elephant).
animal(tiger).
animal(cobra).
animal(python).

snake(cobra).
snake(python).

likes(mary, X) :- snake(X), !, fail.
likes(mary, X) :- animal(X).

输出

| ?- [negate_fail].
compiling D:/TP Prolog/Sample_Codes/negate_fail.pl for byte code...
D:/TP Prolog/Sample_Codes/negate_fail.pl compiled, 11 lines read - 1118 bytes written, 17 ms

yes
| ?- likes(mary,elephant).

yes
| ?- likes(mary,tiger).

yes
| ?- likes(mary,python).

no
| ?- likes(mary,cobra).

no
| ?- trace
.
The debugger will first creep -- showing everything (trace)

yes
{trace}
| ?- likes(mary,dog).
   1 1 Call: likes(mary,dog) ?
   2 2 Call: snake(dog) ?
   2 2 Fail: snake(dog) ?
   2 2 Call: animal(dog) ?
   2 2 Exit: animal(dog) ?
   1 1 Exit: likes(mary,dog) ?
   
yes
{trace}
| ?- likes(mary,python).
   1 1 Call: likes(mary,python) ?
   2 2 Call: snake(python) ?
   2 2 Exit: snake(python) ?
   3 2 Call: fail ?
   3 2 Fail: fail ?
   1 1 Fail: likes(mary,python) ?
   
no
{trace}
| ?-