本文介绍了递归谓词中的回溯的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

假设我们有以下谓词(这是来自 在 Prolog 中编程):

[F0] isInteger(0).[F1] isInteger(X):- isInteger(Y), X 是 Y+1.
  1. 查询的第一个结果是Integer(R),标记放在F0,会返回R=0

  2. 如果用户按下;,标记放置在 F1,我们移动到 subgoal(isInteger(Y),满足 F0) 和 R=1.

我明白了上面的内容.下面是我的问题:

  1. 如果用户按下;再次,标记在哪里?搜索如何进行以返回 R=2?我试图理解这本书第 78-79 页中的图像,但我不清楚.我发现的在线教程不处理存在递归的回溯.

我正在寻找任何解释存在递归时回溯的教程,希望能提供有助于我理解的堆栈内容图像.

先谢谢你苏珊

解决方案

通过使用图像了解回溯和递归适用于非常小的示例,但不适用于更大的程序.此外,通过逐步执行程序,您很容易错过最有趣的属性.幸运的是,还有比这更好的概念.让我们以你的例子isInteger/1.

解决方案/答案集

您的主要兴趣是确保您描述的是正确的事情.在这里,第二条规则最有趣.按照箭头 :- 的方向阅读.也就是说,从右到左:如果 Y 是一个整数,并且 X 是 Y+1 那么X 也是一个整数.

然后,您可以估计在这种情况下无限的解决方案集.

终止属性

下一个问题涉及谓词的终止属性.请注意,它不能–事实上.isInteger(X) :-isInteger(Y), false,.

只有极小部分负责不终止!剩下的部分甚至根本不看 X 的值.因此,您的程序永不终止.不管你怎么称呼它.

参见failure-slice更多示例.

Assume we have the following predicates (This is an example from Programming in Prolog):

[F0] isInteger(0).
[F1] isInteger(X):- isInteger(Y), X is Y+1.
  1. The first result for query isInteger(R), the marker is placed at F0, and will return R=0

  2. If user presses ; , the marker is placed at F1, we move to subgoal(isInteger(Y), which is satisfied with F0) and R=1.

I understand the above. Now here are my questions:

  1. If user presses ; again, where is the marker? How does the search proceed to return R=2? I have tried to understand the images in page 78-79 of the book, but it is not clear to me. The online tutorials that I found, do not handle backtracking in presence of recursion.

I am looking for any tutorials that explain backtracking in presence of recursion, hopefully with images of stack contents that helps me understand.

Thank you in advanceSuzanne

解决方案

Understanding backtracking and recursion by using images works for very tiny examples, but it does not scale to larger programs. Also, by stepping through a program you easily miss the most interesting properties. Fortunately, there are better notions than that. Let's take your example isInteger/1.

Set of solutions/answers

Your primary interest is to ensure that you are describing the right thing. Here, the second rule is most interesting. Read it in the direction of the arrow :-. That is, right-to-left: Provided Y is an integer, and X is Y+1 then also X is an integer.

Then, you can estimate the set of solutions which is infinite in this case.

Termination properties

The next question concerns the termination properties of the predicate. Note, that it cannot – in fact .isInteger(X) :- isInteger(Y), false, .

Only a very small part is responsible for non-termination! The remaining part does not even look at the value of X at all. Therefore your program terminates never. No matter how you call it.

See failure-slice for more examples.

这篇关于递归谓词中的回溯的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 10:22
查看更多