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

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

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

где Спис — исходный список, F — правило преобразования (бинарное отношение), а НовСпиc — список всех преобразованных элементов. Задачу преобразования списка Спис можно разбить на два случая:

(1) Граничный случай: Спис = []

Если Спис = [], то НовСпиc = [], независимо от F

(2) Общий случай: Спис = [X | Хвост]

Чтобы преобразовать список вида [X | Хвост], необходимо:

  преобразовать список Хвост; результат — НовХвост;

  элемент X по правилу F; результат — НовХ;

  результат преобразования всего списка — [НовХ | НовХвост].

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

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

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

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

 саll( G),

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

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

<p>8.2.2. Обобщение</p>

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

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

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

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

Преимущество такого обобщения состоит в том, что отношение n_ферзей допускает непосредственную рекурсивную формулировку:

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

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

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

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

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

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

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

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

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

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

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

(1) Пролог особенно хорошо приспособлен для задач, в которых фигурируют объекты и отношения между ними. Часто такие задачи естественно иллюстрировать графами, в которых узлы соответствуют объектам, а дуги — отношениям.

(2) Естественным наглядным изображением структурных объектов Пролога являются деревья.

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

<p>8.3. Стиль программирования</p>

Подчиняться при программировании некоторым стилистическим соглашениям нужно для того, чтобы

• уменьшить опасность внесения ошибок в программы и

• создавать программы, которые легко читать, понимать, отлаживать и модифицировать.

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

Перейти на страницу:

Похожие книги

Adobe InDesign CS3
Adobe InDesign CS3

Книга посвящена верстке и макетированию в программе Adobe InDesign CS3. Помимо того что в ней описываются возможности программы, рассматриваются также принципы и традиции верстки, приводятся примеры решения типичных задач. Все это позволит читателю не только овладеть богатым инструментарием программы, но и грамотно применять его.Материал книги разделен на логические части: теоретические сведения, инструментарий программы, решение задач, – а также рассчитан на два уровня подготовки читателей – начинающих и опытных пользователей, что выгодно отличает книгу от других изданий. Это позволит применять ее как новичкам для знакомства с программой, так и пользователям со стажем для пополнения своих знаний.

Владимир Гавриилович Завгородний , Владимир Завгородний

Программирование, программы, базы данных / Программное обеспечение / Книги по IT
C++
C++

С++ – это универсальный язык программирования, задуманный так, чтобы сделать программирование более приятным для серьезного программиста. За исключением второстепенных деталей С++ является надмножеством языка программирования C. Помимо возможностей, которые дает C, С++ предоставляет гибкие и эффективные средства определения новых типов. Используя определения новых типов, точно отвечающих концепциям приложения, программист может разделять разрабатываемую программу на легко поддающиеся контролю части. Такой метод построения программ часто называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определенных пользователем. Такие объекты просты и надежны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. Программирование с применением таких объектов часто называют объектно-ориентированным. При правильном использовании этот метод дает более короткие, проще понимаемые и легче контролируемые программы. Ключевым понятием С++ является класс. Класс – это тип, определяемый пользователем. Классы обеспечивают сокрытие данных, гарантированную инициализацию данных, неявное преобразование типов для типов, определенных пользователем, динамическое задание типа, контролируемое пользователем управление памятью и механизмы перегрузки операций. С++ предоставляет гораздо лучшие, чем в C, средства выражения модульности программы и проверки типов. В языке есть также усовершенствования, не связанные непосредственно с классами, включающие в себя символические константы, inline-подстановку функций, параметры функции по умолчанию, перегруженные имена функций, операции управления свободной памятью и ссылочный тип. В С++ сохранены возможности языка C по работе с основными объектами аппаратного обеспечения (биты, байты, слова, адреса и т.п.). Это позволяет весьма эффективно реализовывать типы, определяемые пользователем. С++ и его стандартные библиотеки спроектированы так, чтобы обеспечивать переносимость. Имеющаяся на текущий момент реализация языка будет идти в большинстве систем, поддерживающих C. Из С++ программ можно использовать C библиотеки, и с С++ можно использовать большую часть инструментальных средств, поддерживающих программирование на C. Эта книга предназначена главным образом для того, чтобы помочь серьезным программистам изучить язык и применять его в нетривиальных проектах. В ней дано полное описание С++, много примеров и еще больше фрагментов программ.

Бьёрн Страуструп , Бьярн Страустрап , Мюррей Хилл

Программирование, программы, базы данных / Программирование / Книги по IT