Иван Братко - Программирование на языке Пролог для искусственного интеллекта Страница 24

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

:- op( 50, xfy, :).

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

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

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

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

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

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

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

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

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

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

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

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

  % прямой рейс

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

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

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

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

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

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

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

вр_отпр( [P1-Р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.  Планировщик воздушных маршрутов и база данных о рейсах самолетов.

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

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

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

День = пт;

День = сб;

no        (нет)

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

?- маршрут( любляна, эдинбург, чт, 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 = любляна

Np1 = 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

4.5. Задача о восьми ферзях

Эта задача состоит в отыскании такой расстановки восьми ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого. Решение мы запрограммируем в виде унарного отношения:

решение( Поз)

которое истинно тогда и только тогда, когда Поз изображает позицию, в которой восемь ферзей не бьют друг друга. Будет интересно сравнить различные идеи, лежащие в основе программирования этой задачи. Поэтому мы приведем три программы, основанные на слегка различающихся ее представлениях.

4.5.1. Программа 1

Вначале нужно выбрать способ представления позиции на доске. Один из наиболее естественных способов — представить позицию в виде списка из восьми элементов, каждый из которых соответствует одному из ферзей. Каждый такой элемент будет описывать то поле доски, на которой стоит соответствующий ферзь. Далее, каждое поле доски можно описать с помощью пары координат (X и Y), где каждая координата - целое число от 1 до 8. В программе мы будем записывать такую пару в виде

X / Y

где оператор "/" обозначает, конечно, не деление, а служит лишь для объединения координат поля в один элемент списка. На рис. 4.6 показано одно из решений задачи о восьми ферзях и его запись в виде списка.

После того, как мы выбрали такое представление, задача свелась к нахождению списка вида:

[X1/Y1, X2/Y2, X3/Y3, X4/Y4, X5/Y5, X6/Y6, X7/Y7, X8/Y8]