Prolog 和事实数据库

Question

我正在学习 Prolog，我有一些问题想问你。我想学习如何解决这些问题而不是最终的解决方案。

作为一个新手，我对这门语言知之甚少，但我不想成为一个骗子:(

好的，所以我的问题是......

我定义了一个像这样的二叉树:

tree(ID_of_tree,root,ID_left_tree,ID_right_tree)

例如这棵树

是这样定义的

tree(a4,6,b3,b4).
tree(b3,7,c1,c2).
tree(c1,5,d1,nil).
tree(d1,1,nil,nil).
tree(c2,3,nil,d2).
tree(d2,4,nil,nil).
tree(b4,8,c3,c4).
tree(c3,10,nil,nil).
tree(c4,11,d3,d4).
tree(d3,9,nil,nil).
tree(d4,2,nil,nil).

它们是我的事实数据库中的事实。所以我的第一个问题是，如何识别这个数据库中节点N的父亲。例如:

?-father(3,a4,P).
P=7
?-father(6,a4,P).
false

定义谓词father/3。

father(N,Abn,P).

N= Node that I want to get its father
Abn = Tree where Im looking for. If a4, this means that is the all tree in this case.
P = Father of N.

我正在考虑使用 findall/3 但这样我有两个问题。其中一个返回一个列表，我想得到一个数字或错误。第二，如果必须通过递归来完成，我不知道如何到达基本情况。

我认为我需要使用一些谓词，例如撤回或断言，但我对此不确定。

这是我的第一次尝试，但使用 father(3,a4,P). 的输出是 false

father2(N,Abn,PA,PA):- =(N, PA).
father(N,Abn,P) :- tree(Abn,N,A1,_), tree(A1,PA,_,_), father2(N,A1,PA,P).
father(N,Abn,P) :- tree(Abn,N,_,A2), tree(A2,PA,_,_), father2(N,A2,PA,P).

我的第二次尝试是这样的，它返回了一个很好的解决方案

father(N,Abn,P):- tree(FT,N,_,_), tree(_,P,FT,_).
father(N,Abn,P):- tree(FT,N,_,_), tree(_,P,_,FT).

这可能很好，但我对这个谓词有疑问

father(3,d3,P).
P = 7

如果我在子树中查找，我应该限制搜索树

好吧，我终于明白了。这是我最后的尝试，工作充满魅力。

首先，我创建了一个名为 check_tree/2 的谓词。该谓词检查一棵树是否是另一棵树的子树。例如:

?- check_tree(c4,c2).
false

?-check_tree(d1,b3).
true

这是检查代码:

check_tree(Abn1,Abn1).
check_tree(Ab1,Ab2):- tree(Ft,_,Ab1,_), check_tree(Ft,Ab2).
check_tree(Ab1,Ab2):- tree(Ft,_,_,Ab1), check_tree(Ft,Ab2).

接下来我定义谓词father/3，如下所示:

father(N,Abn,P):- tree(FT,N,_,_), tree(_,P,FT,_), check_tree(FT,Abn).
father(N,Abn,P):- tree(FT,N,_,_), tree(_,P,_,FT), check_tree(FT,Abn).

现在，如果节点位于搜索子树内部，我只计算父亲。

?- father(3,b3,P).
P=7

?- father(3,c4,P).
false

特别感谢 luker 和 Will ness 的提示和耐心。

无论如何，感谢您阅读这个问题。

Answer 1

您不需要自己在树中搜索 - 您已经将其分解为数据库中的片段(节点)。 Prolog 将为您搜索它。

你已经有了

father1(3, a4, P):-             % first approximation
    P = 7.

这是您的谓词的第一个近似值。尝试一下:

?- father1(3,a4,7).
true.
?- father(6,a4,P).
false.

正确!但也有这样的情况

father2(3, a4, P):-              % second approximation
    tree(c2,3,nil,d2), 
    ( tree(b3,7,c1,c2) ; tree(b3,7,c2,c1) ), 
    P = 7.

所以，还有

father3(3, a4, P):-               % third approximation
    tree(C2, 3, Nil, D2), 
    ( tree(B3, P, C1, C2) ; tree(B3, P, C2, C1) ).

你明白我的意思了吗？

两点评论。首先，为什么要这样表示，而不仅仅是作为一个术语？你的树会有共用的 Twig 吗？周期？

第二，a4此处不使用。为什么你需要它？您是否设想树中存在重复项并希望将搜索限制在子树中？

但是，如果这不是您的疏忽，并且您确实想限制搜索，则可以增强上述 father/3用作此构建 block 的谓词:继续搜索父亲，直到找到您要搜索的父亲(即本例中的 a4)——或者没有(即在向上的过程中没有遇到它，这意味着您位于树的错误部分)。您需要对其进行调整，不仅要查找该值，还要查找父亲的 ID(为其添加第四个参数)。

<小时/>

编辑:以下是您可以采取的方法:

father4(Three, A4, P, B3):-               % fourth approximation
    tree(C2, Three, Nil, D2), 
    ( tree(B3, P, C1, C2) ; tree(B3, P, C2, C1) ).

然后，如果您形成了扩展 father4/4 的传递闭包谓词 w.r.t.它的第四个参数，就像简单的

is_under1(3, a4):- 
    transitive_closure(father4(3, a4, _), List_Of_IDs),      % pseudocode
    memberchk(a4, List_Of_IDs).

然后如果是 true ，您知道您位于正确的子树中。您可以手动编写连词，这是一个很好的练习，可以让您真正感受到该语言以及理论基础。考虑一下学徒在开始时必须首先手工完成每一项琐碎的任务，然后才继续学习可以更快地完成工作的复杂工具。当然，有一天一切都将由 3D 打印机完成，但在那之前(或者甚至)，我们可以沉迷于将我们的行业视为一门艺术。

但是手动编码也让您有机会提高效率，一旦找到父ID(如果它是)就停止搜索发现):

is_under2(3, a4):-
    father4( 3, a4, P, B3),
    ( B3 == a4 , !                   % a cut, if you would like it
    ; is_under( ... , ... ) ).       % recursive call

用不同的名称来调用它会有所帮助。

注意递归:3位于a4下如果a4是 3的父亲(在那里称为 B3)，或如果 3的父亲在a4下。完全有道理，对吧？