在沒有循環的圖中找出所有可能的路徑

Question

我想寫一個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())排除週期和避免無限循環，但它不會產生所有可能的解決方案。我如何改變程序以獲得循環圖中兩點之間的所有可能路徑？

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). 

目前尚不清楚你避免循環的意思。在這裏，它不會像@編碼器的答案那樣在同一點上傳遞兩次。例如：

?- 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. 

你看到它失敗。爲了解決這個你需要保持，這將在每一步中實例化一個額外的清單，空單開始：

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(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. 

你可以有輸出@Fatalize還建議通過書面形式：

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.