如何在Prolog中计算飞行时间和路径长度

Question

我在序言中有这个数据库，我想计算：

1) flightTime(Start, Destination, Time, Path) 计算所有可能路径的飞行时间。

2) pathLength(Path, Length) 计算给定路径的长度（路径将是一个列表）。

3) shortestPath(Start, Destination) 打印两个机场之间的最短路径。

flightPath(fco,jfk,10,4321).
flightPath(fco,sin,12,5671).
flightPath(sin,nrt,8,3467).
flightPath(lju,fco,4,2521).
flightPath(lju,cdg,9,8653).
flightPath(cdg,fco,3,1989).
flightPath(cdg,jfk,8,5461).
flightPath(cdg,lax,17,9321).
flightPath(jfk,lax,6,4141).
flightPath(lax,nrt,6,5743).
transferTime(fco,2).
transferTime(sin,1).
transferTime(lju,3).
transferTime(cdg,1).
transferTime(jfk,4).
transferTime(lax,4).
transferTime(nrt,1).
connection(X,Y) :- flightPath(X,Y,_,_);(flightPath(X,Z,_,_),connection(Z,Y)).

我设法获得了直飞航班和间接航班的飞行时间，只有一站，但我又需要所有可能的路径。

flightTime(X,Y,T,P) :-
  flightPath(X,Y,T,_),
  P = Y; (   flightPath(X,Z,T1,_), 
             flightPath(Z,Y,T2,_),
             transferTime(Z,T3),
             T is T1+T2+T3, P = Z
         ).

为了简单起见，我制作了一个显示所有可能路径的图表：

Answer 1

这是我的解决方案：

flightTime(X,Y,T,[Y]):- flightPath(X,Y,T,_).
flightTime(X,Y,T,[Z|TL]):- 
          flightPath(X,Z,T2,_), 
          transferTime(Z,T3), 
          flightTime(Z,Y,T1,TL), 
          T is T1+T2+T3 .

pathLength(Path, Lentgh):- length(Path,Lentgh).          

shortestPath(X,Y,P):-  once( (pathLength(P,_),flightTime(X,Y,_,P)) ).

对于flightTime/4，解决方案只是一个递归，以便找到所有可能的路径。 pathLength/2 也很前卫，没什么特别的。

示例：

?- flightTime(X,Y,T,L).
X = fco,
Y = jfk,
T = 10,
L = [jfk] ;
X = fco,
Y = sin,
T = 12,
L = [sin] ;
X = sin,
Y = nrt,
T = 8,
L = [nrt] ;
X = lju,
Y = fco,
T = 4,
L = [fco]
... and continues

现在求最短路径有很多种方法。最简单明显的方法是使用类似的东西：

Store all paths -> Length encoding of paths -> sort by length -> choose path with min length:

custom_length(L,Len-L):- length(L,Len). 
shortestPath2(X,Y,P):- 
   findall(P1,flightTime(X,Y,_,P1), L),
   maplist(custom_length,L,L1), 
   sort(L1,[_-P|_]).

示例：

?- shortestPath2(fco,nrt,P).
P = [sin, nrt].

很好，但想象一下，findall/3 将生成的列表对于两个站点之间具有多条路径的大图来说可能非常大，然后排序可能非常耗时...... 这里的最佳做法是让 length 生成最小路径长度：

shortestPath(X,Y,P):-  once( (pathLength(P,_),flightTime(X,Y,_,P)) ).

如何在Prolog中计算飞行时间和路径长度

How to calculate flight time and path length in Prolog

prolog

shortest-path