查找所有可能的路徑而不用重訪

我需要一個謂詞路由，它可以爲所有城市提供從開始&結束的所有城市。例如：查找所有可能的路徑而不用重訪

path(chicago,atlanta). 
path(chicago,milwaukee). 
path(milwaukee,detroit). 
path(milwaukee,newyork). 
path(chicago,detroit). 
path(detroit, newyork). 
path(newyork, boston). 
path(atlanta,boston). 
path(atlanta, milwaukee). 

?- routing(chicago,newyork,X). 
X=[chicago,milwaukee,newyork]; 
X=[chicago,detroit,newyork]; 
X=[chicago,milwaukee,detroit,newyork]; 
X=[chicago,atlanta,milwaukee,newyork]; 
X=[chicago,atlanta,milwaukee,detroit,newyork]

我試過這個，並不斷回來。

routing(FromCity,ToCity,[FromCity|ToCity]) :- 
    path(FromCity,ToCity). 

routing(FromCity,ToCity,[FromCity|Connections]) :- 
    path(FromCity,FromConnection), 
    path(FromConnection,ToConnection), 
    path(ToConnection,ToCity), 
    routing(ToConnection,ToCity,Connections). 

routing(FromCity,ToCity,[]).

，但它只是不斷給

X=[chicago,milwaukee,newyork]; 
X=[chicago,chicago,newyork]; 
X=[chicago,chicago,chicago,newyork] 
... 
..

可有一個人請點我在正確的方向...

來源

2012-11-01 Kickaha

如果確定（定義），你的圖形是無環，你可以簡化你的規則，利用Prolog深度優先搜索：

routing(FromCity, ToCity, [FromCity, ToCity]) :- 
    path(FromCity, ToCity). 

routing(FromCity, ToCity, [FromCity|Connections]) :- 
    path(FromCity, ToConnection), 
    routing(ToConnection, ToCity, Connections).

這個找到所有ava ilables上回溯路徑：

?- routing(chicago,newyork,X). 
X = [chicago, atlanta, milwaukee, newyork] ; 
X = [chicago, atlanta, milwaukee, detroit, newyork] ; 
X = [chicago, milwaukee, newyork] ; 
X = [chicago, milwaukee, detroit, newyork] ; 
X = [chicago, detroit, newyork] ; 
false.

注列表構造的第一和第二圖案之間的差異：[FromCity, ToCity] VS [FromCity|Connections]。這是因爲Connections將是list，而ToCity將成爲原子，當規則成功時。

如果您的圖形包含循環，此代碼將循環。您可以參考another answer獲取處理此問題的簡單模式。

來源

2012-11-01 07:22:55 CapelliC

您好，我有一個類似的問題，但我想用「寫」函數寫出來裏面的路徑所以我將不得不在函數中調用是開始和結束有沒有什麼辦法來配置您的示例以使其工作？ – Fjodor

@Fjodor：由於回溯，你無法可靠地寫出路徑。嘗試在遞歸調用後寫入（連接） – CapelliC

這是我的解決方案，適用於有向圖或無向圖，有或沒有周期。

它也試圖找到所有路徑，而不需要重新訪問。

c(1,2). 
% ... c(X,Y) means X and Y are connected 

d(X,Y):- c(X,Y). 
d(X,Y):- c(Y,X). 
% Use d instead of c to allow undirected graphs 

findPathHelper(_, Begin, [], End):- d(Begin, End). 
findPathHelper(Front, Begin, [Next|NMiddle], End):- 
    not(member(Begin,Front)), 
    d(Begin, Next), 
    append([Front,[Begin]], NFront), 
    findPathHelper(NFront, Next, NMiddle, End). 

findPath(Start, End, Path):- 
    findPathHelper([], Start, Middle, End), 
    append([[Start],Middle,[End]], Path).

來源

2015-12-03 21:38:14 VillasV

如何繼續如下？

首先，我們選擇一個比path更好的謂詞名稱。 edge怎麼樣？

edge(chicago , atlanta ). 
edge(chicago , milwaukee). 
edge(milwaukee, detroit ). 
edge(milwaukee, newyork ). 
edge(chicago , detroit ). 
edge(detroit , newyork ). 
edge(newyork , boston ). 
edge(atlanta , boston ). 
edge(atlanta , milwaukee).

如上定義，edge/2顯然不是symmetric，否則下面的查詢不會成功！

?- edge(X, Y), \+ edge(Y, X). 
    X = chicago , Y = atlanta 
; X = chicago , Y = milwaukee 
; X = milwaukee, Y = detroit 
; X = milwaukee, Y = newyork 
; X = chicago , Y = detroit 
; X = detroit , Y = newyork 
; X = newyork , Y = boston 
; X = atlanta , Y = boston 
; X = atlanta , Y = milwaukee.

接下來，我們定義connected_to/2作爲edge/2的對稱閉：

connected_to(X, Y) :- edge(X, Y). 
connected_to(X, Y) :- edge(Y, X).

最後，我們使用meta-predicate path/4連同connected_to/2：

?- path(connected_to, Path, From, To). 
; From = To     , Path = [To] 
; From = chicago, To = atlanta, Path = [chicago,atlanta] 
; From = chicago, To = boston , Path = [chicago,atlanta,boston] 
; From = chicago, To = newyork, Path = [chicago,atlanta,boston,newyork] 
...

所以...做的最一般查詢path/4（含connected_to/2）普遍終止？

 
?- path(connected_to, Path, From, To), false. 
false.         % terminates universally

最後，讓我們計算的不同接地路徑總數：

?- setof(P, From^To^(path(connected_to,P,From,To),ground(P)), _Ps), 
    length(_Ps, N_Ps). 
N_Ps = 244.

來源

2015-12-03 22:48:21 repeat

查找所有可能的路徑而不用重訪

回答

相關問題