0

我正在使用 SWI Prolog 为大学考试学习 Prolog，但我有一些问题无法理解我的老师在这个例子中做了什么（在我看来这是不完整的），它实现了谓词：

k(T1,T2,N)

如果T1 和 T2 是树并且如果它们有恰好有 N 个公共子树，则为TRUE （如果 T1 和 T2 中都存在该子树，则该子树在两棵树 T1 和 T2 之间是公共的）

他给了我另一个谓词T(t)，其中 t 是一棵特定的树，而 T(t) 给了我 t 的所有子树（如果你想看到这个东西的图形解释，你可以看到这个文件的幻灯片 18：http ://www.informatica.uniroma2.it/upload/2012/LPDA/08_Lezione_ZNZ.pptx )

所以他说：

k(T1,T2,N)

如果是TRUE则为 TRUE：（健康）状况

实际上，如果 T1 的子树（从 T(T1) 谓词给出）和 T2 的所有子树（从 T(T2) 给出）的交集为 TRUE，则树 T1 和 T2 有 N 个公共子树是 TRUE谓词）在模块中恰好是 N（即作为数字）

好的，继续：他用以下方式定义树：

tree(F, LIST_OF_SUBTREES).

其中 R 是当前树的根

因此，如果树 T1 和 T2 有 N 个公共子树，则使用前面的属性来实现谓词k(T1,T2,N)为 TRUE。

该谓词必须对树 T1 和 T2 中的子树进行 EXAUSTIVE SEARCH

然后他以这种方式实现k/3谓词：

k(T1,T2,N) :- t(T1, ST1),
              t(T2, ST2),
              intersect(ST1,ST2,LST),
              lenght(LST,N).

这在我看来很清楚（如果我错了，请纠正我）：

  • t(T1,ST1)将 T1中包含的所有子树的列表放入 ST1
  • t(T2,ST2)将 T2中包含的所有子树的列表放入 ST2
  • intersect(ST1,ST2,LST)将 ST1 和 ST2 的公共子树列表放入 LST
  • lenght(LST,N)将 ST1 和 ST2 的公共子树的长度放入 N

因此，如果 N 的计算值与给定的 N 值一致，则谓词k(T1,T2,N)为真。

直到这里我认为一切都很清楚......但现在我有一些问题要理解他如何实现 **t(T,STL) 谓词，该谓词采用树 T 并将其所有子树的列表放入 STL。

他给了我以下代码：

t(T,STL) :- bagof(ST, st(T,ST), STL).

st_r(tree(A,_), tree(A,[]).

st_r(tree(A,R), tree(A,R1) :- st_l(R,R1).

st_l([],[]).
st_l([X|R],[X1|R1]) :- st(X,X1),
                       st_l(R,R1).

st(T,T1) :- st_r(T,T1).

st(tree(A,R),T1) :- member(T,R),
                    st(T,T1).

关于谓词：

t(T,STL) :- bagof(ST, st(T,ST), STL).

我认为只需执行内置谓词的bagof ，其中ST是子树对象，如果满足目标，则将st(T,ST)放入STL列表（子树列表）

但现在我不明白st/2谓词（我的目标）是如何工作的！有人可以尝试向我解释这个谓词以及相关的st_l/2和st_r/2谓词的逻辑吗？

拜托，我也对如何具体构建两棵树来测试这个程序有一些疑问。你能给我两棵简单的树用于测试吗？

最后我认为，在这个例子中，缺少intersect/3谓词

肿瘤坏死因子

安德烈亚

4

1 回答 1

1

这里的命名有点神秘，我会尝试猜测它。

  • st/2应该代表子树，其目的是在回溯时枚举所有子树。
  • st_r/2应该代表 subtree_root。它分别返回根和叶子。
  • st_l/2那么应该代表 subtree_leafs。它制作了一个“扁平化”树的列表，替换了实际的子树。

我不同意 st/2仅枚举子树。实际上，由于第一个子句 st_r 执行了修剪，它返回了更多的树。这对我来说似乎是一个不寻常的定义——但无论如何，它是一个定义。

谓词 intersect/3 在 SWI-prolog 库（列表）中定义为 intersect/3。

经过两次错字更正后，该代码给了我

?- t(tree(x,[tree(u,[]),tree(v,[tree(p,[]),tree(q,[])])]),L).
L = [tree(x, []), tree(x, [tree(u, []), tree(v, [])]), tree(x, [tree(u, []), tree(v, [tree(p, []), tree(..., ...)])]), tree(x, [tree(u, []), tree(v, [tree(..., ...)|...])]), tree(x, [tree(u, []), tree(v, [...|...])]), tree(x, [tree(u, []), tree(..., ...)]), tree(x, [tree(..., ...)|...]), tree(x, [...|...]), tree(..., ...)|...].
于 2013-05-04T20:36:31.190 回答