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之间。