PrologSWI - PathFinding

Question

我想要找到从站点A到站点B的路径，这是可行的。但是，我想出的路径到处都是，它有时会在偏离路线的两个站点之间来回移动，返回到上一个点，然后越过站点B再返回到它，在路径中会出现重复和不需要的站点。

我注意到的一件事可能是一些车站是具有相同名称的交换站，但它们的线路不同。这些是弧形的桩号：

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

我不明白为什么我会得到重复的东西。我如何才能避免路径偏离路线，返回，并走遍所有的地方？

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