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

причем сделаем это таким образом, чтобы наша формулировка могла бы быть непосредственно использована процедурой и_или рис. 13.12. Мы условимся, что карта дорог будет представлена при помощи отношения

связь( Гор1, Гор2, P)

означающего, что между городами Гор1 и Гор2 существует непосредственная связь, а соответствующее расстояние равно P. Далее, мы допустим, что существует отношение

клпункт( Гор1-Гор2, Гор3)

имеющее следующий смысл: для того, чтобы найти маршрут из Гор1 в Гор2, следует рассмотреть пути, проходящие через Гор3 (Гор3 — это 'ключевой пункт' между Гор1 и Гор2). Например, на карте рис. 13.1 f и g — это ключевые пункты между а и z:

клпункт( a-z, f).  клпункт( a-z, g).

Мы реализуем следующий принцип построения маршрута:

 Для того, чтобы найти маршрут между городами X и Z, необходимо:

  (1) если между X и Z имеются ключевые пункты Y1, Y2, …, то найти один из путей:

   путь из X в Z через Y1, или

   путь из X в Z через Y2, или

   …

  (2) если между X и Z нет ключевых пунктов, то найти такой соседний с X город Y, что существует маршрут из Y в Z.

Таким образом, мы имеем два вида задач, которые мы будем представлять как

(1) X-Z         найти маршрут из X в Z

(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). Наша программа поиска с предпочтением — это один из вариантов алгоритма, известного под названием АО*. Формальные свойства АО*-алгоритма (включая его допустимость) изучались несколькими авторами. Подробный обзор