Консультант бюро путешествий

В данном разделе показано, как разработать программу, которая дает консульта­ции по планированию авиаперелетов. Эта программа является довольно простым консультантом, но обладает способностью отвечать на некоторые важные вопросы, наподобие приведенных ниже.

• В какие дни недели имеется прямой вечерний рейс из Любляны в Лондон?

• Как долететь из Любляны в Эдинбург в четверг?

■ Мне нужно посетить Милан, Любляну и Цюрих, отправившись из Лондона во вторник и вернувшись в Лондон в пятницу. В какой последовательности мне следует посещать эти города, чтобы не приходилось совершать больше одного перелета в каждый день путешествия?

Эта программа должна быть сосредоточена вокруг базы данных, содержащей ин­формацию об авиарейсах. Такая информация представлена в виде следующего отно­шения с тремя параметрами: timetable) Placel, Place2, ListOf Flights)

где 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,:).

t route! 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! Ll_r 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 /