3

我需要一个谓词路由，它给出开始和结束之间的所有城市。例如：

path(chicago,atlanta).
path(chicago,milwaukee).
path(milwaukee,detroit).
path(milwaukee,newyork).
path(chicago,detroit).
path(detroit, newyork).
path(newyork, boston).
path(atlanta,boston).
path(atlanta, milwaukee).

?- routing(chicago,newyork,X).
X=[chicago,milwaukee,newyork];
X=[chicago,detroit,newyork];
X=[chicago,milwaukee,detroit,newyork];
X=[chicago,atlanta,milwaukee,newyork];
X=[chicago,atlanta,milwaukee,detroit,newyork]

我已经尝试过这个，并继续回来。

routing(FromCity,ToCity,[FromCity|ToCity]) :-
  path(FromCity,ToCity).

routing(FromCity,ToCity,[FromCity|Connections]) :- 
  path(FromCity,FromConnection), 
  path(FromConnection,ToConnection),
  path(ToConnection,ToCity),
  routing(ToConnection,ToCity,Connections).

routing(FromCity,ToCity,[]).

但它只是不断给予 

X=[chicago,milwaukee,newyork];
X=[chicago,chicago,newyork];
X=[chicago,chicago,chicago,newyork]
...
..

有人可以指出我正确的方向吗...

4

3 回答 3

4

如果你确定（根据定义）你的图是非循环的，你可以简化你的规则，利用 Prolog 深度优先搜索：

routing(FromCity, ToCity, [FromCity, ToCity]) :-
  path(FromCity, ToCity).

routing(FromCity, ToCity, [FromCity|Connections]) :- 
  path(FromCity, ToConnection),
  routing(ToConnection, ToCity, Connections).

这会在回溯中找到所有可用路径：

?- routing(chicago,newyork,X).
X = [chicago, atlanta, milwaukee, newyork] ;
X = [chicago, atlanta, milwaukee, detroit, newyork] ;
X = [chicago, milwaukee, newyork] ;
X = [chicago, milwaukee, detroit, newyork] ;
X = [chicago, detroit, newyork] ;
false.

注意列表构造的第一种和第二种模式之间的区别：[FromCity, ToCity]vs [FromCity|Connections]。这是因为当规则成功时Connections将是一个list，而ToCity将是一个原子。

如果您的图表包含循环，则此代码将循环。对于处理此问题的简单模式，您可以参考另一个答案。

于 2012-11-01T07:22:55.597 回答
1

怎么处理如下？

首先，我们选择一个比 更好的谓词名称path。怎么样edge？

edge(chicago  , atlanta  ).
edge(chicago  , milwaukee).
edge(milwaukee, detroit  ).
edge(milwaukee, newyork  ).
edge(chicago  , detroit  ).
edge(detroit  , newyork  ).
edge(newyork  , boston   ).
edge(atlanta  , boston   ).
edge(atlanta  , milwaukee).

如上所述，edge/2显然不是对称的，否则下面的查询不会成功！

?- edge(X, Y), \+ edge(Y, X).
  X = chicago  , Y = atlanta
; X = chicago  , Y = milwaukee
; X = milwaukee, Y = detroit
; X = milwaukee, Y = newyork
; X = chicago  , Y = detroit
; X = detroit  , Y = newyork
; X = newyork  , Y = boston
; X = atlanta  , Y = boston
; X = atlanta  , Y = milwaukee.

接下来，我们定义connected_to/2为 的对称闭包edge/2：

connected_to(X, Y) :- edge(X, Y).
connected_to(X, Y) :- edge(Y, X).

最后，我们将 path/4与connected_to/2：

?- path(connected_to, Path, From, To).
; From = To                   , Path = [To]
; From = chicago, To = atlanta, Path = [chicago,atlanta]
; From = chicago, To = boston , Path = [chicago,atlanta,boston]
; From = chicago, To = newyork, Path = [chicago,atlanta,boston,newyork]
...

那么... path/4(with connected_to/2) 的最一般查询是否普遍终止？

?- path(connected_to, Path, From, To), false。
假的。% 普遍终止

最后，让我们统计一下不同地面路径的总数：

?- setof(P, From^To^(path(connected_to,P,From,To),ground(P)), _Ps),
   length(_Ps, N_Ps).
N_Ps = 244.
于 2015-12-03T22:48:21.310 回答
0

这是我的解决方案，适用于有向或无向图，有或没有循环。

它还尝试找到所有路径，而无需重新访问。

c(1,2).
% ... c(X,Y) means X and Y are connected

d(X,Y):- c(X,Y).
d(X,Y):- c(Y,X).
% Use d instead of c to allow undirected graphs

findPathHelper(_, Begin, [], End):- d(Begin, End).
findPathHelper(Front, Begin, [Next|NMiddle], End):-
    not(member(Begin,Front)),
    d(Begin, Next),
    append([Front,[Begin]], NFront),
    findPathHelper(NFront, Next, NMiddle, End).

findPath(Start, End, Path):-
    findPathHelper([], Start, Middle, End),
    append([[Start],Middle,[End]], Path).
于 2015-12-03T21:38:14.497 回答