経路探索アルゴリズムで循環経路を扱う

Question

私は地下鉄駅間のルートを見つけるためにプロローグにプログラムを書いた。それは直線ルート(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は名前が異なっていても同じルートを共有していることをプログラムに認識させる方法、です。私のようなルートを除外したい：station3とstation8の間の距離がb1またはb2のいずれかで行うことができますので、

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

を、それらの間で変更する必要はありません。

基本的には、両方のルートを1つとして扱いたいが、検索の方向によって異なる名前を付けたい。この時点で効率の問題ではなく、同じルート上でb1とb2の間をジャンプしないことです。

EDIT：最初の結果の後にバックトラックを停止

• はオプションではありません
• ルートb1/b2ので、私は必ずしも一般的な解決策を捜しているわけではない10+の中で特異なので、アトム名のチェックだろうこの列車仕事（どのようにそれを行うには考えていない）。

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

  あなたの現在のアプローチは、グラフ上Depth First Search (DFS)あるソースから始めて、解決策を見つける/立ち往生まで、第1の深さを行く：

Answer 1

あなたの問題は、基本的にグラフがあるグラフ探索、です。 DFSの既知の欠点の1つは、無限ループです。

この問題を処理するための古典的な方法は、あなたが最初のノード（ステーション）「を探る」とき、あなたはvisitedセットに追加し、visitedセットを追加することで、あなたはこのvisitedに既にある任意のノードを展開避けますセット。