algorithm - 在火车时刻表中找到一条路，并使用 line-nr 获取换乘站

Question

我正试图在火车时刻表中找到一种方法，并获取换乘站和线路编号。但是当你必须换乘火车时，我遇到了一些麻烦。首先是时间表数据库中的代码和(长)片段。

数据库

%Linie 3A (Richtung Wiler Mann) 
%          lineNr, A,B,time(minute)
verbindung('3A',[pirnaischer, platz], [albertplatz], [18, 28, 38, 48, 58, 08]).
verbindung('3A',[albertplatz], [bahnhof, neustadt], [23, 33, 43, 53, 03, 13]).
verbindung('3A',[bahnhof, neustadt], [hansastraße], [25, 35, 45, 55, 05, 15]).
verbindung('3A',[hansastraße], [liststraße], [26, 36, 46, 56, 06, 16]).
verbindung('3A',[liststraße], [trachenberger, platz], [30, 40, 50, 00, 10, 20]).
verbindung('3A',[trachenberger, platz], [hubertusplatz], [33, 43, 53, 03, 13, 23]).
verbindung('3A',[hubertusplatz], [wilder, mann], [35, 45, 55, 05, 15, 25]).
verbindung('3A',[wilder, mann], [xxx1], [38, 48, 58, 08, 18, 28]). 
%xxx ist hier damit man auch die ankuftszeiten an der Enthaltestelle angeben kann.

%Linie 3B = Linie 3 Richtung coschütz
verbindung('3B',[wilder, mann],[hubertusplatz], [04, 14, 24, 34, 44, 54]). 
verbindung('3B',[hubertusplatz],[trachenberger, platz], [06, 16, 26, 36, 46, 56]).
verbindung('3B',[trachenberger, platz],[liststraße], [08, 18, 28, 38, 48, 58]).
verbindung('3B',[liststraße],[hansastraße], [11, 21, 31, 41, 51, 01]).
verbindung('3B',[hansastraße], [bahnhof, neustadt], [14, 24, 34, 44, 54, 04]).
verbindung('3B',[bahnhof, neustadt], [albertplatz],[16, 26, 36, 46, 56, 06]).
verbindung('3B',[albertplatz], [pirnaischer, platz], [18, 28, 38, 48, 58, 08]).
verbindung('3B',[pirnaischer, platz], [xxx2], [23, 33, 43, 53, 03, 13]).

%Linie 1 (Richtung leutewitz)
verbindung('1A',[pirnaischer, platz],[postplatz],[31,41,51,01,11,21]).
verbindung('1A',[postplatz],[bahnhof, mitte],[34,44,54,04,14,24]).
verbindung('1A',[bahnhof, mitte],[waltherstraße],[38,48,58,08,18,28]).
verbindung('1A',[waltherstraße],[flügelweg],[42,52,02,12,22,32]).
verbindung('1A',[flügelweg],[gottfried-keller-straße],[45,55,05,15,25,35]).
verbindung('1A',[gottfried-keller-straße],[leutewitz],[48,58,08,18,28,38]).
verbindung('1A',[leutewitz],[xxx3],[50,00,10,20,30,40]).

%Linie 1 (Richtung prohlis, schleife)
verbindung('1B',[leutewitz],[gottfried-keller-straße],[04,14,24,34,44,54]).
verbindung('1B',[gottfried-keller-straße],[flügelweg],[06,16,26,36,46,56]).
verbindung('1B',[flügelweg],[waltherstraße],[09,19,29,39,49,59]).
verbindung('1B',[waltherstraße],[bahnhof, mitte],[12,22,32,42,52,02]).
verbindung('1B',[bahnhof, mitte],[postplatz],[17,27,37,47,57,07]).
verbindung('1B',[postplatz],[altmarkt],[21,31,41,51,01,11]).
verbindung('1B',[altmarkt],[pirnaischer, platz],[22,32,42,52,02,12]).
verbindung('1B',[pirnaischer, platz],[xxx4],[24,34,44,54,04,14]).

%Linie94
verbindung('94A',[postplatz],[bahnhof, mitte],[07, 27, 47]).
verbindung('94A',[bahnhof, mitte],[krankenhaus, friedrichstadt],[11, 31, 51]).
verbindung('94A',[krankenhaus, friedrichstadt],[waltherstraße],[14, 34, 54]).
verbindung('94A',[waltherstraße],[flügelweg],[17, 37, 57]).
verbindung('94A',[flügelweg],[gottfried-geller-straße],[20, 40, 50]).
verbindung('94A',[gottfried-keller-straße],[zschonergrundstraße],[23, 43, 03]).
verbindung('94A',[zschonergrundstraße],[am, urnenfeld],[27, 47, 07]).
verbindung('94A',[am, urnenfeld],[ludwigstraße],[32, 52, 12]).
verbindung('94A',[ludwigstraße],[erna-berger-straße],[35, 55, 15]).
verbindung('94A',[erna-berger-straße],[cossebaude, bahnhof],[37, 57, 17]).
verbindung('94A',[cossebaude, bahnhof],[xxx9],[38, 58, 18]).

搜索谓词

dlDfs(Node, Goal, Path,LinienPath,UmstiegPath, LinienLimit, ReturnPath, ReturnLinie, ReturnUmstieg) :-
    Node = Goal,
    reverse(Path, ReturnPath),
    reverse(LinienPath, ReturnLinie),
    reverse(UmstiegPath, ReturnUmstieg)
    ;
    0 =< LinienLimit,
    verbindung(Linie,Node,NewNeighbor,_),
    not(member(NewNeighbor,Path)),
    (
        (
            not(member(Linie, LinienPath)), NewLinienLimit is LinienLimit - 1,
            dlDfs(NewNeighbor, Goal, [NewNeighbor|Path], [Linie|LinienPath], [Node|UmstiegPath], NewLinienLimit, ReturnPath, ReturnLinie, ReturnUmstieg)
        )
    ;
        (dlDfs(NewNeighbor, Goal, [NewNeighbor|Path], LinienPath, UmstiegPath, LinienLimit, ReturnPath, ReturnLinie,ReturnUmstieg)
    )).

idDfsLoop(Start, Goal,L, ReturnPath, ReturnLinie, ReturnUmstieg) :-
    dlDfs(Start, Goal, [Start],[], [], L, ReturnPath, ReturnLinie, ReturnUmstieg)
    ;
    L1 is L + 1,
    idDfsLoop(Start, Goal, L1, ReturnPath, ReturnLinie, ReturnUmstieg).

idDfs(Start, Goal, ReturnPath, ReturnLinie, ReturnUmstieg) :-
    idDfsLoop(Start, Goal, 1, ReturnPath, ReturnLinie, ReturnUmstieg),
    !.

例如，如果我尝试找到从“albertplatz”到“erna-berger-straße”的路线，我必须换乘 3 次火车线路。现在，当我调用

 idDfs([albertplatz], [erna-berger-straße], Path, ChangeLine,
 ChangeStop).

程序应该返回

 Path = [The hole Path],
 ChangeLine = ['3B', '1A', '94A'],
 ChangeStop[[albertplatz],[pirnaischer,platz], [...]].

但我只得到

 Path = [The hole Path], 
 ChangeLine = ['3B', '94A'],   
 ChangeLine = [[albertplatz], [am, urnenfeld]].

我也不知道为什么。如果我测试从 [albertplatz] 到 [postplatz] 的路，程序会返回正确答案，可能是因为只有一个换站点。

编辑:

感谢@SQB 的帮助，我解决了我的问题，这是新的工作搜索谓词

搜索谓词-解决方案

dlDfs(Goal, Goal, Path, LinienPath, CurrentLine, UmstiegPath, ReturnPath, ReturnLinie, ReturnUmstieg) :-
    reverse(Path, ReturnPath),
    reverse(LinienPath, ReturnLinie),
    reverse(UmstiegPath, ReturnUmstieg).


dlDfs(Node, Goal, Path, LinienPath, CurrentLine, UmstiegPath,  ReturnPath, ReturnLinie, ReturnUmstieg) :-
    verbindung(CurrentLine, Node, NewNeighbor,_),
    not(member(NewNeighbor, Path)),
    (
        not(member(CurrentLine, LinienPath)),
        dlDfs(NewNeighbor, Goal, [NewNeighbor|Path], [CurrentLine|LinienPath], CurrentLine, [Node|UmstiegPath], ReturnPath, ReturnLinie, ReturnUmstieg)
    ;
        dlDfs(NewNeighbor, Goal, [NewNeighbor|Path], LinienPath, CurrentLine, UmstiegPath, ReturnPath, ReturnLinie,ReturnUmstieg)
    ).

dlDfs(Node, Goal, Path, LinienPath, CurrentLine, UmstiegPath, ReturnPath, ReturnLinie, ReturnUmstieg) :-
    verbindung(Linie, Node, NewNeighbor,_),
    not(Linie == CurrentLine),
    not(member(NewNeighbor, Path)),
    not(member(Linie, LinienPath)),
    dlDfs(NewNeighbor, Goal, [NewNeighbor|Path], [Linie|LinienPath], Linie, [Node|UmstiegPath], ReturnPath, ReturnLinie, ReturnUmstieg). 

Answer 1

问题出在dlDfs/9，我擅自拆分了。

dlDfs(Goal, Goal, Path, LinienPath, UmstiegPath, _LinienLimit, ReturnPath, ReturnLinie, ReturnUmstieg) :-
    reverse(Path, ReturnPath),
    reverse(LinienPath, ReturnLinie),
    reverse(UmstiegPath, ReturnUmstieg).

dlDfs(Node, Goal, Path, LinienPath, UmstiegPath, LinienLimit, ReturnPath, ReturnLinie, ReturnUmstieg) :-
    0 =< LinienLimit,
    verbindung(Linie, Node, NewNeighbor,_),
    not(member(NewNeighbor, Path)),
    (
        not(member(Linie, LinienPath)),
        NewLinienLimit is LinienLimit - 1,
        dlDfs(NewNeighbor, Goal, [NewNeighbor|Path], [Linie|LinienPath], [Node|UmstiegPath], NewLinienLimit, ReturnPath, ReturnLinie, ReturnUmstieg)
    ;
        dlDfs(NewNeighbor, Goal, [NewNeighbor|Path], LinienPath, UmstiegPath, LinienLimit, ReturnPath, ReturnLinie,ReturnUmstieg)
    ).

问题出在第二个。你做了一些检查，然后你有两条路可以走。第一个是如果新的 Linie 还没有在 LinienPath 中(顺便说一下，英语和德语的有趣组合)。您减少 LinienLimit 并再次调用 dlDfs。
但是，如果失败，例如因为 LinienLimit 低于 0，则采用第二条路径，新找到的节点仍添加到路径中，但行不会添加到行列表中 — 即使它是一个新行。

我认为，您需要做的不仅仅是检查该线路是否在已占用线路列表中，而且还要检查您找到连接的线路是否是您当前乘坐的线路。

我的建议是将谓词拆分为多个子句，而不是使用分号。然后，对于 dlDfs，您有几种情况需要定义。

1. 您已经找到了目标。这是我已经拆分的那个。
2. 您找到一个新的连接，与您已经使用的线路相同。
3. 您找到了一条新线路，但它位于您之前从未乘坐过的线路上。

---

一个完全不同的方法是检查你的起点在哪条线上，你的目标在哪条线上，以及如何连接这些线。
人类就是这样做的:“啊，是的，Erna Bergerstraße 在 94 号线，我现在在 3 号线的 Albertplatz，让我们看看，这些线路没有连接，但我可以在 Pirnaischer Platz 换到上 1 号线，然后在 Ludwigstrasse 换上 94 号线去 Erna Bergerstraße。”

---

另外，您有一次拼错了“gottfried-keller-straße”。