Umgang mit Kreisrouten im Routenfindungsalgorithmus

Question

Ich habe ein Programm in Prolog geschrieben, um Routen zwischen Metrostationen zu finden. Es funktioniert so ziemlich wie erwartet für lineare Routen (A -> B -> C -> D), aber ich weiß nicht, wie man die kreisförmigen (A -> B -> C -> D -> A -> B -> ...) und so weiter behandelt.

Die Datenbank:
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 
    ] 
). 

Und das Programm:

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

Linear Routen:a, c
Rundweg:b1, b2

Nun wollen wir den folgenden Fall in Betracht ziehen. Zeigt alle Routen von station2 bis station21 an. Die Reihenfolge der Ergebnisse wurde der Einfachheit halber geändert.

?- 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]] ; 
... 
... 

Das Problem:

Das Problem ist, wie das Programm bewusst zu machen, dass b1 und b2 die gleiche Strecke, auch wenn die Namen sind unterschiedlich. Ich mag ausschließen Routen wie:

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

, weil der Abstand zwischen station3 und station8 kann auf beide b1 oder b2, keine Notwendigkeit, um zwischen ihnen durchgeführt werden.

Also im Grunde möchte ich beide Routen als eins behandelt werden, aber unterschiedliche Namen haben, abhängig von der Richtung der Suche. Es ist nicht eine Frage der Effizienz an diesem Punkt, es geht darum, zwischen b1 und b2 auf der gleichen Route nicht zu springen.

EDIT:

• nach dem ersten Ergebnis Stoppt Rückzieher ist keine Option
• Diese Zugstrecke b1/b2 unter singulär ist 10+, so bin ich nicht unbedingt für eine generische Lösung suchen, so Atom Namensprüfung würde Arbeit (keine Ahnung, wie es geht).

Answer 1

Ihr Problem ist im Grunde eine grafische Darstellung, Suche, wo der Graph:

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

Ihr aktueller Ansatz ist Depth First Search (DFS) auf der Grafik, von der Quelle beginnen, und die Tiefe geht zuerst bis stuck/die Lösung zu finden. Einer der bekannten Nachteile von DFS sind Endlosschleifen.

Der klassische Weg, um dieses Problem zu handhaben ist ein visited Satz hinzuzufügen, wenn Sie zuerst „erforschen“ ein Knoten (Station), können Sie es zum visited Satz hinzufügen und vermeiden Sie Knoten erweitern, die bereits in diesem visited sind einstellen.