有向圖中的序言路線

Question

我對於序言非常陌生，想要創建一個程序，在那裏我可以請求一個謂詞爲「route(Startpoint,Endpoint,Route)」的路線。

到目前爲止我的代碼是：

% facts 

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

% predicates 

route1(X,Y,[X,Y]) :- connection(X,Y). 
route1(X,Y,R) :- connection(X,Z), route1(Z,Y,RZ), R=[X|RZ]. 

route2(X,Y,[X,Y]) :- connection(Y,X). 
route2(X,Y,R) :- connection(Z,X), route2(Z,Y,RZ), R=[X|RZ]. 

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

我的代碼工作的一些途徑，而不是在它（在事實像上面）涉及到一個週期。我怎樣才能在Prolog中防止多次訪問一個站點？

例如，當我問「?- route1(s1,s4,R).」，序言給了我正確的路線「[s1,s2,s3,s4]」第一，但它也給了我其他途徑，如「[s1, s2, s3, s4, s5, s6, s7, s1, s2, s3, s4]」，「[s1, s2, s3, s4, s5, s6, s7, s1, s2, s3, s4, s5, s6, s7, s1, s2, s3, s4]」等。

提前致謝！

Answer 1

你可以這樣寫：

route1(X,Y,[X,Y]) :- connection(X,Y). 
route1(X,Y,R) :- connection(X,Z), route1(Z,Y,RZ),R=[X|RZ],  
       sort(R,R1),length(R,N),length(R1,N1), 
       (N>N1->!,fail ;true). 

sort/2刪除重複，所以如果你希望你的解決方案不是有重複排序列表和輸出列表必須具有相同的長度。

?- route1(s1,s4,R). 
R = [s1, s2, s3, s4] ; 
false. 

另一個做到這一點的方法是：

route1(X,Y,R):-route1(X,Y,[],R). 

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

例子：

?- route1(s1,s4,R). 
R = [s1, s2, s3, s4] ; 
false.