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

Братко Иван

?- допускается( S, [a, b]).

S = s1;

S = s3

Как ни странно, мы можем спросить также "Каковы все цепочки длины 3, допустимые из состояния s1?"

?- допускается( s1, [X1, Х2, X3]).

X1 = а

X2 = а

X3 = b;

X1 = b

X2 =

а

X3 = b;

nо

(нет)

Если мы предпочитаем, чтобы допустимые цепочки выдавались в виде списков, тогда наш вопрос следует сформулировать так:

?- Цепочка = [ _, _, _ ], допускается( s1, Цепочка).

Цепочка = [а, а, b];

Цепочка = [b, а, b];

nо

(нет)

Можно проделать и еще некоторые эксперименты, например спросить: "Из какого состояния автомат допустит цепочку длиной 7?"

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

конечное

,

переход

и

спонтанный

. В автомате, изображенном на рис. 4.3, отсутствуют циклические "спонтанные пути" (пути, состоящие только из спонтанных переходов). Если на рис. 4.3 добавить новый переход

спонтанный( s1, s3)

то получится "спонтанный цикл". Теперь наша модель может столкнуться с неприятностями. Например, вопрос

?- допускается( s1, [а]).

приведет к тому, что модель будет бесконечно переходить в состояние s1, все время надеясь отыскать какой-либо путь в конечное состояние.

Упражнения

4.4. Почему не могло возникнуть зацикливание модели исходного автомата на рис. 4.3, когда в его графе переходов не было "спонтанного цикла"?

4.5. Зацикливание при вычислении

допускается

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

допускается

. Указание: добавьте третий аргумент — максимально допустимое число переходов:

допускается( Состояние, Цепочка, Макс_переходов)

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 минут для пересадки с одного рейса на другой.

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

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

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