- •Иван Братко Программирование на языке Пролог для искусственного интеллекта
- •От редактора перевода
- •Предисловие
- •Предисловие автора
- •Благодарности
- •Упражнения
- •1.2. Расширение программы-примера с помощью правил
- •Упражнения
- •1.3. Рекурсивное определение правил
- •Упражнение
- •1.4. Как пролог-система отвечает на вопросы
- •Упражнение
- •1.5. Декларативный и процедурный смысл программ
- •Литература
- •Глава 2 Синтаксис и семантика Пролог-программ
- •2.1. Объекты данных
- •2.1.1. Атомы и числа
- •2.1.2. Переменные
- •2.1.3. Структуры
- •Упражнения
- •2.2. Сопоставление
- •Упражнения
- •2.3. Декларативный смысл пролог-программ
- •Упражнения
- •2.4. Процедурная семантика
- •Программа
- •Шаги вычисления
- •Упражнение
- •2.5. Пример: обезьяна и банан
- •2.6. Порядок предложений и целей
- •2.6.1. Опасность бесконечного цикла
- •2.6.2. Варианты программы, полученые путем переупорядочивания предложений и целей
- •2.6.3. Сочетание декларативного и процедурного подходов
- •2.7. Замечания о взаимосвязи между Прологом и логикой
- •Упражнение
- •Литература
- •Глава 3 Списки, операторы, арифметика
- •3.1. Представление списков
- •3.2. Некоторые операции над списками
- •3.2.1. Принадлежность к списку
- •3.2.2. Сцепление (конкатенация)
- •Упражнения
- •3.2.3. Добавление элемента
- •3.2.4. Удаление элемента
- •3.2.5. Подсписок
- •3.2.6. Перестановки
- •Упражнения
- •3.3. Операторная запись (нотация)
- •Упражнения
- •3.4. Арифметические действия
- •Упражнения
- •Глава 4 Использование структур: примеры
- •4.1. Получение структурированной информации из базы данных
- •Упражнения
- •4.2. Абстракция данных
- •Упражнение
- •4.3. Моделирование недетерминированного автомата
- •Упражнения
- •4.4. Планирование поездки
- •4.5. Задача о восьми ферзях
- •4.5.1. Программа 1
- •Упражнение
- •4.5.2. Программа 2
- •4.5.3. Программа 3
- •4.5.4. Заключительные замечания
- •Упражнение
- •Глава 5 Управление перебором
- •5.1. Ограничение перебора
- •5.1.1. Эксперимент 1
- •5.1.2. Эксперимент 2
- •5.2. Примеры, использующие отсечение
- •5.2.1. Вычисление максимума
- •5.2.2. Процедура проверки принадлежности списку, дающая единственное решение
- •5.2.3. Добавление элемента к списку, если он в нем отсутствует (добавление без дублирования)
- •5.2.4. Задача классификации объектов
- •Упражнения
- •5.3. Отрицание как неуспех
- •Упражнения
- •5.4. Трудности с отсечением и отрицанием
- •6.2. Обработка файлов термов
- •6.2.2. Вывод списков
- •6.2.3. Формирование термов
- •6.2.4. Обработка произвольного файла термов
- •Упражнения
- •6.3. Обработка символов
- •Упражнение
- •6.4. Создание и декомпозиция атомов
- •Упражнения
- •6.5. Ввод программ: consult, reconsult
- •Глава 7 Другие встроенные процедуры
- •7.1. Проверка типов термов
- •7.1.1. Предикаты var , nоnvar , atom , integer , atomic
- •7.1.2. Решение числового ребуса с использованием nonvar
- •Упражнения
- •Упражнения
- •7.3. Различные виды равенства
- •7.4. Работа с базой данных
- •Упражнения
- •7.5. Средства управления
- •Упражнения
- •Глава 8 Стиль и методы программирования
- •8.1. Общие принципы хорошего программирования
- •8.2. Как представлять себе программы на Прологе
- •8.2.1. Использование рекурсии
- •8.2.2. Обобщение
- •8.2.3. Использование рисунков
- •8.3. Стиль программирования
- •8.3.1. Некоторые правила хорошего стиля
- •8.3.2. Табличная организация длинных процедур
- •8.3.3. Комментирование
- •8.4. Отладка
- •8.5. Эффективность
- •8.5.1. Повышение эффективности решения задачи о восьми ферзях
- •8.5.2. Повышение эффективности программы раскраски карты
- •8.5.3. Повышение эффективности конкатенации списков за счет совершенствования структуры данных
- •8.5.4. Повышение эффективности зa счет добавления вычисленных фактов к базе данных
- •Упражнения
- •9.1. Представление списков. Сортировка
- •9.1.1. Замечания в некоторых альтернативных способах представления списков
- •Упражнения
- •9.1.2. Сортировка списков
- •Упражнения
- •9.2. Представление множеств двоичными деревьями
- •Упражнения
- •9.3. Двоичные справочники: добавление и удаление элемента
- •9.4. Отображение деревьев
- •Упражнение
- •9.5. Графы
- •9.5.1. Представление графов
- •9.5.2. Поиск пути в графе
- •9.5.3. Построение остовного дерева
- •Упражнение
- •Литература
- •Глава 10 Усовершенствованные методы представления множеств деревьями
- •10.1. Двоично-троичные справочники
- •Упражнение
- •Литература
- •Глава 11. Основные стратегии решения задач
- •11.1. Предварительные понятия и примеры
- •11.2. Стратегия поиска в глубину
- •Упражнения
- •11.3. Поиск в ширину
- •11.3.1. Списковое представление множества кандидатов
- •11.3.2. Древовидное представление множества кандидатов
- •Упражнения
- •11.4. Замечания относительно поиска в графах, оптимальности к сложности
- •Литература
- •Глава 12 Поиск с предпочтением: эвристический поиск
- •12.1. Поиск с предпочтением
- •Упражнение
- •12.2. Поиск c предпочтением применительно к головоломке "игра в восемь"
- •Упражнение
- •12.3. Применение поиска с предпочтением к планированию выполнения задач
- •Литература
- •Глава 13 Сведение задач к подзадачам. И/или-Графы
- •13.1. Представление задач в виде и/или-графов
- •13.2. Примеры и/или-представления задач
- •13.2.1. И/или-представление задачи поиска маршрута
- •13.2.2. Задача о ханойской башне
- •13.2.3. Формулировка игровых задач в терминах и/или-графов
- •13.3. Базовые процедуры поиска в и/или-графах
- •Упражнения
- •13.4. Поиск с предпочтением в и/или-графах
- •13.4.1. Эвристические оценки и алгоритм поиска
- •13.4.2. Программа поиска
- •13.4.3. Пример отношений, определяющих конкретную задачу: поиск маршрута
- •Упражнение
- •Литература
- •Глава 14 Экспертные системы
- •14.1. Функции, выполняемые экспертной системой
- •14.2. Грубая структура экспертной системы
- •14.3. Правила типа "если-то" для представления знаний
- •Упражнения
- •14.4. Разработка оболочки
- •14.4.1. Процесс рассуждений
- •14.4.2. Формирование ответа на вопрос "почему"
- •14.4.3. Формирование ответа на вопрос "как"
- •14.5. Реализация
- •14.5.1. Процедура рассмотреть
- •14.5.2. Процедура ответпольз
- •14.5.3. Усовершенствование процедуры ответпольз
- •14.5.4. Процедура выдать
- •14.5.5. Драйвер верхнего уровня
- •14.5.6. Одно замечание по поводу программы-оболочки
- •14.5.7. Цели с отрицанием
- •Упражнение
- •14.6. Работа с неопределенностью
- •14.6.1. Степень достоверности
- •14.6.2. Модель Prospector'а
- •14.6.3. Принципы реализации
- •14.7. Заключительные замечания
- •Проекты
- •Литература
- •Глава 15 Игры
- •15.1. Игры двух лиц с полной информацией
- •15.2. Минимаксный принцип
- •15.3. Альфа-бета алгоритм: эффективная реализация минимаксного принципа
- •15.4. Минимаксные игровые программы: усовершенствования и ограничения
- •15.5. Знания о типовых ситуациях и механизм "советов"
- •15.5.1. Цели и ограничения на ходы
- •15.5.2. Выполнимость совета
- •15.5.3. Правила и таблицы советов
- •15.6. Программа на языке al0 для игры в шахматном эндшпиле
- •15.6.1. Миниатюрный интерпретатор языка al0
- •15.6.2. Программа на языке советов для эндшпиля "король и ладья против короля"
- •Литература
- •Глава 16 Программирование в терминах типовых конфигураций
- •16.1. Архитектура, ориентированная на типовые конфигурации
- •16.1.1. Основные понятия
- •16.1.2. Прологовские программы как системы, управляемые образцами
- •16.1.3. Пример составления программы
- •16.2. Простой интерпретатор программ, управляемых образцами
- •16.3. Простая программа для автоматического доказательства теорем
- •16.4. Заключительные замечания
- •Литература
- •Ответы к некоторым упражнениям Глава 1
- •Глава 2
- •Глава 3
- •Глава 4
- •Глава 5
- •Глава 6
- •Глава 7
- •Глава 8
- •Глава 9
- •Глава 10
- •Глава 11
9.1. Представление списков. Сортировка
9.1.1. Замечания в некоторых альтернативных способах представления списков
В главе 3 была введена специальная система обозначений для списков (специальная прологовская нотация), которую мы и использовали в последующем изложении. Разумеется, это был всего лишь один из способов представления списков на Прологе. Список — это, в самом общем смысле, структура, которая либо
• пуста , либо
• состоит из головы и хвоста , причем хвост должен быть сам списком.
Поэтому для представления этой структуры нам необходимо иметь всего лишь два языковых средства: специальный символ, обозначающий пустой список, и функтор для соединения головы с хвостом. Мы могли бы, например, выбрать
ничего_не_делать
в качестве символа, обозначающего пустой список, и атом
затем
в качестве инфиксного оператора для построения списка по заданным голове и хвосту. Этот оператор мы можем объявить в программе, например, так:
:- op( 500, xfy, затем).
Список
[ войти, сесть, поужинать]
можно было бы тогда записать как
войти затем сесть затем поужинать
затем ничего_не_делать
Важно заметить, что на соответствующем уровне абстракции специальная прологовская нотация и всевозможные альтернативные способы обозначения списков сводятся, фактически, к одному и тому же представлению. В связи с этим типовые операции над списками, такие как
принадлежит ( X, L)
конк( L1, L2, L3)
удалить( X, L1, L2)
запрограммированные нами в специальной прологовской нотации, легко поддаются перепрограммированию в различные системы обозначений, выбранные пользователем. Например, отношение конк транслируется на язык "затем — ничего_не_делать" следующим образом. Определение, которое мы использовали до сих пор, имеет вид
конк( [], L, L).
конк( [X | L1], L2, [X | L3] ) :-
конк( L1, L2, L3).
В новой системе обозначений оно превращается в
конк( ничего_не_делать, L, L).
конк( X затем L1, L2, X затем L3) :-
конк(L1, L2, L3).
Этот пример показывает, как легко наши определения отношений над списками обобщаются на весь класс структур этого типа. Решение о том, какой именно способ записи списков будет использоваться в той или иной программе, следует принимать в соответствии с тем смыслом, который мы придаем списку в каждом конкретном случае. Если, например, список — это просто множество элементов, то наиболее удобна обычная прологовская нотация, поскольку в ней непосредственно выражается то, что программист имел в виду. С другой стороны, некоторые типы выражений также можно трактовать как своего рода списки. Например, для конъюнктов в исчислении высказываний подошло бы следующее спископодобное представление:
• истина соответствует пустому списку,
• & — оператор для соединения головы с хвостом, определяемый, например, как
:- op( 300, xfy, &)
Конъюнкция членов а, b, и с выглядела бы тогда как
а & b & с & истина
Все приведенные примеры базируются, по существу, на одной и той же структуре, представляющей список. Однако в гл. 8 мы рассмотрели существенно другой способ, влияющий на эффективность вычислений. Уловка состояла в том, что список представлялся в виде пары списков, являясь их "разностью". Было показано, что такое представление приводит к очень эффективной реализации отношения конкатенации.
Материал настоящего раздела проливает свет и на то различие, которое существует между применением операторов в математике и применением их в Прологе. В математике с каждым оператором всегда связано некоторое действие, в то время как в Прологе операторы используются просто для представления структур.
