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

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

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

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

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

Эта программа должна быть сосредоточена вокруг базы данных, содержащей ин­формацию об авиарейсах. Такая информация представлена в виде следующего отно­шения с тремя параметрами: 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 /