首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在Prolog中查找is_a()树中的叶节点

问在Prolog中查找is_a()树中的叶节点
EN

Stack Overflow用户
提问于 2018-10-28 21:38:39
回答 1查看 1.1K关注 0票数 2

我使用`is_a(X,Y)在prolog中做了一棵“树”。看起来是这样的:

代码语言:javascript
复制
is_tree('b', 'a').
is_tree('c', 'a').
is_tree('d', 'b').
is_tree('e', 'b').
is_tree('f', 'c').
is_tree('g', 'c').

       a
  b         c
d   e      f  g

现在我试图找到所有的叶节点,也就是d, e, f, g。到目前为止,我已经成功地完成了第一页的write()'ing,但是我不明白如何回树查找其他节点,以及如何编写closing clause来查找值。

代码语言:javascript
复制
find_leaf(X, Y):-
    \+is_tree(X, Y).
find_leaf(X, Y):-
    is_tree(A, Y), !,
    find_leaf(Y, A).
find_leaf(X, Y):-
    is_tree(A, X),
    write(Y),
    find_leaf(Y, A).

我怎么才能“再回来”找到其他的叶子呢?正确的“结束句”是什么?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-10-28 21:56:48

Prolog中的大多数谓词都不执行write/1操作。就像在命令式中一样,函数式编程通常会有大量的函数计算事物,而其他函数则会“沟通”事物(通过写到控制台、更改用户界面等等)。

因此,我建议构造一个谓词find_leaf(X),它将变量X与叶统一起来。由于Prolog的回溯机制,我们最终可以与所有的叶子统一。

从is_tree/2谓词获取节点

在这里,节点--除非您没有提到这一点--只能通过分析is_tree/2谓词获得,其中第一项是“子”,第二项是“父”。我们在这里知道,如果它是一个节点,而不是父节点,那么它就是一种休假。由于没有其他机制来定义树,所以节点(很可能)是某个is_tree谓词中的子节点。

因此,我们可以实现一个谓词,通过以下方法查找childs:

代码语言:javascript
复制
find_leave(X) :-
    is_tree(X, _),
    \+ is_tree(_, X).

因此,第一个调用is_tree(X, _)将把X与树中的一个子调用统一起来,而第二个调用将验证X没有子调用。

这就产生了:

代码语言:javascript
复制
?- find_leave(X).
X = d ;
X = e ;
X = f ;
X = g.

从给定的根中获取叶子

我们还可以通过一个参数传递根,例如:find_leave(b, X)将把X与b的所有子类统一起来。我们在这里有两种情况:

  1. 根R不是父类,在这种情况下是R = X (R是休假);以及
  2. 否则,如果存在子级,我们将递归地使用find_leave(C, X)和C调用子级。由于回溯,我们最终会得到所有的叶子。

所以:

代码语言:javascript
复制
find_leave(R, R) :-
    \+ is_tree(_, R).
find_leave(R, X) :-
    is_tree(C, R),
    find_leave(C, X).

这样我们就可以得到不同的根,不同的叶子:

代码语言:javascript
复制
?- find_leave(a, X).
X = d ;
X = e ;
X = f ;
X = g ;
false.

?- find_leave(b, X).
X = d ;
X = e ;
false.

?- find_leave(R, X).
R = a,
X = d ;
R = a,
X = e ;
R = a,
X = f ;
R = a,
X = g ;
R = b,
X = d ;
R = b,
X = e ;
R = c,
X = f ;
R = c,
X = g ;
false.
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/53036325

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档