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

принадлежит( ВрОтпр / ВрПриб / 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

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

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

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

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

X / Y

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

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

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

удовлетворяющего требованию отсутствия нападений. Наша процедура решениедолжна будет найти подходящую конкретизацию переменных X1, Y1, Х2, Y2, …, Х8, Y8. Поскольку мы знаем, что все ферзи должны находиться на разных вертикалях во избежание нападений по вертикальным линиям, мы можем сразу же ограничить перебор, чтобы облегчать поиск решения. Можно поэтому сразу зафиксировать X-координаты так, чтобы список, изображающий решение, удовлетворял следующему, более конкретному шаблону:

[1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]

Рис. 4.6. Решение задачи о восьми ферзях. Эта позиция может быть представлена в виде списка [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1].

Нас интересует решение для доске размером 8×8. Однако, как это часто бывает в программировании, ключ к решению легче найти, рассмотрев более общую постановку задачи. Как это ни парадоксально, но часто оказывается, что решение более общей задачи легче сформулировать, чем решение более частной, исходной задачи; после этого исходная задача решается просто как частный случай общей задачи.

Основная часть работы при таком подходе ложится на нахождение правильного обобщения исходной задачи. В нашем случае хорошей является идея обобщать задачу в отношении количества ферзей (количества вертикалей в списке), разрешив количеству ферзей принимать любое значение, включая нуль. Тогда отношение решение можно сформулировать, рассмотрев два случая: