Prolog和事实数据库-Java 学习之路

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

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

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

我已经定义了这样的二叉树：

tree(ID_of_tree,root,ID_left_tree,ID_right_tree)

例如，这棵树

enter image description here

是这样定义的

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

定义谓词父/ 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 ，但有了这个我有2个问题 . 一个这返回一个列表，我想得到一个数字或假 . 还有两个，如果必须通过递归完成，我不知道如何进入基本情况 .

我认为我需要使用一些谓词，如retract或asserta，但我不确定这一点 .

这是我的第一次尝试，但使用 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

如果我正在寻找一个子树，我应该限制搜索树

Ok, finally I got it. This is my finally attempt and working like charm.

首先，我创建了一个名为 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).

接下来我定义谓词父/ 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的提示和耐心 .

无论如何，谢谢阅读这个问题 .

1 回答

3
您不需要自己在树中搜索 - 您已经将其分解为数据库中的碎片（节点） . Prolog会为你搜索 .

你已经有了
```
father1(3, a4, P):-             % first approximation
    P = 7.
```
这是谓词的第一个近似值 . 试试吧：

？ - father1（3，a4,7） . 真正 . ？ - 父亲（6，a4，P） . 假 .

正确！但情况也是如此
```
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) ).
```
你知道我要去哪儿吗？

两个评论 . 首先，为什么这种表示，而不仅仅是一个术语？你的树木会在其中共享分支吗？循环？

其次，这里不使用 a4 . 为什么你需要它？您是否设想在树中重复，并希望限制搜索到子树？

但是，如果这不是你的疏忽，而你真的想限制你的搜索，你可以扩充上面的 father/3 谓词用作这个的构建块：继续寻找父亲，直到你击中你的'正在寻找（即 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
```
用不同的名称调用它有帮助 .

请注意递归：如果 a4 是 3 的父亲（在那里称为 B3 ），或者如果 3 的父亲在 a4 之下，则 3 在 a4 之下 . 总的来说，对吧？
回复于 2024-05-15T10:42:25+08:00

Prolog和事实数据库

1 回答

相关问题