サイクルなしでグラフ内のすべての可能なパスを見つける

Question

私は、グラフ内の2つの点の間に可能なすべてのパスを与えるためにPrologプログラムを作成しようとしています。

edge(a,b). 
edge(a,c). 
edge(a,d). 
edge(b,e). 
edge(c,e). 
edge(c,f). 
edge(d,f). 
edge(f,g). 
edge(g,e). 
edge(e,a). 

show_path(X,Y,[X,Y]) :- edge(X,Y). 
show_path(X,Z,[X|T]) :- edge(X,Y), not(member(Y, T)), show_path(Y,Z,T). 

私はサイクルを除外し、無限ループを避けるためにnot(member())を使用しようとしているが、それはすべての可能な解決策が得られていません。どのようにしてサイクル内のグラフ内の2つのポイント間のすべての可能なパスを取得するようにプログラムを変更できますか？

Answer 1

not(member(Y, T))は常にfalseになるため、プログラムが機能しません。Tはインスタンス化されていないため、Yを含むリストを常に見つけることができます。

あなたは、アキュムレータを追加して、プログラムを修正することができます：

show_path(X,X,T,P) :- reverse([X|T],P). 
show_path(X,Z,T,P) :- edge(X,Y), not(member(X,T)), show_path(Y,Z,[X|T],P). 

show_path(X,Y,P) :- show_path(X,Y,[],P). 

それはあなたがサイクルを避けることによって何を意味するかは明らかではありません。ここでは、@ coderの答えとは違って、同じ点で2回通ることを避けます。例：

?- show_path(a,e,Z). 
Z = [a, b, e] ; 
Z = [a, c, e] ; 
Z = [a, c, f, g, e] ; 
Z = [a, d, f, g, e] ; 
false. 

Answer 2

Tがインスタンス化されていないときにnot(member(Y, T))が失敗することは簡単に分かります。たとえば、試してみてください：

?- not(member(X,L)). 
false. 

あなたが失敗したことがわかります。あなたは@Fatalizeは、書面によっても示唆された出力を持つことができ

?- show_path(a,e,L). 
L = [a, b, e] ; 
L = [a, b, e, a, c, e] ; 
L = [a, b, e, a, c, f, g, e] ; 
L = [a, b, e, a, d, f, g, e] ; 
L = [a, c, e] ; 
L = [a, c, e, a, b, e] ; 
L = [a, c, e, a, d, f, g, e] ; 
L = [a, c, f, g, e] ; 
L = [a, c, f, g, e, a, b, e] ; 
L = [a, d, f, g, e] ; 
L = [a, d, f, g, e, a, b, e] ; 
L = [a, d, f, g, e, a, c, e] ; 
false. 

：

show_path(X,Y,R):-show_path(X,Y,[],R). 

show_path(X,Y,_,[X,Y]) :- edge(X,Y). 
show_path(X,Y,L,[X|R]) :- edge(X,Z),\+member(Z,L), 
          show_path(Z,Y,[Z|L],R). 

例：あなたは空のリストで始まるすべてのステップでインスタンス化される余分なリストを維持する必要があることを解決するために、 ：

show_path(X,Y,[X,Y]) :- edge(X,Y). 
show_path(X,Y,R) :- edge(X,Z), show_path(Z,Y,RZ),R=[X|RZ],  
          sort(R,R1),length(R,N),length(R1,N1), 
          (N>N1->!,fail ;true). 

例：

?- show_path(a,e,L). 
L = [a, b, e] ; 
L = [a, c, e] ; 
L = [a, c, f, g, e] ; 
L = [a, d, f, g, e] ; 
false.