1

Prolog で自分のプロジェクトに苦労しています。私の問題は、動線を含むファイルがline(NameOfLine, Type, ListOfStations). 例えば：

line(m1, train, [a,b,c,d,e])
line(m2, train, [h,e,j,i])
...

ここで、e は 2 つの路線の交差する駅です (実際の路線ファイルは非常に複雑で、数百の駅を持つ多数の路線が含まれています)。ルーティングの検索、コストの計算などの古典的なグラフの質問を行う必要があります。

開始前に無向グラフを作成する必要があることはわかっていたので、次のようなことを試しました。

adjacent(X,Y,[X,Y|_]).
adjacent(X,Y,[_|T]) :- adjacent(X,Y,T).

find_edge(LArret) :- forall(adjacent(X, Y, LArret), assert(edge(X,Y))).

connected(X,Y) :- edge(X,Y) ; edge(Y,X).

graph :-
    forall(ligne(_,_,L),  find_edge(L)).

しかし、期待どおりにすべてのエッジを取得できませんでした。そのためのアドバイスをいただけますか？それとも、この種の問題を解決するのに最初は間違っていましたか?

補足質問: 提案された解決策に感謝し、最終的にエッジを定義することに成功しました。次に、このアルゴリズムの古典を試して、AとBの間のパスを見つけましたが、検索が終了しないように見えたり、プログラムが検索で動かなくなったりすることがありました。

connected(X,Y) :- edge(X,Y) ; edge(Y,X).

path(A,B,Path) :-
       travel(A,B,[A],Q), 
       reverse(Q,Path).

travel(A,B,P,[B|P]) :- 
       connected(A,B).
travel(A,B,Visited,Path) :-
       connected(A,C),           
       C \== B,
       \+member(C,Visited),
       travel(C,B,[C|Visited],Path).

その理由は、グラフのループまたは検索の無限ループである可能性があると思います。この種の問題を回避しながら、可能なすべてのパスを見つけるにはどうすればよいですか?

4

1 に答える 1

0

定義で次のコードを使用して、line/3定義のリストを作成することができましたedge/2。

adjacent(X,Y, [X,Y|_]).
adjacent(X,Y, [_|T]) :- adjacent(X,Y, T).

adjacent_lines(X,Y) :- line(_,_,L), adjacent(X,Y, L).

:- forall(adjacent_lines(X, Y), assert(edge(X, Y))).

edge/2事実で指定されているように、すべての適用可能かつ有効な事実を作成しましたline/3。
(少なくとも、SWI-Prolog では)

于 2012-12-28T10:45:43.563 に答える