在寻路由算法中处理循环路由

Question

我在prolog中编写了一个程序，用于查找地铁站之间的路线。对于线性路线(A -> B -> C -> D)，它几乎可以按预期工作，但我不知道如何处理(A -> B -> C -> D -> A -> B -> ...)等的圆形路线。

数据库：
stations.pl

train(
a,
[
station2,
station3,
station4,
station10
]
).
train(
b1,
[   station1,
station8,
station3,
station10,
station11
]
).
train(
b2,
[
station1,
station11,
station10,
station3,
station8
]
).
train(
c,
[
station0,
station8,
station21
]
).

和程序：

rails.pl

:- include('stations.pl').
% Case: direct route (A) --> (B).
route(A, B, Trains, Acc, R) :-
train(Train, Stations),
+ member(Train, Trains),
member(A, Stations),
member(B, Stations),
append(Acc, [[A, Train, B]], R).
% Case: intermediary station/s (I) between
% departure (A) and destination (B).
route(A, B, Trains, Acc0, R) :-
train(Train, Stations),
+ member(Train, Trains),
member(A, Stations),
member(I, Stations),
A = I,
I = B,
length(Acc0, L),
L < 3, % do not find routes where more than 2 changes are needed
append(Acc0, [[A, Train, I]], Acc1),
route(I, B, [Train|Trains], Acc1, R).

线性路线：a，c
环形路线：b1，b2

现在让我们考虑以下情况。显示从station2到station21的所有路线。为简单起见，结果顺序已更改。

?- route(station2, station21, [], [], R).
R = [[station2, a, station3], [station3, b1, station8], [station8, c, station21]] ;
R = [[station2, a, station3], [station3, b2, station8], [station8, c, station21]] ;
R = [[station2, a, station3], [station3, b1, station1], [station1, b2, station8], [station8, c, station21]] ;
R = [[station2, a, station3], [station3, b2, station1], [station1, b1, station8], [station8, c, station21]] ;
...
...

问题：

问题是，如何让程序知道b1和b2共享相同的路由，即使名称不同。我想排除以下路线：

station2 (a) station3 -> station3 (b1) station1 -> 
station1 (b2) station8 -> station8 (c) station21

因为station3和station8之间的距离可以在b1或b2上完成，因此无需在它们之间更改。

所以基本上我希望两条路线被视为一条，但根据搜索方向有不同的名称。在这一点上，这不是效率问题，而是在同一条路线上不要在b1和b2之间跳跃。

编辑：

在

• 第一个结果后停止回溯不是一种选择
• 这条火车路线b1 / b2在 10+ 中是单数的，所以我不一定在寻找通用解决方案，所以原子名称检查会起作用(虽然不知道怎么做)。

Answer 1

你的问题基本上是一个图形搜索，其中图形是：

G=(V,E)
V = Stations
E =  { (u,v) | u,v are stations connected by some train }

您当前的方法是在图形上进行深度优先搜索 (DFS)，从源开始，先深入，直到卡住/找到解决方案。DFS的已知缺点之一是无限循环。

处理此问题的经典方法是添加一个visited集，当您第一次"探索"一个节点(工作站)时，将其添加到visited集中，并避免扩展此visited集中已有的任何节点。