tree - 在 Prolog 中的 is_a() 树中查找叶节点
问题描述
我使用'is_a(X,Y)'在'prolog'中制作了一个基本的'树'。看起来像这样:
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
的找到值。
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).
我怎样才能“再次备份”以找到其他叶子?什么是正确的“结束语”?
解决方案
Prolog 中的大多数谓词都不做任何write/1
事情。就像在命令式和函数式编程中一样,通常大量函数计算事物,而其他函数则“通信”事物(通过写入控制台、更改用户界面等)。
所以我建议构建一个谓词find_leaf(X)
,将变量X
与叶子统一起来。由于 Prolog 的回溯机制,我们可以最终统一所有叶子。
从is_tree/2
谓词中获取节点
这里的节点——除非你没有提到这一点——只能通过分析is_tree/2
谓词获得,其中第一项是“孩子”,第二项是“父母”。我们知道,如果它是一个节点而不是父节点,那么它就是一个休假。由于没有其他机制来定义树,因此节点(很可能)是某个is_tree
谓词中的子节点。
因此,我们可以实现一个谓词来查找具有以下条件的子级:
find_leave(X) :-
is_tree(X, _),
\+ is_tree(_, X).
因此,第一个调用is_tree(X, _)
将与树中的一个孩子统一X
,而第二个调用验证没有孩子 for X
。
然后产生:
?- find_leave(X).
X = d ;
X = e ;
X = f ;
X = g.
从给定的根中获取叶子
我们还可以通过参数传递根,例如:find_leave(b, X)
将X
与b
. 我们这里做两种情况:
R
,根,不是父母,在这种情况下R = X
(R
是休假);和- 否则,如果有孩子,我们递归调用
find_leave(C, X)
一个C
孩子。由于回溯,最终我们将获得所有叶子。
所以:
find_leave(R, R) :-
\+ is_tree(_, R).
find_leave(R, X) :-
is_tree(C, R),
find_leave(C, X).
然后我们因此获得不同的根,不同的叶子:
?- 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.
推荐阅读
- java - 在这一行发现了多个注释。MyConnection 无法解决
- r - 尝试在本地浏览器中查看时,Docker R Shiny app 0.0.0.0 拒绝连接
- sql - sas 数据集中的问题
- mysql - 有人如何每天访问我的 mysql 数据库一次,尤其是为什么?
- php - 在 PHP 中的总周计数范围内查找当前日期的周数
- ios - 使用 xcode 11.7 可以成功编译相同的项目,但使用 xcode 12.1 编译失败
- javascript - Javascript允许在多行字符串中使用字符``
- xamarin - 如何更改“Xamarin.Forms Material Visual”禁用按钮的透明度?
- flask - FlaskMigrate 未检测到添加的新列
- vb.net - VB.NET - DataGridView 数据不显示