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

Запоминание промежуточных результатов — стандартный метод, позволяющий избегать повторных вычислений. Следует, однако, заметить, что в случае чисел Фибоначчи повторных вычислений можно избежать еще и применением другого алгоритма, а не только запоминанием промежуточных результатов.

Рис. 8.2. Вычисление 6-го числа Фибоначчи процедурой фиб.

Рис. 8.3. Вычисление 6-го числа Фибоначчи при помощи процедуры фиб2, которая запоминает предыдущие результаты. По сравнению с процедурой фибздесь вычислений меньше (см. рис. 8.2).

Этот новый алгоритм позволяет создать программу более трудную для понимания, зато более эффективную. Идея состоит на этот раз не в том, чтобы определить N-e число Фибоначчи просто как сумму своих предшественников по последовательности, оставляя рекурсивным вызовам организовать вычисления "сверху вниз" вплоть до самых первых двух чисел. Вместо этого можно работать "снизу вверх": начать с первых двух чисел и продвигаться вперед, вычисляя члены последовательности один за другим. Остановиться нужно в тот момент, когда будет достигнуто N-e число. Большая часть работы в такой программе выполняется процедурой

фибвперед( М, N, F1, F2, F)

Здесь F1 и F2 — (М – 1)-e и М-e числа, а F — N-e число Фибоначчи. Рис. 8.4 помогает понять отношение фибвперед. В соответствии с этим рисунком фибвпереднаходит последовательность преобразований для достижения конечной конфигурации (в которой М = N) из некоторой заданной начальной конфигурации. При запуске фибвпередвсе его аргументы, кроме F, должны быть конкретизированы, а М должно быть меньше или равно N. Вот эта программа:

фиб3( N, F) :-

фибвперед( 2, N, 1, 1, F).

% Первые два числа Фиб. равны 1

фибвперед( М, N, F1, F2, F2) :-

М >= N. % N-e число достигнуто

фибвперед( M, N, F1, F2, F) :-

M < N, % N-e число еще не достигнуто

СледМ is М + 1,

СледF2 is F1 + F2,

фибвперед( СледМ, N, F2, СледF2, F).

Рис. 8.4. Отношения в последовательности Фибоначчи. "Конфигурация" изображается здесь в виде большого круга и определяется тремя параметрами: индексом М и двумя последовательными числами f( M-1) и f( М).

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

подсп1( Спис, Подспис) :-

начало( Спис, Подспис).

подсп1( [ _ | Хвост], Подспис) :-

% Подспис - подсписок хвоста

подсп1( Хвост, Подспис).

начало( _, []).

начало( [X | Спис1], [X | Спис2] ) :-

начало( Спис1, Спис2).

подсп2( Спис, Подспис) :-

конк( Спис1, Спис2, Спис),

конк( Спис3, Подспис, Cпис1).

подсп3( Спис, Подспис) :-

конк( Спис1, Спис2, Спис),

конк( Подспис, _, Спис2).

8.2. Определите отношение

добавить_в_конец( Список, Элемент, НовыйСписок)

добавляющее Элементв конец списка Список; результат — НовыйСписок. Оба списка представляйте разностными парами.

8.3. Определите отношение

обратить( Список, ОбращенныйСписок)

где оба списка представлены разностными парами.

8.4. Перепишите процедуру собратьиз разд. 8.5.2, используя разностное представление списков, чтобы конкатенация выполнялась эффективнее.

• Для оценки качества программы существует несколько критериев:

правильность

эффективность

простота, читабельность

удобство модификации

документированность

• Принцип пошаговой детализации — хороший способ организации процесса разработки программ. Пошаговая детализация применима к отношениям, алгоритмам и структурам данных.

• Следующие методы часто помогают находить идеи для совершенствования программ на Прологе:

Применение рекурсии : выявить граничные и общие случаи рекурсивного определения.

Обобщение : рассмотреть такую более общую задачу, которую проще решить, чем исходную.

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

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

• В пролог-системах обычно имеются средства отладки. Наиболее полезными являются средства трассировки программ.

• Существует много способов повышения эффективности программы. Наиболее простые способы включают в себя:

изменение порядка целей и предложений

управляемый перебор при помощи введения отсечений

запоминание (с помощью assert) решений, которые иначе пришлось бы перевычислять

Более тонкие и радикальные методы связаны с улучшением алгоритмов (особенно, в части повышения эффективности перебора) и с совершенствованием структур данных.

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