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

Братко Иван

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

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

и все более ремеслом. И все же главным остается вопрос: как возникают идеи? Большинство идей приходит из опыта, из тех задач, решения которых уже известны. Если мы не знаем прямого решения задачи, то нам может помочь уже решенная задача, похожая на нашу. Другим источником идей является повседневная жизнь. Например, если необходимо запрограммировать сортировку списка, то можно догадаться, как это сделать, если задать себе вопрос: "А как бы я сам стал действовать, чтобы расположить экзаменационные листы студентов по их фамилиям в алфавитном порядке?"

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

8.2. Как представлять себе программы на Прологе

Одной из характерных особенностей Пролога является то, что в нем допускается как процедурный, так и декларативный стиль мышления при составлении программы. Эти два подхода детально обсуждались в гл. 2 и затем многократно иллюстрировались на примерах. Какой из этих подходов окажется более эффективным и практичным, зависит от конкретной задачи. Обычно построение декларативного решения задачи требует меньших усилий, но может привести к неэффективной программе. В процессе построения решения мы должны сводить задачу к одной или нескольким более легким подзадачам. Возникает важный вопрос: как находить эти подзадачи? Существует несколько общих принципов, которые часто применяются при программировании на Прологе. Они будут обсуждаться в следующих разделах.

8.2.1. Использование рекурсии

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

(1) тривиальные, или "граничные" случаи;

(2) "общие" случаи, в которых решение получается из решений для (более простых) вариантов самой исходной задачи.

Этот метод мы использовали в Прологе постоянно. Рассмотрим еще один пример: обработка списка элементов, при которой каждый элемент преобразуется по одному и тому же правилу. Пусть это будет процедура

преобрспис( Спис, F, НовСпиc)

где

Спис

 — исходный список,

F

 — правило преобразования (бинарное отношение), а

НовСпиc

 — список всех преобразованных элементов. Задачу преобразования списка

Спис

можно разбить на два случая:

(1) Граничный случай:

Спис = []

Если

Спис = []

, то

НовСпиc = []

, независимо от

F

(2) Общий случай:

Спис = [X | Хвост]

Чтобы преобразовать список вида

[X | Хвост]

, необходимо:

преобразовать список

Хвост

; результат —

НовХвост

;

элемент

X

по правилу

F

; результат —

НовХ

;

результат преобразования всего списка —

[НовХ | НовХвост]

.

Тот же алгоритм, изложенный на Прологе:

преобрспис( [], _, []).

преобрспис( [X | Хвост], F, [НовХ | НовХвост] :-

 G =.. [F, X, НовХ],

 саll( G),

 пpeoбpcпиc( Хвост, F, НовХвост).

Одна из причин того, что рекурсия так естественна для определения отношений на Прологе, состоит в том, что объекты данных часто сами имеют рекурсивную структуру. К таким объектам относятся списки и деревья. Список либо пуст (граничный случай), либо имеет голову и хвост, который сам является списком (общий случай). Двоичное дерево либо пусто (граничный случай), либо у него есть корень и два поддерева, которые сами являются двоичными деревьями (общий случай). Поэтому для обработки всего непустого дерева необходимо сначала что-то сделать с его корнем, а затем обработать поддеревья.

8.2.2. Обобщение

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

восемьферзей( Поз)

Оно выполняется (истинно), если

Поз

 — представленная тем или иным способом позиция, удовлетворяющая условию задачи. Можно предложить следующую полезную идею: обобщить задачу, перейдя от 8 ферзей к произвольному количеству — N. Количество ферзей станет дополнительным аргументом:

n_ферзей( Поз, N)

Преимущество такого обобщения состоит в том, что отношение

n_ферзей

допускает непосредственную рекурсивную формулировку:

(1) Граничный случай: N = 0

Разместить 0 ферзей — тривиальная задача.

(2) Общий случай: N > 0

Для "безопасного" размещения N ферзей необходимо:

• получить требуемое размещение для (N - 1) ферзей и

• добавить оставшегося ферзя так, чтобы он не бил ни одного из уже поставленных ферзей.

Как только мы научимся решать более общую задачу, решить исходную уже не составит труда:

восемьферзей( Поз) :- n_ферзей( Поз, 8)

8.2.3. Использование рисунков

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

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