- •Иван Братко Программирование на языке Пролог для искусственного интеллекта
- •От редактора перевода
- •Предисловие
- •Предисловие автора
- •Благодарности
- •Упражнения
- •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
14.4.1. Процесс рассуждений
Наш интерпретатор будет принимать вопрос и искать на него ответ. Язык правил допускает, чтобы в условной части правила была И/ИЛИ-комбинация условий. Вопрос на входе интерпретатора может быть такой же комбинацией подвопросов. Поэтому процесс поиска ответов на эти вопросы будет аналогичен процессу поиска в И/ИЛИ-графах, который мы обсуждали в гл. 13.
Ответ на заданный вопрос можно найти несколькими способами в соответствии со следующими принципами:
Для того, чтобы найти ответ Отв на вопрос В , используйте одну из следующих возможностей:
• если В найден в базе знаний в виде факта, то Отв — это "В это правда"
• если в базе знаний существует правило вида
"если Условие то В ",
то для получения ответа Отв рассмотрите Условие
• если вопрос В можно задавать пользователю, спросите пользователя об истинности В
• если в имеет вид В1 и В2 , то рассмотрите В1 , а затем,
если В1 ложно, то положите Отв равным "В это ложь", в противном случае рассмотрите В2 и получите Отв как соответствующую комбинацию ответов на вопросы В1 и В2
• если В имеет вид В1 или В2 , то рассмотрите В1 , а затем,
если В1 истинно, то положите Отв равным "В1 это правда", в противном случае рассмотрите В2 и получите Oтв как соответствующую комбинацию ответов на вопросы В1 и В2 .
Вопросы вида
не В
обрабатываются не так просто, и мы обсудим их позже.
14.4.2. Формирование ответа на вопрос "почему"
Вопрос "почему " возникает в ситуации, когда система просит пользователя сообщить ей некоторую информацию, а пользователь желает знать, почему эта информация необходима. Допустим, что система спрашивает:
а — это правда?
В ответ пользователь может спросить:
почему?
Объяснение в этом случае выглядит примерно так:
Потому, что
Я могу использовать а ,
чтобы проверить по правилу Па , что b , и
Я могу использовать b ,
чтобы проверить по правилу Пb , что с , и
Я могу использовать с ,
чтобы проверить по правилу Пc , что d , и
…
Я могу использовать y ,
чтобы проверить по правилу Пy , что z , и
z — это ваш исходный вопрос.
Объяснение — это демонстрация того, как система намерена использовать информацию, которую она хочет получить от пользователя. Намерения системы демонстрируются в виде цепочки правил и целей, соединяющей эту информацию с исходным вопросом.
Рис. 14.8. Объяснение типа "почему". На вопрос "Почему вас интересует текущая цель?" дается объяснение в виде цепочки правил и целей, соединяющей текущую цель с исходным вопросом пользователя, находящимся в верхушке дерева. Эта цепочка называется трассой.
Будем называть такую цепочку трассой . Трассу можно себе представлять как цепочку правил, соединяющую в И/ИЛИ-дереве вопросов текущую цель с целью самого верхнего уровня так, как это показано на рис. 14.8. Таким образом, для формирования ответа на вопрос "почему" нужно двигаться в пространстве поиска от текущей цели вверх вплоть до самой верхней цели. Для того, чтобы суметь это сделать, нам придется в процессе рассуждений сохранять трассу в явном виде.
14.4.3. Формирование ответа на вопрос "как"
Получив ответ на свой вопрос, пользователь возможно захочет увидеть, как система пришла к такому заключению. Один из подходящих способов ответить на вопрос "как" — это представить доказательство, т.е. те правила и подцели, которые использовались для достижения полученного заключения. Это доказательство в случае нашего языка записи правил имеет вид решающего И/ИЛИ-дерева. Поэтому наша машина логического вывода будет не просто отвечать на вопрос, соответствующий цели самого верхнего уровня — этого нам недостаточно, а будет выдавать в качестве ответа решающее И/ИЛИ-дерево, составленное из имен правил и подцелей. Затем это дерево можно будет отобразить на выходе системы в качестве объяснения типа "как". Объяснению можно придать удобную для восприятия форму, если каждое поддерево печатать с надлежащим отступом, например:
питер это хищник
было выведено по прав3 из
питер это млекопитающее
было выведено по прав1 из
питер имеет шерсть
было сказано
и
питер ест мясо
было сказано
