PrologSWI - PathFinding

Question

Я хочу найти путь от станции A до станции B, которая работает, однако путь, который я придумал, повсюду, он иногда идет туда и обратно между двумя станциями, которые выключены конечно, возвращается к предыдущей точке, а затем выходит за пределы станции B и возвращается к ней, предоставляя мне дубликаты и нежелательные станции на пути.

Одна вещь, которую я заметил, может быть проблемой в том, что некоторые станции - это станции обмена с тем же именем, но другая линия на них. Это arc'd станции:

%adjecent stations % 

% Central line 

adjacent(nh,lg,central,4). 
adjacent(lg,oc,central,4). 
adjacent(oc,tc,central,4). 
adjacent(tc,cl,central,4). 
adjacent(cl,ls,central,4). 
adjacent(ls,bg,central,4). 

% Victoria Line 
adjacent(br,vi,victoria,4). 
adjacent(vi,oc,victoria,4). 
adjacent(oc,ws,victoria,4). 
adjacent(ws,kx,victoria,4). 
adjacent(kx,fp,victoria,4). 

% Northern Line 
adjacent(ke,em,northern,4). 
adjacent(em,tc,northern,4). 
adjacent(tc,ws,northern,4). 
adjacent(ws,eu,northern,4). 

% Metropolitan Line 
adjacent(al,ls,metropolitan,4). 
adjacent(ls,kx,metropolitan,4). 
adjacent(bs,fr,metropolitan,4). 

% Bakerloo Line 
adjacent(ec,em,bakerloo,4). 
adjacent(em,oc,bakerloo,4). 
adjacent(oc,pa,bakerloo,4). 
adjacent(pa,wa,bakerloo,4). 

... и вот правило:

next(X,Y,L):-adjacent(X,Y,L,_). 
next(X,Y,L):-adjacent(Y,X,L,_). 
direct_connect(X,Y,L,S,F):- 
       next(X,Z,L), 
       not(member(Z,S)), 
       direct_connect(Z,Y,L,[Z|S],F). 
direct_connect(X,Y,L,S,[Y|S]):- next(X,Y,L). 
one_change(X,Y,L,F):- 
       direct_connect(X,Z,L,[X],F1), 
       direct_connect(Z,Y,L2,[Z|F1],F), 
       L\=L2. 
exist(X):-next(X,_,_). 
member(X,[X|_]). 
member(X,[_|T]):-member(X,T). 

route(X,Y,F):-exist(X),exist(Y), 
       direct_connect(X,Y,_,[X],F), 
       write('Direct Connection'),nl, 
       revwrite(F). 

route(X,Y,F):-exist(X),exist(Y), 
       one_change(X,Y,_,F), 
       write('One change required'),nl, 
       revwrite(F). 

revwrite([X]):-write(X). 
revwrite([H|T]):-revwrite(T), write('->'),write(H). 

С тестом случае:

route(em,ls,Route). 

... выход я получаю является:

One change required 
em->tc->ws->tc->tc->cl->ls->bg->ls 
Route = [ls, bg, ls, cl, tc, tc, ws, tc, em] 

Я не понимаю, почему я получаю Dupli пропагандисты. Как я могу избежать того, чтобы идти по пути, возвращаться и ходить повсюду?

Answer 1

Проблема (одна проблема, по крайней мере) находится в direct_connect/5; в следующей статье

direct_connect(X,Y,L,S,F):- 
       next(X,Z,L), 
       not(member(Z,S)), 
       direct_connect(Z,Y,L,[Z|S],F). 

вы не навязываю, что Z отличается от Y.

Предложение: изменить его следующим образом, введение Z \= Y

direct_connect(X,Y,L,S,F):- 
       next(X,Z,L), 
       Z \= Y, 
       not(member(Z,S)), 
       direct_connect(Z,Y,L,[Z|S],F).