时间戳

首页 > 解决方案 > 如何在 Prolog 中计算飞行时间和路径长度

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

问题描述

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

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
         ).

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

飞行路径图

标签： prologshortest-path

解决方案

这是我的解决方案：

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

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

存储所有路径 -> 路径的长度编码 -> 按长度排序 -> 选择最小长度的路径：

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两个站点之间有多个路径的大型图，生成的列表可能非常大，然后排序可能非常耗时......这里的最佳实践是让长度生成最小的路径长度：

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

推荐阅读