prolog中有向圖的循環

Question

我在prolog中創建了一個程序，它應該給我一個循環中兩個站之間的路由。例如，當我要求s3和s4之間的路線時，它給了我兩條正確的路線[s3，s4]和[s3，s2，s1，s6，s5，s4]，但它也給了我一個解決方案，不想要。它是[s3，s4，s5，s6，s1，s2，s3，s4]。在一條路線上多次訪問一個站點是不可能的。我試圖用成員命令來防止這種情況，但它似乎總是不起作用。我怎樣才能解決這個問題？

下面是代碼：

% facts 

connection(s1,s2). 
connection(s2,s3). 
connection(s3,s4). 
connection(s4,s5). 
connection(s5,s6). 
connection(s6,s1). 

% predicates 

direction1(X,Y) :- connection(X,Y). 
direction2(X,Y) :- connection(Y,X). 

route1(X,Y,R):- route1(X,Y,[],R). 
route1(X,Y,_,[X,Y]) :- direction1(X,Y). 
route1(X,Y,L,R) :- direction1(X,Z), \+member(Z,L), route1(Z,Y,[Z|L],RZ), R=[X|RZ]. 

route2(X,Y,R):- route2(X,Y,[],R). 
route2(X,Y,_,[X,Y]) :- direction2(X,Y). 
route2(X,Y,L,R) :- direction2(X,Z), \+member(Z,L), route2(Z,Y,[Z|L],RZ), R=[X|RZ]. 

route(X,Y,R) :- route1(X,Y,R); route2(X,Y,R). 

提前感謝！

Answer 1

這是Prolog中的一個經典錯誤。你會得到這個額外的答案，因爲route1（或route2）的第三條規則與第二條規則的超集相匹配，這不是你想要的。

例如，如果我們只關注：

route1(X,Y,_,[X,Y]) :- direction1(X,Y). 
route1(X,Y,L,R) :- direction1(X,Z), \+member(Z,L), route1(Z,Y,[Z|L],RZ), R=[X|RZ]. 

然後，我們看到，如果X和Y匹配的第一個規則，那麼他們也將匹配第二個規則，導致你的問題。事實上，我們希望第二條規則僅適用於第一條規則失敗的情況下（即，如果不存在X和Y之間的路徑，並且我們必須經過從Z開始的其他點）。

因此，我們可以解決這個問題，這些簡單的改變（去掉調用member後）：

route1(X,Y,R) :- 
    route1(X,Y,[],R). 
route1(X,Y,_,[X,Y]) :- 
    direction1(X,Y). 
route1(X,Y,L,R) :- 
    \+ direction1(X,Y), 
    direction1(X,Z), 
    route1(Z,Y,[Z|L],RZ), 
    R=[X|RZ]. 

route2(X,Y,R) :- 
    route2(X,Y,[],R). 
route2(X,Y,_,[X,Y]) :- 
    direction2(X,Y). 
route2(X,Y,L,R) :- 
    \+ direction2(X,Y), 
    direction2(X,Z), 
    route2(Z,Y,[Z|L],RZ), 
    R=[X|RZ].

以粗體顯示兩行，我們說，這些規則如果沒有已經是僅適用直接路徑在X和Y之間。