遍歷（隨可能存在的環路），並返回在序言

的路上我給定弧線的列表：如果有從路徑遍歷（隨可能存在的環路），並返回在序言

arc(a,b). 
arc(b,c). 
arc(c,d). 
arc(d,b). 
arc(d,e). 
arc(e,e). 
arc(e,f).

我已經寫了一組子句，這將告訴我的節點X到節點Y。循環可能會發生，我已經說明了這一點。

path(X,Y) :- 
    arc(X,Y). 
path(X,Y) :- 
    arc(X,Z), 
    path(Z,Y,[X]). 

path(X,Y,P) :- 
    arc(X,Y). 
path(X,Y,P) :- 
    \+ member(X,P), 
    arc(X,Z), 
    append([X],P,L), 
    path(Z,Y,L).

我需要修改它，在成功時返回遍歷的節點列表。我不清楚我會如何做到這一點。

我假設我的基本情況是類似於path2(X,Y,[X,Y]) :- arc(X,Y).，但這不適用於我的程序。前一部分的解決方案有什麼問題嗎？或者我錯過了一些小修改？任何幫助，將不勝感激。謝謝！

來源

2010-10-10 birderic

你想用「路徑（X，Y，P）： - 弧（X，Y）」來實現什麼？（確保頭部中的所有變量也存在於身體內是一個好主意。） – Kaarel 2010-10-10 19:51:07

這是基本情況。一旦我們從當前節點（X）到最終節點（Y）出現一條弧線，我們就找到了一條路徑。 P是我們已經訪問的節點的列表。我明白你在說什麼，並同意P在那個條款中沒有真正的用處（或者是否）？但是我只是不知道該從哪裏去。 – birderic 2010-10-10 20:04:38

另一件事：append（[X]，P，L）== L = [X | P] – Kaarel 2010-10-10 20:13:45

關閉......但是考慮：

path(Start, End, Path) :- 
    path(Start, End, [], Path).

調用path/3有開始和結束節點將建設路之間，如果它存在，並原路返回給你備用路由。沒有節點被訪問兩次。 []是一個節點累加器列表，因此我們可以檢查我們不會在路徑建立時進入圓圈。

path(Now, End, Acc, Path) :- 
    arc(Now, Mid), 
    Mid == End, !, 
    append(Acc, [Now, End], Path). 

path(Now, End, Acc, Path) :- 
    arc(Now, Mid), 
    \+ member(Mid, Acc), 
    path(Mid, End, [Now|Acc], Path).

這些謂詞完成實際工作。第一個是基本情況，通過對arc/2的另一個調用來到達終端節點;在這種情況下，建立了一條路徑。第二個遍歷（定向）圖，但僅限於尚未訪問過的節點。

所有路徑可以位於一次經由使用findall/3：

findall(Path, path(Start,End,Path), Paths).

對於到節點原子Start和End界值。

來源

2010-10-10 22:23:24 sharky

由sharky給出的答案似乎並不適用於我，但下面的mod確實對我而言更直接。：

path(Now, End, Acc, [Now,End]) :- 
    arc(Now, End), 
    \+ member(Now, Acc), 
    \+ member(End, Acc). 

path(Now, End, Acc, Path) :- 
    arc(Now, Mid), 
    \+ member(Mid, Acc), 
    path(Mid, End, [Now|Acc], Path).

請告訴我，如果我失去了一些東西。

來源

2015-11-17 19:04:24 hutchinscruff

移至higher level並使用transitive-closure 作爲基本用法！

 
%  your binary predicate arc/2 gets used here 
%   | 
%   v 
?- path (arc, Path, From, To). 
    From = To  , Path = [To] 
; From = a, To = b, Path = [a,b] 
; From = a, To = c, Path = [a,b,c] 
; From = a, To = d, Path = [a,b,c,d] 
; From = a, To = e, Path = [a,b,c,d,e] 
; From = a, To = f, Path = [a,b,c,d,e,f] 
; From = b, To = c, Path = [b,c] 
; From = b, To = d, Path = [b,c,d] 
; From = b, To = e, Path = [b,c,d,e] 
; From = b, To = f, Path = [b,c,d,e,f] 
; From = c, To = d, Path = [c,d] 
; From = c, To = b, Path = [c,d,b] 
; From = c, To = e, Path = [c,d,e] 
; From = c, To = f, Path = [c,d,e,f] 
; From = d, To = b, Path = [d,b] 
; From = d, To = c, Path = [d,b,c] 
; From = d, To = e, Path = [d,e] 
; From = d, To = f, Path = [d,e,f] 
; From = e, To = f, Path = [e,f] 
; false.

^{腳註1：作爲由多功能meta-predicatepath/4實現。}

來源

2015-12-21 14:12:25 repeat

遍歷（隨可能存在的環路），並返回在序言

回答

相關問題