Как рассчитать время полета и длину пути в Прологе

Question

У меня есть эта база данных в прологе, и я хотел бы рассчитать:

1) flightTime (Start, Destination, Time, Path), чтобы вычислить время полета для всех возможных путей.

2) pathLength (Path, Length) для вычисления длины заданного пути (path будет списком).

3) shorttestPath (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 для прямых рейсов и непрямых рейсов только с одной остановкой, но мне снова нужны все возможные пути.

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 

Теперь, чтобы найти кратчайший путь, есть много способов.Самый простой и очевидный способ - использовать что-то вроде:

Сохранить все пути -> Длина кодирования путей -> Сортировать по длине -> Выбрать путь с минимальной длиной:

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