1

我已经阅读了一些关于这个主题的教程，但我仍然不明白。

代码：

%flight(ORIGIN,DEST,DEPARTTIME,ARRIVALTIME,FLIGHTNO, DAY). Day 1=mon 7=sun
flight(singapore,london , 2310, 0520, ba58,1).
flight(singapore,london , 2310, 0520, ba58,3).
flight(singapore,london , 2310, 0520, ba58,4).
flight(singapore,london , 2310, 0520, ba58,6).
flight(london,singapore , 1000, 1610, ba24,1).
flight(london,singapore , 1000, 1610, ba24,3).
flight(london,singapore , 1000, 1610, ba24,4).
flight(london,singapore , 1000, 1610, ba24,6).
flight(london,edinburgh , 0940, 1050, ba4732,1).
flight(london,edinburgh , 0940, 1050, ba4732,2).
flight(london,edinburgh , 0940, 1050, ba4732,3).
flight(london,edinburgh , 0940, 1050, ba4732,4).
flight(london,edinburgh , 0940, 1050, ba4732,5).
flight(london,edinburgh , 0940, 1050, ba4732,6).
flight(london,edinburgh , 0940, 1050, ba4732,7).

如何找到从新加坡到爱丁堡的最快航班？

最短航班计算应包括航班之间的总飞行时间和总等待时间。

4

2 回答 2

2 
%flight(ORIGIN,DEST,DEPARTTIME,ARRIVALTIME,FLIGHTNO, DAY).
flight(singapore,london , 2310, 0520, ba58,1).
flight(singapore,london , 2310, 0520, ba58,3).
flight(singapore,london , 2310, 0520, ba58,4).
flight(singapore,london , 2310, 0520, ba58,6).
flight(london,singapore , 1000, 1610, ba24,1).
flight(london,singapore , 1000, 1610, ba24,3).
flight(london,singapore , 1000, 1610, ba24,4).
flight(london,singapore , 1000, 1610, ba24,6).
flight(london,edinburgh , 0940, 1050, ba4732,1).
flight(london,edinburgh , 0940, 1050, ba4732,2).
flight(london,edinburgh , 0940, 1050, ba4732,3).
flight(london,edinburgh , 0940, 1050, ba4732,4).
flight(london,edinburgh , 0940, 1050, ba4732,5).
flight(london,edinburgh , 0940, 1050, ba4732,6).
flight(london,edinburgh , 0940, 1050, ba4732,7).
flight(london,edinburgh , 1140, 1250, ba4735,1).
flight(london,edinburgh , 1140, 1250, ba4735,2).
flight(london,edinburgh , 1140, 1250, ba4735,3).
flight(london,edinburgh , 1140, 1250, ba4735,4).
flight(london,edinburgh , 1140, 1250, ba4735,5).
flight(london,edinburgh , 1140, 1250, ba4735,6).
flight(london,edinburgh , 1140, 1250, ba4735,7).
flight(london,edinburgh , 1840, 1950, ba4822,1).
flight(london,edinburgh , 1840, 1950, ba4822,2).
flight(london,edinburgh , 1840, 1950, ba4822,3).
flight(london,edinburgh , 1840, 1950, ba4822,4).
flight(london,edinburgh , 1840, 1950, ba4822,5).
flight(edinburgh,london , 0830, 0940, ba4733 ,1).
flight(edinburgh,london , 0830, 0940, ba4733,2).
flight(edinburgh,london , 0830, 0940, ba4733,3).
flight(edinburgh,london , 0830, 0940, ba4733,4).
flight(edinburgh,london , 0830, 0940, ba4733,5).
flight(edinburgh,london , 0830, 0940, ba4733,6).
flight(edinburgh,london , 0830, 0940, ba4733,7).
flight(edinburgh,london , 1340, 1450, ba4736,1).
flight(edinburgh,london , 1340, 1450, ba4736,2).
flight(edinburgh,london , 1340, 1450, ba4736,3).
flight(edinburgh,london , 1340, 1450, ba4736,4).
flight(edinburgh,london , 1340, 1450, ba4736,5).
flight(edinburgh,london , 1340, 1450, ba4736,6).
flight(edinburgh,london , 1340, 1450, ba4736,7).
flight(edinburgh,london , 1940, 2050, ba4833,1).
flight(edinburgh,london , 1940, 2050, ba4833,2).
flight(edinburgh,london , 1940, 2050, ba4833,3).
flight(edinburgh,london , 1940, 2050, ba4833,4).
flight(edinburgh,london , 1940, 2050, ba4833,5).
flight(edinburgh,london , 1940, 2050, ba4833,6).
flight(london,greece , 0910, 1245, ba614,1).
flight(london,greece , 0910, 1245, ba614,2).
flight(london,greece , 0910, 1245, ba614,3).
flight(london,greece , 0910, 1245, ba614,4).
flight(london,greece , 0910, 1245, ba614,5).
flight(london,greece , 0910, 1245, ba614,6).
flight(london,greece , 0910, 1245, ba614,7).
flight(london,greece , 1445, 1820, sr805,1).
flight(london,greece , 1445, 1820, sr805,2).
flight(london,greece , 1445, 1820, sr805,3).
flight(london,greece , 1445, 1820, sr805,4).
flight(london,greece , 1445, 1820, sr805,5).
flight(london,greece , 1445, 1820, sr805,6).
flight(london,greece , 1445, 1820, sr805,7).
flight(greece,london , 0900, 1140, ba613,1).
flight(greece,london , 0900, 1140, ba613,2).
flight(greece,london , 0900, 1140, ba613,3).
flight(greece,london , 0900, 1140, ba613,4).
flight(greece,london , 0900, 1140, ba613,5).
flight(greece,london , 0900, 1140, ba613,6).
flight(greece,london , 1610, 1855, sr806,1).
flight(greece,london , 1610, 1855, sr806,2).
flight(greece,london , 1610, 1855, sr806,3).
flight(greece,london , 1610, 1855, sr806,4).
flight(greece,london , 1610, 1855, sr806,5).
flight(greece,london , 1610, 1855, sr806,7).
flight(london,paris , 0830, 1030, ba510,1).
flight(london,paris , 0830, 1030, ba510,2).
flight(london,paris , 0830, 1030, ba510,3).
flight(london,paris , 0830, 1030, ba510,4).
flight(london,paris , 0830, 1030, ba510,5).
flight(london,paris , 0830, 1030, ba510,6).
flight(london,paris , 0830, 1030, ba510,7).
flight(london,paris , 1310, 1510, az459,1).
flight(london,paris , 1310, 1510, az459,2).
flight(london,paris , 1310, 1510, az459,3).
flight(london,paris , 1310, 1510, az459,4).
flight(london,paris , 1310, 1510, az459,5).
flight(london,paris , 1310, 1510, az459,6).
flight(london,paris , 1310, 1510, az459,7).
flight(paris,london , 0910, 1020, ba511,1).
flight(paris,london , 0910, 1020, ba511,2).
flight(paris,london , 0910, 1020, ba511,3).
flight(paris,london , 0910, 1020, ba511,4).
flight(paris,london , 0910, 1020, ba511,5).
flight(paris,london , 0910, 1020, ba511,6).
flight(paris,london , 0910, 1020, ba511,7).
flight(paris,london , 1220, 1330, az460,1).
flight(paris,london , 1220, 1330, az460,2).
flight(paris,london , 1220, 1330, az460,3).
flight(paris,london , 1220, 1330, az460,4).
flight(paris,london , 1220, 1330, az460,5).
flight(paris,london , 1220, 1330, az460,6).
flight(paris,london , 1220, 1330, az460,7).
flight(paris,rome , 1130, 1240, jp322,2).
flight(paris,rome , 1130, 1240, jp322,3).
flight(paris,rome , 1130, 1240, jp322,4).
flight(rome,paris , 1330, 1440, jp323,2).
flight(rome,paris , 1330, 1440, jp323,3).
flight(rome,paris , 1330, 1440, jp323,4).
flight(rome,greece , 1440, 1630, fs619,1).
flight(rome,greece , 1440, 1630, fs619,3).
flight(rome,greece , 1440, 1630, fs619,4).
flight(rome,greece , 1440, 1630, fs619,5).
flight(greece,rome , 1100, 1310, fs620,1).
flight(greece,rome , 1100, 1310, fs620,3).
flight(greece,rome , 1100, 1310, fs620,4).
flight(greece,rome , 1100, 1310, fs620,5).


% Start menu
start :- repeat,nl,nl,
         nl, write('============================='), 
         nl, write(' FLIGHT ENQUIRY SYSTEM '),
         nl, write('============================='),
         nl, write('1) Preferred Direct'),
         nl, write('2) Preferred Fastest'),
         nl, write('3) Quit'),
         nl, nl, read(Option),
         option(Option).


% option 1 will terminate the program
option(1) :- nl, write('Please Day of Flight in Numberic format (1 for Mon, 7 for Sun: '), 
read(Day),
nl, write('Origin Country: '),
read(Origin), checkOCountry(Origin, 0), nl, write('Dest Country: '),
read(Dest), checkDCountry(Dest, 1)->
plane(Board,0),
plane(Arrive,1),
flightInfo(Board, Arrive,Start,End,FlightNo,Day),
calculateTime(Start,End, DH,DM),
nl,write('Flight No: '),write(FlightNo),
%checkDH(DurH,DurM), 
nl,write('Flight Dur: '),write(DH),write(':'),write(DM),
retractall(plane(X,Y)),!,fail.  

% option 3 will terminate the program
option(3) :- nl, write('Program has terminated!').


% check if a country is valid
checkOCountry(OCountry, Indicator) :- flight(OCountry,_,_,_,_,_) -> asserta(plane(OCountry, Indicator)); nl,write('Origin Country is invalid! Enter a valid Country: '), read(NewCountry),checkOCountry(NewCountry, Indicator).
checkDCountry(DCountry, Indicator) :- flight(_,DCountry,_,_,_,_) -> asserta(plane(DCountry, Indicator)); nl,write('Destination Country is invalid! Enter a valid Country: '), read(NewCountry),checkDCountry(NewCountry, Indicator).

flightInfo(Origin, Dest,Start,End, FlightNo,Day) :- flight(Origin, Dest,Start,End,FlightNo,Day).


calculateTime(Start, End, DH,DM):- OriMin is mod(Start, 100), DestMin is mod(End, 100), OriHour is (Start - OriMin)/100, DestHour is (End - DestMin)/100,
Y is DestHour - OriHour, X is DestMin - OriMin, 
(Y < 0 -> checkDH(OriHour, OriMin, DestHour,DestMin, DH, DM);
X < 0 -> checkDM(Y,X, DM, DH);
       DM is X, DH is Y
    ).

checkDM(Y, X , DM, DH):- DM is X + 60, DH is Y-1.
checkDH(OriHour, OriMin, DestHour,DestMin, DH, DM) :- THour1 is ((24-OriHour)+DestHour), TMin1 is 0-OriMin,
(TMin1< 0 -> THour is THour1 -1, TMin is ((60+ TMin1)+DestMin);
THour is THour1, TMin is TMin1
), 
(TMin > 60 -> DH is (THour + (TMin//60)), DM is mod(TMin, 60) ;
DH is THour, DM is TMin
).
于 2013-04-28T14:37:57.400 回答
1

分支定界最短路径算法可以通过restart来实现。该算法不使用任何动态数据库，只使用回溯和递归。假设我们有这个图表：

在此处输入图像描述

我们可以在 Prolog 中将其表示为以下事实：

% edge(-Vertex, -Vertex)
edge(a, b).         edge(a, c).
edge(a, d).         edge(b, c).
edge(c, d).         edge(c, e).
edge(d, e).

我们首先需要一个有界路径查找器。这可以实现为一个谓词，它接受一个上限，然后返回从上限中减去的跳数，并保证结果永远不会低于零：

% path(+Vertex, +Vertex, +Integer, -Integer)
path(X, X, N, N).
path(X, Y, N, M) :- N > 0,
   H is N-1,
   edge(X, Z),
   path(Z, Y, H, M).

有界路径查找器是非确定性的，并使用回溯进行搜索。我们现在添加一个进一步的谓词，它通过递归地使用较小的上限来重新启动路径查找器，只要找到路径。这样可以找到最小的长度：

% bb_path(+Vertex, +Vertex, +Integer, -Integer)
bb_path(X, Y, N, M) :- N > 0,
   H is N-1,
   path(X, Y, H, K), !,
   L is H-K,
   bb_path(X, Y, L, M).
bb_path(_, _, N, N).

请注意在谓词分支和绑定谓词中使用剪切。这是一个示例运行。我们从边数加一的上限开始。我们可以先手动多次调用path/4，模拟搜索：

?- path(a, e, 7, K), L is 7-K.
K = 3,
L = 4 
?- path(a, e, 3, K), L is 3-K.
K = 0,
L = 3 
?- path(a, e, 2, K), L is 2-K.
K = 0,
L = 2 
?- path(a, e, 1, K), L is 1-K.
No

因此，从上限 8 开始，我们逐渐得到更好的上限 4、3 和 2，直到无法再改进为止。谓词 bb_path/4 为我们做这个搜索：

?- bb_path(a, e, 8, X).
X = 2
于 2019-06-21T10:36:27.663 回答