Иван Братко - Программирование на языке Пролог для искусственного интеллекта

(2) X-Z через Y найти маршрут из X в Z, проходящий через Y

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

:- op( 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, P), СписокЗадач).

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

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

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

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

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

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.

Экспертная система - это программа, которая ведет себя подобно эксперту в некоторой проблемной области. Она должна иметь способность к объяснению своих решений и тех рассуждений, на основе которых эти решения были приняты. Часто от экспертной системы требуют, чтобы она могла работать с неточной и неполной информацией.