我正在为我在 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).
我认为原因可能是图表中的循环或搜索中的无限循环,我怎样才能避免这种问题但仍然找到所有可能的路径?