Цикл в ориентированном графе в прологе

Question

Я создал программу в прологе, которая должна дать мне маршруты между двумя станциями в цикле. Когда я, например, прошу маршрут между s3 и s4, он дает мне два правильных маршрута [s3, s4] и [s3, s2, s1, s6, s5, s4], но также дает мне одно решение. я хочу. Это [s3, s4, s5, s6, s1, s2, s3, s4]. Нельзя было бы посещать одну станцию ​​по одному маршруту несколько раз. Я пытался предотвратить это с помощью команды member, но кажется, что она не работает всегда. Как я могу это исправить?

Вот код:

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