サブツリーのプロローグの高さ（深さ）

Question

child(X,Y)の関係を持ちます。Xはルート/親ノードで、Yは有向枝です。私は特定のルートノードRから各サブツリーの高さHを動的関係height(R, H)で計算したいと思います。

私の以前のコードは：

child(a,b). 
child(a,f). 
child(f,g). 
child(f,h). 
child(b,c). 
child(c,d). 
child(b,e). 
child(c,l). 
child(l,j). 

height(R, H) :- 
    path(R,_,B,H), 
    write(B). 

path(X,Y,[X,Y],1) :- 
    child(X,Y). 
path(X,Y,[X|P],C) :- 
    child(X,Z), 
    path(Z,Y,P,Cn), 
    C is Cn+1. 

は、ノードRから始まるすべてのパス（および長さ）を求めます。再帰的にn-naryツリー内で最長のパスのみを見つける方法はありますか？または、以前にツリー構造をリストに保存する必要がありますか？

Answer 1

引数ではなくwriteそれとしてパスを提供する方が良いでしょう：

あなたの結果を与える

height(Node, Height, Path) :- path(Node, _, Path, Height). 

：

| ?- height(a, H, P). 

H = 1 
P = [a,b] ? ; 

H = 1 
P = [a,f] ? ; 

... 

あなたがwriteを使用すると、結果が画面に行きますプログラムで使用するためにはキャプチャされません。 setof/3を使用すると、パスとその高さのペアを収集できます。 setof/3が昇順に結果を順序付けするので、所与のノードから始まる最短（または最長）経路を得ることが簡単になる：

max_height_path_for_node(Node, MaxHeight, MaxPath) :- 
    setof(Height-Path, height(Node, Height, Path), Paths), 
    reverse(Paths, [MaxHeight-MaxPath | _]). 

reverse/2がリストの先頭に最大高さを取得するために使用され、そしてあなたはそこから結果を "選ぶ"。あなたがaggregateライブラリを使用する場合は、ワンライナーでこれを解決することができます

max_height_path(MaxHeight, MaxPath) :- 
    setof(Height-Path, Node^height(Node, Height, Path), Paths), 
    reverse(Paths, [MaxHeight-MaxPath | _]). 

Answer 2

：

height(R,H) :- 
    aggregate(max(Hi),A^B^path(R,A,B,Hi),H). 

照会の例：

をすべてのノードを超える最大のパスを見つけるには

?- height(A,H). 
A = a, 
H = 4 ; 
A = b, 
H = 3 ; 
A = c, 
H = 2 ; 
A = f, 
H = 1 ; 
A = l, 
H = 1. 

?- height(a,H). 
H = 4. 

?- height(f,H). 
H = 1. 

?- height(f,3). 
false. 

?- height(A,3). 
A = b ; 
false. 

したがって、max集約を実行する各パスの高さに実行します。与えられたルート要素Rで始まり（弁別子引数としてAとBを設定します）、結果をHとして返します。