1

有谁知道，如何在 Prolog 中获取叶节点列表？

假设，我有一个由这些有向边描述的简单有向图：

de(0,1).
de(0,2).
de(2,3).
de(2,4).
de(3,4).
de(4,5).

现在，如何递归地浏览图并编写这 2 个叶节点（节点 1 和 5）的列表？

感谢您的任何回答！

编辑：

好吧，我有第一个谓词编写和工作：

isLeaf(Node) :-
not(de(Node,_)).

但是现在，我不知道如何遍历图形并编写叶节点的输出列表。我知道，这很容易，但我没有这种思维和编程方式的经验:(

4

2 回答 2

4

您需要定义一个谓词is_leaf/1生成器，即它用可能的解决方案实例化输入变量。

像这样的东西：

% Directed graph
de(0,1).
de(0,2).
de(2,3).
de(2,4).
de(3,4).
de(4,5).

% If Node is ground,
%         then test if it is a child node that is not a parent node.
% If Node is not ground,
%         then bind it to a child node that is not a parent node.
is_leaf(Node) :-
    de(_, Node),
    \+ de(Node, _).

使用示例：

?- is_leaf(Node).
Node = 1 ;
Node = 5.

?- is_leaf(Node), writeln(Node), fail ; true.
1
5
true.

?- findall(Node, is_leaf(Node), Leaf_Nodes).
Leaf_Nodes = [1, 5].

您的解决方案立即调用not. （顺便说一句，SWI-Prolog 建议使用\+而不是not.）

isLeaf(Node) :-
    not(de(Node,_)).

这意味着您isLeaf/2不是生成器：它要么失败要么成功（一次），并且如果它恰好是一个变量，则永远不会绑定输入参数。此外，它从不测试输入是否是叶子，它只是测试它是否不是父节点。

% Is it false that 1 is a parent? YES
?- isLeaf(1).
true.

% Is it false that blah is a parent? YES
?- isLeaf(blah).
true.

% Is it false that 2 is a parent? NO
?- isLeaf(2).
false.

% Basically just tests if the predicate de/2 is in the knowledge base,
% in this sense quite useless.
?- isLeaf(Node).
false.
于 2009-05-19T12:06:59.843 回答
0

想想你会做相反的事情，即制定一个谓词，可以告诉你一个节点是否是一个分支。

从那里开始，编写一个遍历图的谓词应该非常简单，如果当前节点是叶子，则打印和回溯。

于 2009-05-19T08:25:14.377 回答