![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
13.4. Напишите процедуру
отобр2(РешДер)
для отображения решающего дерева, найденного программой и_или рис. 13.12. Формат отображения пусть будет аналогичен тому, что применялся в процедуре отобр (рис. 13.8), так что процедуру отобр2 можно получить, внеся в отобр изменения, связанные с другим представлением деревьев. Другая полезная модификация — заменить в отобр цель write(Верш) на процедуру, определяемую пользователем
печверш(Верш, H)
которая выведет Верш в удобной для пользователя форме, а также конкретизирует H в соответствии с количеством символов, необходимом для представления Верш в этой форме. В дальнейшем H будет использоваться как величина отступа для поддеревьев.
Резюме
• И/ИЛИ-граф — это формальный аппарат для представления задач. Такое представление является наиболее естественным и удобным для задач, которые разбиваются на независимые подзадачи. Примером могут служить игры.
• Вершины И/ИЛИ-графа бывают двух типов: И-вершины и ИЛИ-вершины.
• Конкретная задача определяется стартовой вершиной и целевым условием. Решение задачи представляется решающим деревом.
• Для моделирования оптимизационных задач в И/ИЛИ-граф можно ввести стоимости дуг и вершин.
• Процесс решения задачи, представленной И/ИЛИ-графом, включает в себя поиск в графе. Стратегия поиска в глубину предусматривает систематический просмотр графа и легко программируется. Однако эта стратегия может привести к неэффективности из-за комбинаторного взрыва.
• Для оценки трудности задач можно применить эвристики, а для управления поиском — принцип эвристического поиска с предпочтением. Эта стратегия более трудна в реализации.
• В данной главе были разработаны прологовские программы для поиска в глубину и поиска с предпочтением в И/ИЛИ-графах.
• Были введены следующие понятия:
И/ИЛИ-графы
И-дуги, ИЛИ-дуги
И-вершины, ИЛИ-вершины
решающий путь, решающее дерево
стоимость дуг и вершин
эвристические оценки в И/ИЛИ-графах
"возвращенные" оценки
поиск в глубину в И/ИЛИ-графах
поиск с предпочтением в И/ИЛИ-графах
Литература
И/ИЛИ-графы и связанные с ними алгоритмы поиска являются частью классических механизмов искусственного интеллекта для решения задач и реализации машинных игр. Ранним примером прикладной задачи, использующей эти методы, может служить программа символического интегрирования (Slagle 1963). И/ИЛИ-поиск используется в самой пролог-системе. Общее описание И/ИЛИ-графов и алгоритма можно найти в учебниках по искусственному интеллекту (Nilsson 1971; Nilsson 1980). Наша программа поиска с предпочтением — это один из вариантов алгоритма, известного под названием АО*. Формальные свойства АО*-алгоритма (включая его допустимость) изучались несколькими авторами. Подробный обзор полученных результатов можно найти в книге Pearl (1984).
Nilsson N.J. (1971). Problem-Solving Methods in Artificial Intelligence. McGraw-Hill.
Nilsson N.J. (1980). Principles of Artificial Intelligence. Tioga; also Springer-Verlag.
Pearl J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.
Slagle J.R. (1963). A heuristic program that solves symbolic integration problems in freshman calculus. In: Computers and Thought (E. Feigenbaum, J. Feldman, eds.). McGraw-Hill.
Дата публикования: 2015-10-09; Прочитано: 176 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!