Читаем Prolog полностью

Здесь 'через' - это инфиксный оператор более высокого приоритета, чем '-', и более низкого, чем '--->'. Теперь можно определить соответствующий И / ИЛИ-граф явным образом при помощи следующего фрагмента программы:

        :- ор( 560, xfx, через)

        % Правила задачи X-Z, когда между  X  и  Z

        % имеются ключевые пункты,

        % стоимости всех дуг равны 0

        X-Z ---> или : СписокЗадач

        :- bagof( ( X-Z через Y)/0, клпункт( X-Z, Y),

                        СписокЗадач),   !.

        % Правила для задачи X-Z без ключевых пунктов

        X-Z ---> или : СписокЗадач

        :- bagof( ( Y-Z)/P, связь( X, Y, Р), СписокЗадач).

        % Сведение задачи типа ''через" к подзадачам,

           % связанным отношением И

        X-Z через Y---> и : [( X-Y)/0, ( Y-Z)/0].

        цель( Х-Х)         % Тривиальная задача: попасть из X в X

Функцию  h  можно определить, например, как расстояние, которое нужно преодолеть при воздушном сообщении между городами.

Упражнение

13. 4.    Напишите процедуру

        отобр2( РешДер)

для отображения решающего дерева, найденного программой и_или рис. 13.12. Формат отображения пусть будет аналогичен тому, что применялся в процедуре отобр (рис. 13.8), так что процедуру отобр2 можно получить, внеся в отобр изменения, связанные с другим представлением деревьев. Другая полезная модификация - заменить в отобр цель write( Верш) на процедуру, определяемую пользователем

        печверш( Верш, 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.

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

Глава 14

ЭКСПЕРТНЫЕ СИСТЕМЫ