有向グラフ内のすべてのルート

Question

2つのステーション間のすべての可能なルートを提供するプログラムを作りたいと思います。私が持っている問題は、それが私にすべてのルートを与えないということです。私のコードは、これまでのところです：たとえば

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). 

私はそれは私だけR = [s1, s4]、R = [s1, s2, s3, s4]とR = [s1, s5, s4]を与える "?- route(s1,s4,R)" を求めるとき。 しかし、ルート（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). 

私は意味：direction1/2とdirection2/2の一つだけdirection/2代わりに重複を使用します。 Visitedリストを使用すると、潜在的なループを避けることができます。

とroute2/3を1つのroute/3にまとめることができます。

あなたのコードは、あなたがdirection2/2を必要とする（ただし、direction2/2をroute1/4呼び出すことはありません）あなたはdirection1/2（そうroute1/3とroute1/4）を必要とするため、s1からs5に[s1, s2, s5, s4]を見つけることが、s5からs4に失敗します。あなたのコードは、あなたがs2にs1からdirection2/2（そうroute2/3とroute2/4）が必要ですが、あなたはs2からs4にdirection1/2を必要とするので[s1, s5, s2, s3, s4]を見つけることに失敗同様に

。