有向圖中的所有路線

Question

我想製作一個應該給出兩個站之間所有可能路線的程序。我遇到的問題是它並沒有給我所有的路線。到目前爲止我的代碼是：

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

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

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

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

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

例如，當我問 「?- route(s1,s4,R)」 只給了我R = [s1, s4]，R = [s1, s2, s3, s4]和R = [s1, s5, s4]。 但也有路線（s1，s2，s5，s4）和（s1，s5，s2，s3，s4），我不知道爲什麼我沒有得到它們。如何解決這個問題？

在此先感謝！

Answer 1

足夠

direction(X,Y) :- connection(X,Y). 

direction(X,Y) :- connection(Y,X). 

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

route(X,Y,_,[X,Y]) :- 
    direction(X,Y). 

route(X, Y, Visited, [X | Hr]) :- 
    direction(X, Z), 
    Z \= Y, 
    \+ member(Z, Visited), 
    route(Z, Y, [Z | Visited], Hr). 

我的意思是：只使用一個direction/2，而不是direction1/2和direction2/2重複。使用Visited列表可以避免潛在的循環。

所以你可以統一route1/3和route2/3在一個單一的route/3。

你的代碼失敗尋找[s1, s2, s5, s4]因爲s1到s5你需要direction1/2（所以route1/3和route1/4），但是從s5到s4你需要direction2/2（但route1/4不叫direction2/2）。

以類似的方式你的代碼失敗找[s1, s5, s2, s3, s4]，因爲你需要從direction2/2s1（所以route2/3和route2/4），以s2但你需要direction1/2從s2到s4。