在一個簡單的Prolog圖中找到一個循環

我遇到了這個簡單的Prolog圖的麻煩，我想測試一個循環，不知道爲什麼它不工作。 isPath似乎工作，問題是與cycle函數應該檢查給定的字母是否有一個循環。誰能幫忙？在一個簡單的Prolog圖中找到一個循環

path(a, b). 
path(a, c). 
path(a, f). 
path(b, e). 
path(c, d). 
path(d, a). 
path(d, h). 
path(e, f). 
path(e, g). 
path(e, h). 
path(f, g). 
path(f, b). 
path(h, g). 

isPath(X, X) :- 
    path(X, Y). 

isPath(X, Y) :- 
    path(X, Z), 
    isPath(Z, Y). 

cycleIt(J) :- 
    isPath(J, K), 
    isPath(K, J).

來源

2015-12-05 bobEe

我假設你的'週期/ 1'導致堆棧溢出。 'isPath/2'可以無限循環，因爲它不會檢查循環本身。要做到這一點，你需要保持一個你已經在路徑中的列表，並拒絕你已經去過的節點。還要注意，由於構建了事實，因爲'path（X，Y）'只在'X \ = Y'時才已經嘗試過，所以'X \ = Y'沒有任何作用。 – lurker

我是新來的prolog，所以你的意思是我需要創建一個列表，如附加2個節點的功能，然後檢查：我在哪裏「llist與成員函數，看看他們是否已被訪問 – bobEe

路徑單向還是雙向？換句話說，如果你有'path（a，b）'你想'isPath（b，a）'是真的還是不是？無論如何，內置到你的數據中你有一個循環。（a，X）.'將會運行，但它會提供無限的解決方案，因爲沒有任何東西可以阻止循環周而復始地停止它，所以你需要引入另一個參數，一個列表，它跟蹤你訪問過的所有節點，並在接受節點之前檢查列表。 – lurker

您可以使用DCG！你怎麼找到週期？你需要找到一個節點From，由邊連接到另一個節點Via，然後從Via，你需要找到一個路徑，以From結尾，並且在搜索過程中你不能有循環。這樣：

cycle --> [X], {path(X, Y)},search(Y, X, []). 

% the search is ended 
search(From, To, _Visited)--> {path(From,To)}, [From,To]. 

% we try an another path using Via, which has not been already visited 
search(From, To, Visited)--> {path(From,Via), \+member(Via, Visited)}, [From], search(Via, To, [Via|Visited]).

結果

?- phrase(cycle, A,[]). 
A = [a, c, d, a] ; 
A = [b, e, f, b] ; 
A = [c, d, a, c] ; 
A = [d, a, c, d] ; 
A = [e, f, b, e] ; 
A = [f, b, e, f] ; 
false.

來源

2015-12-05 15:51:05 joel76

在一個簡單的Prolog圖中找到一個循環

回答

相關問題