Консультант бюро путешествий
В данном разделе показано, как разработать программу, которая дает консультации по планированию авиаперелетов. Эта программа является довольно простым консультантом, но обладает способностью отвечать на некоторые важные вопросы, наподобие приведенных ниже.
• В какие дни недели имеется прямой вечерний рейс из Любляны в Лондон?
• Как долететь из Любляны в Эдинбург в четверг?
■ Мне нужно посетить Милан, Любляну и Цюрих, отправившись из Лондона во вторник и вернувшись в Лондон в пятницу. В какой последовательности мне следует посещать эти города, чтобы не приходилось совершать больше одного перелета в каждый день путешествия?
Эта программа должна быть сосредоточена вокруг базы данных, содержащей информацию об авиарейсах. Такая информация представлена в виде следующего отношения с тремя параметрами: timetable) Placel, Place2, ListOfFlights)
где ListOfFlights — список структурированных элементов в следующей форме: D«partureTime / ArrivalTirce / FlightNumber / ListOfDays
В данном случае знак операции " ■■'" лишь соединяет друг с другом компоненты структуры и, безусловно, не означает арифметического деления. Переменная ListOfDays может представлять собой либо список дней недели, либо атом alldays с обозначением ежедневного рейса. Одно из предложений отношения timetable может, например, выглядеть таким образом: timetable С london, edinburgh, ( 9:40 / 10:50 J Ьа4733 / alldays, 19:40/ 20:50 / ba4833 / [mo, tu, we, th, f r, su] ]).
Значения времени представлены как структурированные объекты с двумя компонентами (часы и минуты), которые соединены знаком операции ":".
Главная проблема состоит в том, что необходимо иметь возможность точно определять маршруты между двумя указанными городами в указанный день недели. Это требование можно учесть в программе с помощью следующего отношения с четырьмя параметрами: route; Placel, Piace2, Day, Route)
где Route — последовательность авиаперелетов, которая удовлетворяет следующим критериям.
1. Начальной точкой маршрута является Placel.
2. Конечная точка маршрута — Р1асе2.
3. Все авиаперелеты должны происходить в один и тот же день недели, Day.
4. Все авиаперелеты, заданные в маршруте Route, должны осуществляться с помощью авиарейсов, которые определены в отношении timetable.
5. Должно быть предусмотрено достаточное время для пересадки с одного авиарейса на другой.
Глава 4. Использование структур: примеры программ
Маршрут представлен в виде списка структурированных объектов, имеющих следующую форму: From / То / FlightNumber / Departure J:ime
Кроме того, предусмотрено использование перечисленных ниже вспомогательных предикатов.
1) flight ( Placel, Place2, Day, FlightNum, DepTine, ArrTime)
Этот предикат указывает, что существует авиарейс FlightNum, на котором может быть осуществлен авиаперелет из города Placel в город Р1асе2 в день недели Day, с указанным временем отправления и прибытия.
2) deptime; Route, Time)
Временем отправления по маршруту Route является Time.
3)transfer С Timel, Time2)
Между значениями времени Timel и Time2 должен быть предусмотрен промежуток времени не меньше 40 минут, которого будет достаточно для пересадки с одного рейса на другой.
Проблема поиска маршрута напоминает задачу моделирования недетерминированного конечного автомата, рассматриваемую в предыдущем разделе. Между этими двумя проблемами имеются указанные ниже аналогии.
• Состояния конечного автомата соответствуют пребыванию в тех или иных го
родах.
• Переходы между двумя состояниями соответствуют перелету из одного города в другой.
• Отношение transition конечного автомата соответствует отношению timetable.
• Эмулятор конечного автомата находит в графе переходов путь от начального состояния к конечному; программа планирования путешествий находит маршрут между начальной и конечной точками маршрута.
Поэтому нет ничего удивительного в том, что отношение route может быть определено по аналогии с отношением accepts, за исключением того, что в этом случае отсутствуют скрытые переходы. При этом могут рассматриваться два перечисленных ниже случая.
1. Выполнение задачи с помощью прямого рейса. Если существует прямой рейс
между городами Placel и ?1асе2, то маршрут состоит из этого рейса:
route; Placel, Place2, Day, [ Placel / Flace2 / From / Dep ]) :-flight! Placel, Flace2, Day, Fnum, Dep, An).
2. Выполнение задачи с помощью рейсов с пересадкой. Маршрут между городами
Р1 и F2 состоит из первого рейса, от города Р1 до некоторого промежуточного
города РЗ, за которым следует рейс из города РЗ в город Р2. Кроме того, долж
но быть достаточно времени между прибытием первого рейса и отправлением
второго для выполнения пересадки.
route ( PI, P2, Day, [M / РЗ / Fnuml / Depl | RestRoute]) :-route( РЗ, Р2, Day, RestRoute), flight! PI, РЭ, Day, Fnuml, Depl,Arrl), cleptimel RestRoute, Dep2), transfer) Arrl, Dep2).
Программы для вспомогательных отношений f 1 i ght, transferи deptime можно легко разработать, и они включены в полную программу планирования путешествий, приведенную в листинге 4.1. Кроме того, в нее в качестве примера включена база данных о расписании авиаперелетов.
108 Часть I. Язык Prolog
Листинг 4.1. Планировщик маршрутов, состоящих из отдельных авиаперелетов, и вымышленное расписание авиарейсов
Ч ПЛАНИРОВЩИК МАРШРУТОВ ПОЛЕТА
:- opt 50, xfy, : ) .
troute! Placel, Place2, Day, Route):
I Route - последовательность полетов, начинающихся s городе Placel и заканчивающихся в городе Р1асе2, проводимых в день Day
route[ PI, Р2 , Day, [ PI / Р2 / Frmm / Deptime ] ) :- % Прямой рейс flight! PI, P2, Day, Fnura, Deptime, _ ) .
I Рейс с пересадками
route ( PI, P2, Day, [ {Pi / P3 / Fnuml / Depl) I RestRoute] ) :-
route С РЗ, P2, Day, RestRoute) ,
flight! PI, P3, Day, Fnuml, Depl, Arrl),
deptime) RestRoute, Dep2), % Время отправления DC маршруту
transfer! Arrl, Dep2) . % Достаточное время для пересадки
flight) Placel, Place2 , Day, Fnuni, Deptime, Arrtime) :-timetable! Placel, Place2, Flightlist),
member! Deptime / Arrtiine / Fnum / Daylist , Flightlist), flyday! Day, Daylist) .
flyday! Day, Daylist) :-member! Day, Daylist) .
flyday) Day, alldays):-
member) Day, [mo, tu,we, th, f r, sa, su] ).
deptime) [ PI / P2 / Fnum / Dep _), Dep).
transfer) Hoursl :Minsl, Hours2:Mins2) :-
60 * (Hours2 - Hoursl) + Mins2 - Hinsl >- 40. member) X, [X | LJ ).
member! H, [Y \ L] ) :-member! X, L) .
% БАЗА ДАННЫХ О ПОЛЕТАХ
timetable[ edinburgh, london,
[ Э:40 / 10:50/ ba4733 /alldays, 13:40 / 14:50 / Ьа4773 / alldays, 19:40 / 20:50 / ba4833 / (mo,tu,we,th,fr,su] ] ).
timetable! london, edinburgh,
[ 9:40 / 10:50 /Ьа4732 / alldays,
11:40 / 12;50 / ba4752 / alldays,
13:40 / 19:50 / ba4S22 / [mo,tu,we,th,fr] ] ).
timetable) london, ljubljana,
[ 13:20/ 16:20 / jp212 / (mo, tu,we,fГ,SU]f 16:30 / 19:30 / Ьа473 / [mo, we,th,sa] ] ).
timetable! london, Zurich,
[ 9:10 / 11:45/ ba614 / alldays, 14:45/ 17:20 / sr805 / alldays ] ).
timetable I london, milan,
[ 8:30 / 11:20 /baElO / alldays, 11:00 / 13:50 / az459 / alldays ] ).
Глава 4. Использование структур: примеры программ
timetable! ljubljana, Zurich,
[ 11:30 / 12:40 / jp322 / [tu,th] ! ).
timetable) ljubljana, london,
[ 11:10 / 12:20 / jp211 / [mo,tu,we,fr,su], 20:30 / 21:30 / ba4"72 / Imo, we, th, sa] ] >.
timetable! milan, london,
[ 9:10 / 10:00 / az458 / alldays, 12:20 / 13:10 / ba51.1 / alldays ] ).
timetable! milan, Zurich,
[ 9:25 10:15 / sr621 / alldays, 12:45 / 13:35 / Sr623 / alldays ] ).
timetable! Zurich, ljubljana,
[ 13:30 / 14:40 / jp323 / (tll,th] ] ) .
timetablei Zurich, london,
[ 5:00 / 5:40 / ba6l3 / [mo,tu,we,th,fr,sa], 16:10 / 16:55 / sr8Q6 / [mo, tu,we, th, t r, su] ] ) .
timetable! Zurich, milan,
[7:55 / 8:45 /sr620 / alldays] ).
query3 (Cityl,City2,City3,FN1,FN2,FN3,FN41 :-
permutation! [milan,ljubljana,Zurich] , [Cityl,City2,City3]),
flight! london, Cityl, tu, FN1, Depl, Arrl}, flight! Cityl, City2, we, FN2, Dep2, Arr2}, flight! City2, City3, th, FN3, Dep3, Arr3), flight: City3, london, ft, FN4, Dep4, Arr4) .
cone! [) , L, L) ,
cone([X|LI],L2, [X|L3]) :-СОПС(L1,L2,L3).
permutation! [] , []) ,
permutation! L, [X I P] I :-del( x, l, LI), permutation! Llr P).
del ( X, [X|L] ,L] .
del! X, [Y|L], [Y|L1]) :-del! X, L, LI) .
Рассматриваемый планировщик маршрутов является чрезвычайно простым и способен заниматься исследованием даже таких маршрутов, которые, безусловно, никуда не ведут. Тем не менее он успешно справляется со своей работой, если база данных об авиарейсах невелика. Л при наличии действительно крупной базы данных требуется более интеллектуальное планирование, которое позволило бы справиться с большим количеством потенциальных рассматриваемых маршрутов.
Ниже приведены некоторые примеры вопросов к программе,
• В какие дни недели существует прямой вечерний рейс из Любляны в Лондон?
1- flight! ljubljana, london, Day, _, DeptHour:_, _) , DeptHour >= 18. Day = mo; Day - we;
• Как можно добраться из Любляны в Эдинбург в четверг?
?- route! ljubljana, edinburgh, th, R) .
P, = [ ljubljana / zurich / jp322 / 11:30, zuricb / london / sr806 /