- •Иван Братко Программирование на языке Пролог для искусственного интеллекта
- •От редактора перевода
- •Предисловие
- •Предисловие автора
- •Благодарности
- •Упражнения
- •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.7. Заключительные замечания
Нашу оболочку экспертной системы можно развивать в целом ряде направлений. В данный момент уместно сделать несколько критических замечаний и высказать предложения по усовершенствованию нашей программы.
В нашей программе, являющейся упрощенной реализацией, не уделено достаточного внимания вопросам эффективности. В более эффективной реализации потребовалось бы использовать более сложные структуры данных, ввести индексирование или иерархическую структуризацию множества правил и т.п.
Наша процедура рассмотреть подвержена зацикливанию в тех случаях, когда в правилах базы знаний "циклически" упоминается одна и та же цель. Этот недостаток легко исправить, предусмотрев в рассмотреть соответствующий контроль, т.е. проверку, не является ли текущая цель частным случаем некоторой цели, уже введенной в состав объекта Трасса.
Наше объяснение типа "как" выводит дерево доказательства целиком. В случае больших деревьев, удобнее было бы вывести только верхнюю часть дерева, а затем дать пользователю возможность "гулять" по остальной части дерева по своему желанию. Тогда пользователь смог бы просматривать дерево выборочным образом, используя команды, такие как "Вниз по ветви 1", "Вниз по ветви 2", …, "Вверх", "Достаточно".
В объяснениях типа "как" и "почему" наша оболочка ссылается на правила, указывая их имена, и не показывает их в явном виде. Необходимо, чтобы во время консультационного сеанса пользователь мог, по желанию, запрашивать те или иные правила и получать их явные изображения.
Известно, что придать диалогу с пользователем естественный характер при помощи умелой постановки вопросов - сложная задача. Наш способ ее решения работает только в определенных пределах и во многих случаях приводит к самым разным проблемам, например:
Это правда: сьюзен летает?
нет.
Это правда: сьюзен летает хорошо?
Конечно же нет, раз она совсем не летает! Другой пример:
Есть (еще) решения для: Кто-нибудь летает?
да.
Кто-нибудь = птица .
Это правда: альбатрос летает?
Для того, чтобы справиться с подобными нежелательными эффектами, следует ввести в экспертную систему дополнительные отношения между понятиями вместе с механизмами их обработки. Обычно эти новые отношения задают иерархию объектов и их свойств.
Возможно еще одно усовершенствование процедуры взаимодействия с пользователем, предусматривающее планирование оптимальной стратегии постановки вопросов. Целью оптимизации является минимизация количества вопросов, которые необходимо задать пользователю для достижения некоторого окончательного логического заключения. Разумеется, возникнут различные варианты таких стратегий, и то, какая из них окажется оптимальной, будет зависеть от ответов пользователя. Принятие решения о выборе той или иной альтернативной стратегии можно основывать на априорных вероятностях, являющихся вероятностными оценками "стоимостей" альтернатив. Величины оценок, возможно, придется пересчитывать после каждого ответа пользователя.
Существует еще одна величина, поддающаяся оптимизации: длина цепочки вывода. Такая оптимизация позволила бы давать более простые объяснения типа "как". Сложность объяснений можно также уменьшить за счет селективного подхода к правилам. Некоторые из правил можно было бы не включать в состав объектов Трасса и Ответ, порождаемых процедурой рассмотреть. С этой целью необходимо указывать в базе знаний, какие из правил "трассируемы", а следовательно, должны появляться в объяснениях, а какие можно опускать.
В "разумной" экспертной системе следует предусмотреть вероятностные механизмы, заставляющие ее концентрировать свое внимание на наиболее правдоподобных гипотезах среди всех конкурирующих между собой гипотез. Такая экспертная система должна запрашивать у пользователя ту информацию, которая позволила бы распознать наилучшую среди наиболее правдоподобных гипотез.
Наша экспертная система была классификационного или "анализирующего" типа, в противоположность системам "синтезирующего" типа, в которых ставится задача построить что-либо. В последнем случае результат работы - это план действий, предпринимаемых для выполнения этой задачи, например план действий робота, компьютерная конфигурация, удовлетворяющая заданным требованиям, или форсированная комбинация в шахматах. Наш пример, относящийся к локализации неисправностей, можно естественным образом расширить, чтобы включить в рассмотрение действия. Например, если система не может прийти к определенному выводу, поскольку приборы выключены, она даст рекомендацию: "Включить лампу 3". Здесь сразу возникнет задача построения оптимального плана: минимизировать число действий, необходимых для достижения окончательного вывода.
