Назад | Содержание| Вперёд 4. 4. Планирование поездки В данном ра...

Назад | Содержание| Вперёд

4. 4. Планирование поездки

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

По каким дням недели есть прямые рейсы из Лондона в Любляну?

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

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

Центральной частью программы будет базаданных, содержащая информацию о рейсах. Этаинформация будет представлена в видетрехаргументного отношения:

расписание( Пункт1,Пункт2, Список_рейсов)

где Список_рейсов - этосписок, состоящий из структурированных объектоввида:

Время_отправления /Время_прибытия / Номер_рейса

/ Список_дней_вылета

Список_дней_вылета - это либо списокдней недели, либо атом "ежедневно". Одно изпредложений, входящих в расписаниемогло бы быть, например, таким:

расписание( лондон,эдинбург,

[ 9:40 / 10:50 / bа4733/ ежедневно,

19:40 / 20:50 / bа4833 / [пн, вт, ср, чт, пт, сб]] ).

Время представлено в виде структурированныхобъектов, состоящих из двух компонент - часов иминут, объединенных оператором ":".

Главная задача состоит в отыскании точныхмаршрутов между двумя заданными городами вопределенные дни недели. Ее решение мы будемпрограммировать в виде четырехаргументногоотношения:

маршрут( Пункт1,Пункт2, День, Маршрут)

Здесь Маршрут - этопоследовательность перелетов, удовлетворяющихследующим критериям:

(1) начальная точкамаршрута находится в Пункт1;

(2) конечная точка - в Пункт2;

(3) все перелетысовершаются в один и тот же день недели - День;

(4) все перелеты, входящие вМаршрут, содержатся в определенииотношения расписание;

(5) остается достаточновремени для пересадки с рейса на рейс.

Маршрут представляется в виде спискаструктурированных объектов вида

Откуда - Куда :Номер_рейса : Время_отправления

Мы еще будем пользоваться следующимивспомогательными предикатами:

(1) рейс( Пункт1,Пункт2, День, N_рейса, Вр_отпр, Вр_приб)

Здесь сказано, что существует рейс N_рейсамежду Пункт1 и Пункт2 в деньнедели День с указанными временамиотправления и прибытия.

(2) вр_отпр( Маршрут,Время)

Время - это время отправления помаршруту Маршрут.

(3) пересадка( Время1,Время2)

Между Время1 и Время2 долженсуществовать промежуток не менее 40 минут дляпересадки с одного рейса на другой.

Задача нахождения маршрута напоминаетмоделирование недетерминированного автомата изпредыдущего раздела:

Состояния автомата соответствуют городам.

Переход из состояния в состояние соответствует перелету из одного города в другой.

Отношение переход автомата соответствует отношению расписание.

Модель автомата находит путь в графе переходов между исходным и конечным состояниями; планировщик поездки находит маршрут между начальным н конечным пунктами поездки.

Неудивительно поэтому, что отношение маршрутможно определить аналогично отношению допускает,с той разницей, что теперь нет "спонтанныхпереходов". Существуют два случая:

(1) Прямой рейс: еслисуществует прямой рейс между пунктами Пункт1и Пункт2, то весь маршрут состоит толькоиз одного перелета:

маршрут( Пункт1,Пункт2, День, [Пункт1-Пункт2 : Nр : Отпр]):-

рейс(Пункт1, Пункт2, День, Np, Отпр, Приб).

(2) Маршрут с пересадками:маршрут между пунктами Р1 и Р2состоит из первого перелета из P1 внекоторый промежуточный пункт Р3 имаршрута между Р3 и Р2. Крометого, между окончанием первого перелета иотправлением во второй необходимо оставитьдостаточно времени для пересадки.

маршрут( Р1, Р2, День,[Р1-Р3 : Nр1 : Отпр1 | Маршрут]) :-

маршрут( Р3, Р2, День, Маршрут ),

рейс(Р1, Р3, День, Npl, Oтпpl, Приб1),

вр_отпр( Маршрут, Отпр2),

пересадка( Приб1, Отпр2).

Вспомогательные отношения рейс, пересадкаи вр_отпр запрограммировать легко; мывключили их в полный текст программыпланировщика поездки на рис. 4.5. Там же приводитсяи пример базы данных расписания.

Наш планировщик исключительно прост и можетрассматривать пути, очевидно ведущие в никуда.Тем не менее его оказывается вполне достаточно,если база данных о рейсах самолетов невелика. Длябольших баз данных потребовалось бы разработатьболее интеллектуальный планировщик, который могбы справиться с большим количеством путей,участвующих в перебора при нахождении нужногопути.

Вот некоторые примеры вопросов к планировщику:

По каким дням недели существуют прямые рейсы из Лондона в Люблину?

?- рейс( лондон, любляна, День, _, _, _ ).

День = пт;

День = сб;

no (нет)

% ПЛАНИРОВЩИК ВОЗДУШНЫХ МАРШРУТОВ

:- ор( 50, xfy, :).

рейс( Пункт1, Пункт2, День, Np, ВрОтпр, ВрПриб):-

расписание( Пункт1, Пункт2, СписРейсов),

принадлежит( ВрОтпр / ВрПриб / Nр /СписДней, СписРейсов),

день_выл( День, СписДней).

принадлежит( X, [X | L] ).

принадлежит( X, [Y | L] ) :-

принадлежит( X, L ).

день_выл( День, СписДней) :-

принадлежит( День, СписДней).

день_выл( День, ежедневно) :-

принадлежит( День, [пн, вт, ср, чт,пт, сб, вс] ).

маршрут( P1, P2, День, [Р1-Р2 : Np : ВрОтпр] ) :-

% прямой рейс

рейс( P1, P2, День, Np, ВрОтпр, _ ).

маршрут( Р1, Р2, День, [Pl-P3 : Np1 : Oтпp1 | Маршрут]):-

% маршрут с пересадками

маршрут( Р3, P2, День, Маршрут ),

рейс( Р1, Р3, День, Npl, Oтпp1, Приб1),

вр_отпр( Маршрут, Отпр2),

пересадка( Приб1, Отпр2).

вр_отпр( [Р1-Р2 : Np : Отпр | _ ], Отпр).

пересадка( Часы1 : Минуты1, Часы2 : Минуты2) :-

60 * (Часы2-Часы1) + Минуты2 - Минуты1>= 40

% БАЗА ДАННЫХ О РЕЙСАХ САМОЛЕТОВ

расписание( эдинбург, лондон,

[ 9:40 / 10:50 / bа4733 / ежедневно,

13:40 / 14:50 / ba4773 / ежедневно,

19:40 / 20:50 / bа4833 / [пн, вт, ср, чт, пт,вс] ] ).

расписание( лондон, эдинбург,

[ 9:40 / 10:50 / bа4732 / ежедневно,

11:40 / 12:50 / bа4752 / ежедневно,

18:40 / 19:50 / bа4822 / [пн, вт, ср, чт, пт] ]),

расписание( лондон, любляна,

[13:20 / 16:20 / ju201 / [пт],

13:20 / 16:20 / ju213 / [вс] ] ).

расписание( лондон, цюрих,

[ 9:10 / 11:45 / bа614 / ежедневно,

14:45 / 17:20 / sr805 / ежедневно ] ).

расписание( лондон, милан,

[ 8:30 / 11:20 / bа510 / ежедневно,

11:00 / 13:50 / az459 / ежедневно ] ).

расписание( любляна, цюрих,

[11:30 / 12:40 / ju322 / [вт,чт] ] ).

расписание( любляна, лондон,

[11:10 / 12:20 / yu200 / [пт],

11:25 / 12:20 / yu212 / [вс] ] ).

расписание( милан, лондон,

[ 9:10 / 10:00 / az458 / ежедневно,

12:20 / 13:10 / bа511 / ежедневно ] ).

расписание( милан, цюрих,

[ 9:25 / 10:15 / sr621 / ежедневно,

12:45 / 13:35 / sr623 / ежедневно ] ).

расписание( цюрих, любляна,

[13:30 / 14:40 / yu323 / [вт, чт] ] ).

расписание( цюрих, лондон,

9:00 / 9:40 / bа613 /

[ пн, вт, ср, чт, пт, сб],

16:10 / 16:55 / sr806 / [пн, вт, ср, чт, пт,сб] ] ).

расписание( цюрих, милан,

[ 7:55 / 8:45 / sr620 / ежедневно ] ).

Рис. 4. 5. Планировщиквоздушных маршрутов и база данных о рейсахсамолетов.

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

?- маршрут( любляна, эдинбург, чт, R).

R = [любляна-цюрих : уu322 : 11:30, цюрих-лондон:

sr806 : 16:10,

лондон-эдинбург : bа4822 : 18:40 ]

Как мне посетить Милан, Любляну и Цюрих, вылетев из Лондона во вторник и вернувшись в него в пятницу, совершая в день не более одного перелета? Этот вопрос сложнее, чем предыдущие. Его можно сформулировать, использовав отношение перестановка, запрограммированное в гл. 3. Мы попросим найти такую перестановку городов Милан, Любляна и Цюрих, чтобы соответствующие перелеты можно было осуществить в несколько последовательных дней недели:

?- перестановка( [милан, любляна, цюрих],

[Город1, Город2, Город3] ),

рейс( лондон, Город1, вт, Np1, Oтпp1, Пpиб1),

peйc( Город1, Город2, ср, Np2, Отпр2, Приб2),

рейс( Город2, Город3, чт, Np3, Отпp3, Приб3),

рейс( Город3, лондон, пт, Np4, Отпр4, Приб4).

Город1 = милан

Город2 = цюрих

Город3 = любляна

Npl = ba510

Отпр1 = 8:30

Приб1 = 11:20

Np2 =sr621

Отпр2 = 9:25

Приб2 = 10:15

Np3 = yu323

Отпр3 = 13:30

Приб3 = 14:40

Np4 = yu200

Отпр4 = 11:10

Приб4 = 12:20

Назад | Содержание| Вперёд

Оглавление