1

我正在为我在 Prolog 中的项目而苦苦挣扎。我的问题是,给定一个包含line(NameOfLine, Type, ListOfStations). 例如:

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

其中e是两条线的交叉站(实际的线文件非常复杂,包含十几条线,数百个站)。我必须做经典的图形问题,比如查找路由、计算成本等。

我知道我必须在开始之前构建一个无向图,所以我尝试了这样的事情:

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 回答