2

I have some program about a graph with black and white vertices:

black(root).
black(v1).
black(v3).
black(v4).

edge(root,root).
edge(v1,root).
edge(v2,v1).
edge(v3,v1).
edge(v4,v3).
edge(v5,v2).
edge(v5,v4).
edge(v6,v5).

vertex(X) :- edge(X,_).
vertex(X) :- edge(_,X).

white(X) :-
   vertex(X),
   not(black(X)).

foo(root).
foo(X) :-
   edge(X,Y),
   black(Y),
   foo(Y).

when I run the goal foo(X) I get a problem: If I remove the fact edge(root,root) the program find some solutions (6 different solutions). Otherwise, I get infinite solutions and all are X=root. Why does this happen?

4

1 回答 1

4

首先是一个快速回答，它向您展示了 Prolog 程序员如何看待您的程序，下面是对它的解释。您的程序不会终止，因为以下故障片不会终止：

黑色（根）。
黑色（v1）：-假。
黑色（v3）：-假。
黑色（v4）：-假。

边缘（根，根）。
边缘（v1，根）：-假。
边缘（v2，v1）：-假。
边缘（v3，v1）：-假。
边缘（v4，v3）：-假。
边缘（v5，v2）：-假。
边缘（v5，v4）：-假。
边缘（v6，v5）：-假。

富（根）：-假。
foo(X) :- X = 根，Y = 根，
   边缘（X，Y），
   黑色（Y），
   富（Y），假。

所有被划线的文本都与理解非终止无关。如您所见，其余部分相对较短，因此可以快速掌握。

Prolog 无法直接检测到此循环。但是，您可以使用这里closure0/3定义的目的：

edge_toblack(X, Y) :-
   edge(X, Y),
   black(Y).

foo(X) :-
   closure0(edge_toblack, X,root).

现在了解详情。

在回答您的问题为什么会发生这种情况之前，让我们退后一步。我们首先需要找到一个观察问题的好方法。目标foo(X)确实产生了答案，实际上只有X = root. 所以也许你只是不耐烦地等待 Prolog 完成？通过询问问题foo(X), false，我们摆脱了这些烦人、眼睛疲劳的答案，我们将等待得到false答案。

我们仍然不能确定程序的非终止属性。false但是我们可以通过插入目标（以及）来缩小实际原因(=)/2。在上面的故障片中，我插入了最大值。如果您刚刚开始，只需添加一个 false 然后重新加载程序并重试查询。有了一些经验，您很快就能快速识别此类零件。所以现在我们只需要了解

富（根）： -
   边缘（根，根），% 始终为真
   黑色（根），% 始终为真
   富（根），假。

甚至更短

富（根）： -
   富（根）。

Prolog 非常简单但高效的执行机制不会检测到此类循环。基本上有几种方法：

  1. 手动添加循环检测。这通常很容易出错

  2. 使用closure0/3- 见上文

  3. 编写自己的元解释器来检测循环

  4. 使用 B-Prolog 或 XSB-Prolog 中提供的语言扩展，如表格。

于 2015-01-27T14:01:35.613 回答