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

Один из фундаментальных вопросов программирования — это вопрос о представлении сложных объектов (таких как, например, множества), а также вопрос об эффективной реализации операций над подобными объектами. В этой главе мы рассмотрим несколько часто используемых структур данных, принадлежащих к трем большим семействам: спискам, деревьям и графам. Мы изучим способы представления этих структур на Прологе и составим программы, реализующие некоторые операции над ними, в том числе, сортировку списков, работу с множествами как древовидными структурами, запись элементов данных в дерево, поиск данных в дереве, нахождение пути в графе и т.п. Мы подробно разберем несколько примеров, чрезвычайно поучительных с точки зрения программирования на Прологе.

9.1. Представление списков. Сортировка

ничего_не_делать

затем

:- op( 500, xfy, затем).

[ войти, сесть, поужинать]

войти затем сесть затем поужинать

 затем ничего_не_делать

принадлежит ( X, L)

конк( L1, L2, L3)

удалить( X, L1, L2)

конк

конк( [], L, L).

конк( [X | L1], L2, [X | L3] ) :-

 конк( L1, L2, L3).

конк( ничего_не_делать, L, L).

конк( X затем L1, L2, X затем L3) :-

 конк(L1, L2, L3).

истина

&

:- op( 300, xfy, &)

а & b & с & истина

список( Объект)

Объект

преобр( СтандСпис, Спис)

преобр( [а, b], а затем b затем ничего_не_делать)

преобр

преобр

преобр( СтандСпис, Спис, Функтор, ПустСпис)

?- пpeoбp( [а, b], L, затем, ничего_не_делать).

L = а затем b затем ничего_не_делать

?-  преобр( [а, b, с], L, +, 0).

L = а+(b+(с+0) )

9.1.2. Сортировка списков

Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядка

больше( X, Y)

означающее, что X больше, чем Y, независимо от того, что мы в действительности понимаем под "больше, чем". Если элементами списка являются числа, то отношение

больше

будет, вероятно, определено как

больше( X, Y) :- X > Y.

Если же элементы списка — атомы, то отношение

больше

может соответствовать алфавитному порядку между ними.

Пусть

сорт( Спис, УпорСпис)

обозначает отношение, в котором

Спис

— некоторый список, а

УпорСпис

— это список, составленный из тех же элементов, но упорядоченный по возрастанию в соответствия с отношением

больше

. Мы построим три определения этого отношения на Прологе, основанные на трех различных идеях о механизме сортировки. Вот первая идея:

Для того, чтобы упорядочить список

Спис

, необходимо:

• Найти в

Спис

два смежных элемента X и Y, таких, что

больше( X, Y)

, и поменять X и Y местами, получив тем самым новый список

Спис1

; затем отсортировать

Спис1

.

• Если в

Спис

нет ни одной пары смежных элементов X и Y, таких, что

больше( X, Y)

, то считать, что

Спис

уже отсортирован.

Мы переставили местами 2 элемента X и Y, расположенные в списке "не в том порядке", с целью приблизить список к своему упорядоченному состоянию. Имеется в виду, что после достаточно большого числа перестановок все элементы списка будут расположены в правильном порядке. Описанный принцип сортировки принято называть методом пузырька, поэтому соответствующая прологовская процедура будет называться

пузырек

.

пузырек( Спис, УпорСпис) :-

 перест( Спис, Спис1), !, % Полезная перестановка?

 пузырек( Спис1, УпорСпис).

пузырек( УпорСпис, УпорСпис).

 % Если нет, то список уже упорядочен

перест( [X, Y | Остаток], [Y, X ) Остаток] ):-

 % Перестановка первых двух элементов

 больше( X, Y).

перест( [Z | Остаток], [Z | Остаток1] ):-

 перест( Остаток, Остаток1). % Перестановка в хвосте

Еще один простой алгоритм сортировки называется сортировкой со вставками. Он основан на следующей идее:

Для того, чтобы упорядочить непустой список

L = [X | Хв]

, необходимо:

(1) Упорядочить хвост

Хв

списка

L

.

(2) Вставить голову

X

списка

L

в упорядоченный хвост, поместив ее в такое место, чтобы получившийся список остался упорядоченным. Список отсортирован.

Этот алгоритм транслируется в следующую процедуру

вставсорт

на Прологе:

вставсорт([], []).

вставсорт( [X | Хв], УпорСпис) :-

 вставсорт( Хв, УпорХв), % Сортировка хвоста

встав( X, УпорХв, УпорСпис).

 % Вставить X на нужное место

встав( X, [Y | УпорСпис], [Y | УпорСпис1]):-

 больше( X, Y), !,

 встав( X, УпорСпис, УпорСпис1).

встав( X, УпорСпис, [X | УпорСпис] ).

Рис. 9.1. Сортировка списка процедурой

быстрсорт

.

Процедуры сортировки

пузырек

и

вставсорт

просты, но не эффективны. Из этих двух процедур процедура со вставками более эффективна, однако среднее время, необходимое для сортировки списка длиной n процедурой

вставсорт

, возрастает с ростом n пропорционально n². Поэтому для длинных списков значительно лучше работает алгоритм быстрой сортировки, основанный на следующей идее (рис. 9.1):

Для того, чтобы упорядочить непустой список

L

, необходимо:

(1) Удалить из списка

L

какой-нибудь элемент

X

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

Меньш

и

Больш

, следующим образом: все элементы большие, чем

X

, принадлежат списку

Больш

, остальные — списку

Меньш

.

(2) Отсортировать список

Меньш

, результат — список

УпорМеньш

.

(3) Отсортировать список

Больш

, результат — список

УпорБольш

.

(4) Получить результирующий упорядоченный список как конкатенацию списков

УпорМеньш

и

[ X | УпорБольш]

.

Заметим, что если исходный список пуст, то результатом сортировки также будет пустой список. Реализация быстрой сортировки на Прологе показана на рис. 9.2. Здесь в качестве элемента X, удаляемого из списка, всегда выбирается просто голова этого списка. Разбиение на два списка запрограммировано как отношение с четырьмя аргументами:

разбиение( X, L, Больш, Меньш).

Временная сложность нашего алгоритма зависит от того, насколько нам повезет при разбиении сортируемого списка. Если списки всегда разбиваются на два списка примерно равной длины, то процедура сортировки имеет временную сложность порядка n log n, где n — длина исходного списка. Если же, наоборот, разбиение всегда приводит к тому, что один из списков оказывается значительно больше другого, то сложность будет порядка n². Анализ показывает, что, к счастью, средняя производительность быстрой сортировки ближе к лучшему случаю, чем к худшему.

Программу, показанную на рис. 9.2, можно усовершенствовать, если реализовать операцию конкатенации более эффективно. Напомним, что конкатенация становится тривиальной операцией после применения разностного представления списков, введенного в гл. 8. Для того, чтобы использовать эту идею в нашей процедуре сортировки, нужно представить встречающиеся в ней списки в форме пар вида

A-Z

следующим образом:

 УпорМеньш

имеет вид

A1-Z1

 УпорБольш

имеет вид

A2-Z2

быстрсорт( [], [] ).

быстрсорт( [X | Хвост], УпорСпис) :-

 разбиение( X, Хвост, Меньш, Больш),

 быстрсорт( Меньш, УпорМеньш),

 быстрсорт( Больш, УпорБольш),

 конк( УпорМеньш, [X | УпорБольш], УпорСпис).

разбиение( X, [], [], [] ).

разбиение( X, [Y | Хвост], [Y | Меньш], Больш ) :-

 больше( X, Y), !,

 разбиение( X, Хвост, Меньш, Больш).

разбиение( X, [Y | Хвост], Меньш, [Y | Больш] ) :-

 разбиение( X, Хвост, Меньш, Больш).

конк( [], L, L).

конк( [X | L1], L2, [X | L3] ) :-

 конк( L1, L2, L3 ).

Рис. 9.2. Быстрая сортировка.

Тогда конкатенации списков

УпорМеньш

и

[ X | УпорБольш]

будет соответствовать конкатенация пар

A1-Z1

и

[ X | A2]-Z2

В результате мы получим

А1-Z2

, причем

Z1 = [ X | А2]

Пустой список представляется парой Z-Z. Систематически вводя изменения в программу рис. 9.2, мы получим более эффективный способ реализации процедуры

быстрсорт

, показанный на рис. 9.3 под именем

быстрсорт2

. Здесь, как и раньше, процедура

быстрсорт

использует обычное представление списков, но в действительности сортировку выполняет более эффективная процедура

быстрсорт2

, использующая разностное представление. Эти две процедуры связаны между собой, соотношением

быстрсорт( L, S) :-

 быстрсорт2( L, S-[] ).

быстрсорт( Спис, УпорСпис) :-

 быстрсорт2( Спис, УпорСпис-[] ).

быстрсорт2( [], Z-Z).

быстрсорт2( [X | Хвост], A1-Z2) :-

 разбиение( X, Хвост, Меньш, Больш),

 быстрсорт2( Меньш, А1-[X | A2] ),

 быстрсорт2( Больш, A2-Z2).

Рис. 9.3. Более эффективная реализация процедуры

быстрсорт

с использованием разностного представления списков. Отношение

разбиение( X, Спис, Меньш, Больш)

определено, как на рис. 9.2.

Упражнения

9.5. Напишите процедуру слияния двух упорядоченных списков в один третий список. Например:

?- слить( [2, 5, 6, 6, 8], [1, 3, 5, 9], L).

L = [1, 2, 3, 5, 5, 6, 6, 8, 9]

9.6. Программы сортировки, показанные на рис. 9.2 и 9.3, отличаются друг от друга способом представления списков. Первая из них использует обычное представление, в то время как вторая — разностное представление. Преобразование из одного представления в другое очевидно и может быть автоматизировано. Введите в программу рис. 9.2 необходимые изменения, чтобы преобразовать ее в программу рис. 9.3.

9.7. Наша программа

быстрсорт

в случае, когда исходный список уже упорядочен или почти упорядочен, работает очень неэффективно. Проанализируйте причины этого явления.

9.8. Существует еще одна хорошая идея относительно механизма сортировки списков, позволяющая избавиться от недостатков программы

быстрсорт

, а именно: разбить список на два меньших списка, отсортировать их, а затем слить вместе. Итак, для того, чтобы отсортировать список L, необходимо

• разбить L на два списка L1 и L2 примерно одинаковой длины;

• произвести сортировку списков L1 и L2,получив списки S1 и S2;

• слить списки S1 и S2, завершив на этом сортировку списка L.

Реализуйте этот принцип сортировки и сравните его эффективность с эффективностью программы

быстрсорт

.

9.2. Представление множеств двоичными деревьями

Списки часто применяют для представления множеств. Такое использование списков имеет тот недостаток, что проверка принадлежности элемента множеству оказывается довольно неэффективной. Обычно предикат

принадлежит( X, L)

принадлежит X, [X | L] ).

принадлежит X, [ Y | L] ) :-

 принадлежит( X, L).

Для того, чтобы найти X в списке L, эта процедура последовательно просматривает список элемент за элементом, пока ей не встретится либо элемент X, либо конец списка. Для длинных списков такой способ крайне неэффективен.

Для облегчения более эффективной реализация отношения принадлежности применяют различные древовидные структуры. В настоящем разделе мы рассмотрим двоичные деревья.

Двоичное дерево либо пусто, либо состоит из следующих трех частей:

• корень

• левое поддерево

правое поддерево

Корень может быть чем угодно, а поддеревья должны сами быть двоичными деревьями. На рис. 9.4 показано представление множества [а, b, с, d] двоичным деревом. Элементы множества хранятся в виде вершин дерева. Пустые поддеревья на рис. 9.4 не показаны. Например, вершина b имеет два поддерева, которые оба пусты.

Существует много способов представления двоичных деревьев на Прологе. Одна из простых возможностей — сделать корень главным функтором соответствующего терма, а поддеревья — его аргументами. Тогда дерево рис. 9.4 примет вид

а( b, с( d) )

Такое представление имеет среди прочих своих недостатков то слабое место, что для каждой вершины дерева нужен свой функтор. Это может привести к неприятностям, если вершины сами являются структурными объектами.

Рис. 9.4. Двоичное дерево.

Существует более эффективный и более привычный способ представления двоичных деревьев: нам нужен специальный символ для обозначения пустого дерева и функтор для построения непустого дерева из трех компонент (корня и двух поддеревьев). Относительно функтора и специального символа сделаем следующий выбор:

• Пусть атом

nil

• В качестве функтора примем

дер

X

L

R

дер( L, X, R)

В этом представлении дерево рис. 9.4 выглядит как

дер( дер( nil, b, nil), a,

 дер( дер( nil, d, nil), с, nil) ).

Теперь рассмотрим отношение принадлежности, которое будем обозначать

внутри

внутри( X, T)

истинна, если

X

T

внутри

Рис. 9.5. Представление двоичных деревьев.

Эти правила непосредственно транслируются на Пролог следующим образом:

внутри( X, дер( _, X, _) ).

внутри( X, дер( L, _, _) ) :-

 внутри( X, L).

внутри( X, дер( _, _, R) ) :-

 внутри( X, R).

Очевидно, что цель

внутри( X, nil)

терпит неудачу при любом X.

Посмотрим, как ведет себя наша процедура. Рассмотрим рис. 9.4. Цель

внутри( X, T)

используя механизм возвратов, находит все элементы данных, содержащиеся в множестве, причем обнаруживает их в следующем порядке:

X = а; X = b; X = с; X = d

Теперь рассмотрим вопрос об эффективности. Цель

внутри( а, T)

достигается сразу же после применения первого предложения процедуры

внутри

внутри( d, T)

будет успешно достигнута только после нескольких рекурсивных обращений. Аналогично цель

внутри( e, T)

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

внутри

В этом последнем случае мы видим такую же неэффективность, как если бы мы представили множество просто списком. Положение можно улучшить, если между элементами множества существует отношение порядка. Тогда можно упорядочить данные в дереве слева направо в соответствии с этим отношением.

Рис. 9.6. Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5→8→6.

Будем говорить, что непустое дерево

дер( Лев, X, Прав)

(1) все вершины левого поддерева

Лев

(2) все вершины правого поддерева

Прав

(3) оба поддерева упорядочены.

Будем называть такое двоичное дерево двоичным справочником. Пример показан на рис. 9.6.

Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в двоичном справочнике всегда достаточно просмотреть не более одного поддерева. Экономия при поиске объекта X достигается за счет того, что, сравнив X с корнем, мы можем сразу же отбросить одно из поддеревьев. Например, пусть мы ищем элемент 6 в дереве, изображенной на рис. 9.6. Мы начинаем с корня 5, сравниваем 6 с 5, получаем 6 > 5. Поскольку все элементы данных в левом поддереве должны быть меньше, чем 5, единственная область, в которой еще осталась возможность найти элемент 6, — это правое поддерево. Продолжаем поиск в правом поддереве, переходя к вершине 8, и т.д.

Общий метод поиска в двоичном справочнике состоит в следующем:

Эти правила запрограммированы в виде процедуры, показанной на рис. 9.7. Отношение

больше( X, Y)

Существует способ использовать процедуру

внутри

?- внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).

Д = дер( дер( Д1, 3, Д2), 5, дер( Д3, 8, Д4) ).

Переменные Д1, Д2, Д3 и Д4 соответствуют четырем неопределенным поддеревьям. Какими бы они ни были, все равно дерево Д будет содержать заданные элементы 3, 5 и 8. Структура построенного дерева зависит от того порядка, в котором указываются цели (рис. 9.8).

внутри( X, дер( _, X, _ ).

внутри( X, дер( Лев, Корень, Прав) ) :-

 больше( Корень, X), % Корень больше, чем X

внутри( X, Лев).   % Поиск в левом поддереве

внутри( X, дер( Лев, Корень, Прав) ) :-

 больше( X, Корень), % X больше, чем корень

 внутри( X, Прав).  % Поиск в правом поддереве

Рис. 9.7. Поиск элемента X в двоичном справочнике.

Рис. 9.8. (а) Дерево

Д

внутри( 5, Д)

внутри( 3, Д)

внутри( 8, Д)

внутри( 5, Д)

внутри( 3, Д)

внутри( 8, Д)

Здесь уместно сделать несколько замечаний относительно эффективности поиска в справочниках. Вообще говоря, поиск элемента в справочнике эффективнее, чем поиск в списке. Но насколько? Пусть n — число элементов множества. Если множество представлено списком, то ожидаемое время поиска будет пропорционально его длине n. В среднем нам придется просмотреть примерно половину списка. Если множество представлено двоичным деревом, то время поиска будет пропорционально глубине дерева. Глубина дерева — это длина самого длинного пути между корнем и листом дерева. Однако следует помнить, что глубина дерева зависит от его формы.

Мы говорим, что дерево (приближенно) сбалансировано, если для каждой вершины дерева соответствующие два поддерева содержат примерно равное число элементов. Если дерево хорошо сбалансировано, то его глубина пропорциональна log n. В этом случае мы говорим, что дерево имеет логарифмическую сложность. Сбалансированный справочник лучше списка настолько же, насколько log n меньше n. К сожалению, это верно только для приближенно сбалансированного дерева. Если происходит разбалансировка дерева, то производительность падает. В случае полностью разбалансированных деревьев, дерево фактически превращается в список. Глубина дерева в этом случае равна n, а производительность поиска оказывается столь же низкой, как и в случае списка. В связи с этим мы всегда заинтересованы в том, чтобы справочники были сбалансированы. Методы достижения этой цели мы обсудим в гл. 10.

9.9. Определите предикаты

двдерево( Объект)

справочник( Объект)

распознающие, является ли

Объект

9.10. Определите процедуру

глубина( ДвДерево, Глубина)

вычисляющую глубину двоичного дерева в предположении, что глубина пустого дерева равна 0, а глубина одноэлементного дерева равна 1.

9.11. Определите отношение

линеаризация( Дерево, Список)

соответствующее "выстраиванию" всех вершин дерева в список.

9.12. Определите отношение

максэлемент( Д, Элемент)

таким образом, чтобы переменная

Элемент

Д

9.13. Внесите изменения в процедуру

внутри( Элемент, ДвСправочник)

добавив в нее третий аргумент

Путь

9.3. Двоичные справочники: добавление и удаление элемента

Если мы имеем дело с динамически изменяемым множеством элементов данных, то нам может понадобиться внести в него новый элемент или удалить из него один из старых. В связи с этим набор основных операций, выполняемых над множеством S, таков:

внутри( X, S)    % X  содержится в  S

добавить( S, X, S1) % Добавить  X  к  S,  результат -  S1

удалить( S, X, S1) % Удалить  X  из  S,  результат -  S1

Рис. 9.9. Введение в двоичный справочник нового элемента на уровне листьев. Показанные деревья соответствуют следующей последовательности вставок:

добавить( Д1, 6, Д2)

добавить( Д2, 6, Д3)

добавить( Д3, 6, Д4)

доблист( nil, X, дер( nil, X, nil) ).

доблист( дер( Лев, X, Прав), X, дер( Лев, X, Прав) ). 

доблист( дер( Лев, Кор, Прав), X, дер( Лев1, Кор, Прав)) :- 

 больше( Кор, X), 

доблист( Лев, X, Лев1)). 

доблист( дер( Лев, Кор, Прав), X, дер( Лев, Кор, Прав1)) :- 

 больше( X, Кор), 

 доблист( Прав, X, Прав1). 

Рис. 9.10. Вставление в двоичный справочник нового элемента в качестве листа.

Определим отношение добавить. Простейший способ: ввести новый элемент на самый нижний уровень дерева, так что он станет его листом. Место, на которое помещается новый элемент, выбрать таким образом, чтобы не нарушить упорядоченность дерева. На рис. 9.9 показано, какие изменения претерпевает дерево в процессе введения в него новых элементов. Назовем такой метод вставления элемента в множество

доблист( Д, X, Д1)

Правила добавления элемента на уровне листьев таковы:

• Результат добавления элемента X к пустому дереву есть дерево

дер( nil, X, nil)

• Если X совпадает с корнем дерева Д, то Д1 = Д (в множестве не допускается дублирования элементов).

• Если корень дерева Д больше, чем X, то X вносится в левое поддерево дерева Д; если корень меньше, чем X, то X вносится в правое поддерево.

На рис. 9.10 показана соответствующая программа.

Теперь рассмотрим операцию удалить. Лист дерева удалить легко, однако удалить какую-либо внутреннюю вершину — дело не простое. Удаление листа можно на самом деле определить как операцию, обратную операции добавления листа:

удлист( Д1, X, Д2) :-

 доблист( Д2, X, Д1).

Рис. 9.11. Удаление X из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента X.

К сожалению, если X — это внутренняя вершина, то такой способ не работает, поскольку возникает проблема, иллюстрацией к которой служит рис. 9.11. Вершина X имеет два поддерева

Лев

Прав

Лев

Прав

Если одно из поддеревьев Лев и Прав пусто, то существует простое решение: подсоединить к А непустое поддерево. Если же оба поддерева непусты, то можно использовать следующую идею (рис. 9.12): если самую левую вершину Y поддерева

Прав

Лев

Рис. 9. 2. Заполнение пустого места после удаления X.

На рис. 9.13 показана программа, реализующая операцию удаления элементов в соответствии с изложенными выше соображениями. Основную работу по перемещению самой левой вершины выполняет отношение

удмин( Дер, Y, Дер1)

Здесь Y — минимальная (т.е. самая левая) вершина дерева

Дер

Дер1

Дер

Существует другой, элегантный способ реализация операции добавить и удалить. Отношение добавить можно сделать недетерминированным в том смысле, что новый элемент вводится на произвольный уровень дерева, а не только на уровень листьев. Правила таковы:

уд( дер( nil, X, Прав), X, Прав).

уд( дер( Лев, X, nil), X, Лев).

уд( дер( Лев, X, Прав), X, дер( Лев,Y, Прав1) ) :-

 удмин( Прав, Y, Прав1).

уд( дер( Лев, Кор, Прав), X, дер( Лев1, Кор, Прав) ) :-

 больше( Кор, X),

 уд( Лев, X, Лев1).

уд( дер( Лев, Кор, Прав), X, дер( Лев, Кор, Прав1) ) :-

 больше( X, Кор),

 уд( Прав, X, Прав1).

удмин( дер( nil, Y, Прав), Y, Прав).

удмин( дер( Лев, Кор, Прав), Y, дер( Лев1, Кор, Прав) ) :-

 удмин( Лев, Y, Лев1).

Рис. 9.13. Удаление элемента из двоичного справочника.

Трудным моментом здесь является введение X на место корня. Сформулируем эту операций в виде отношения

добкор( Д, X, X1)

где X — новый элемент, вставляемый вместо корня в Д, а Д1 — новый справочник с корнем X. На рис. 9.14 показано, как соотносятся X, Д и Д1. Остается вопрос: что из себя представляют поддеревья L1 и L2 (или, соответственно, R1 и R2) на рис. 9.14?

Рис. 9.14. Внесение X в двоичный справочник в качестве корня.

Ответ мы получим, если учтем следующие ограничения на L1, L2:

• L1 и L2 — двоичные справочники;

• множество всех вершин, содержащихся как в L1, так и в L2, совпадает с множеством вершин справочника L;

• все вершины из L1 меньше, чем X; все вершены из L2 больше, чем X.

Отношение, которое способно наложить все эти ограничения на L1, L2, — это как раз и есть наше отношение

добкор

добкор( L, X, дер( L1, X, L2) ).

Те же самые ограничения применимы к R1, R2:

добкор( R, X, дер( R1, X, R2) ).

На рис. 9.15 показана программа для "недетерминированного" добавления элемента в двоичный справочник.

добавить( Д, X, Д1) :-        % Добавить X на место корня

 добкор( Д, X, Д1).

добавить( дер( L, Y, R), X, дер( L1, Y, R) ) :-

 больше( Y, X),           % Ввести X в левое поддерево

 добавить( L, X, L1).

добавить( дер( L, Y, R), X, дер( L, Y, R1) ) :-

 больше( X, Y),           % Ввести X в правое поддерево

 добавить( R, X, R1).

добкор( nil, X, дер( nil, X, nil) ). % Ввести X в пустое дерево

добкор( дер( L, Y, R), X, дер( L1, X, дер( L2, Y, R) )) :-

 больше( Y, X),

 добкор( L, X, дер( L1, X, L2) ).

добкор( дep( L, Y, R), X, дep( дep( L, Y, R1), X, R2) ) :-

 больше( X, Y),

 добкор( R, X, дер( R1, X, R2) ).

Рис. 9.15. Внесение элемента на произвольный уровень двоичного справочника.

Эта процедура обладает тем замечательным свойством, что в нее не заложено никаких ограничений на уровень дерева, в который вносится новый элемент. В связи с этим операцию добавить можно использовать "в обратном направлении" для удаления элемента из справочника. Например, приведенная ниже последовательность целей строит справочник Д, содержащий элементы 3, 5, 1, 6, а затем удаляет из него элемент 5, после чего получается справочник ДД:

добавить( nil, 3, Д1), добавить( Д1, 5, Д2),

добавить( Д2, 1, Д3), добавить( Д3, 6, Д),

добавить( ДД, 5, Д).

9.4. Отображение деревьев

Так же, как и любые объекты данных в Прологе, двоичное дерево T может быть непосредственно выведено на печать при помощи встроенной процедуры

write

write( T)

хотя и отпечатает всю информацию, содержащуюся в дереве, но действительная структура дерева никак при этом не будет выражена графически. Довольно утомительная работа — пытаться представить себе структуру дерева, рассматривая прологовский терм, которым она представлена. Поэтому во многих случаях желательно иметь возможность отпечатать дерево в такой форме, которая графически соответствует его структуре.

Существует относительно простой способ это сделать. Уловка состоит в том, чтобы изображать дерево растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким образом, чтобы корень стал его крайним слева элементом, а листья сдвинулись вправо (рис. 9.16).

Рис. 9.16. (а) Обычное изображение дерева. (b) То же дерево, отпечатанное процедурой

отобр

Давайте определим процедуру

отобр( T)

так, чтобы она отображала дерево в форме, показанной на рис. 9.16. Принцип работы этой процедуры:

Величина отступа H, которую можно выбирать по желанию, — это дополнительный параметр при отображении деревьев. Введем процедуру

отобр2( T, H)

печатающую дерево T с отступом на H пробелов от левого края листа. Связь между процедурами

отобр

отобр2

отобр( T) :- отобр2( T, 0).

На рис. 9.17 показана программа целиком. В этой программе предусмотрен сдвиг на 2 позиции для каждого уровня дерева. Описанный принцип отображения можно легко приспособить для деревьев других типов.

отобр( T) :-

 отобр2( T, 0).

отобр2( nil, _ ).

отобр2( дер( L, X, R), Отступ) :-

 Отступ2 is Отступ + 2,

 отобр2( R, Отступ2),

 tab( Отступ), write( X), nl,

 отобр( L, Отступ2).

Рис. 9.17. Отображение двоичного дерева.

9.14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья — справа. Напишите (более сложную) процедуру для отображения дерева, ориентированного обычным образом, т.е. с корнем наверху и листьями внизу.

9.5. Графы

9.5.1. Представление графов

Графы используются во многих приложениях, например для представления отношений, ситуаций или структур задач. Граф определяется как множество вершин вместе с множеством ребер, причем каждое ребро задается парой вершин. Если ребра направлены, то их также называют дугами. Дуги задаются упорядоченными парами. Такие графы называются направленными. Ребрам можно приписывать стоимости, имена или метки произвольного вида, в зависимости от конкретного приложения. На рис. 9.18 показаны примеры графов.

В Прологе графы можно представлять различными способами. Один из них — каждое ребро записывать в виде отдельного предложения. Например, графы, показанные на рис. 9.18, можно представить в виде следующего множества предложений:

связь( а, b).

связь( b, с).

...

дуга( s, t, 3).

дуга( t, v, 1).

дуга( u, t, 2).

...

Другой способ — весь граф представлять как один объект. В этом случае графу соответствует пара множеств — множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро — парой вершин. Для объединения двух множеств в пару будем применять функтор

граф

, а для записи ребра — функтор

p

. Тогда (ненаправленный) граф рис. 9.18 примет вид:

G1 = граф( [a, b, c, d],

 [p( а, b), p( b, d), p( b, с), p( c, d)] )

Рис. 9.18. (а) Граф. (b) Направленный граф. Каждой дуге приписана ее стоимость.

Для представления направленного графа (рис. 9.18), применив функторы

диграф

и

д

(для дуг), получим

G2 = диграф( [s, t, u, v],

 [д( s, t, 3), д( t, v, 1), д( t, u, 5), д( u, t, 2),

 д( v, u, 2) ] )

Если каждая вершина графа соединена ребром еще по крайней мере с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку оно неявным образом содержится в списке ребер.

Еще один способ представления графа — связать с каждой вершиной список смежных с ней вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины- плюс ее список смежности. Наши графы (рис. 9.18), например, можно представить как

G1 = [ a->[b1, b->[a, c, d], c->[b, d], d->[b, c] ]

G2 = [s->[t/3], t->[u/5, v/l], u->[t/2], v->[u/2]]

Здесь символы '

->

' и '

/

' — инфиксные операторы.

Какой из способов представления окажется более удобным, зависит от конкретного приложения, а также от того, какие операции имеется в виду выполнять над графами. Вот типичные операции:

• найти путь между двумя заданными вершинами;

• найти подграф, обладающий некоторыми заданными свойствами.

Примером последней операции может служить построение основного дерева графа. В последующих разделах, мы рассмотрим некоторые простые программы для поиска пути в графе и построения основного дерева.

9.5.2. Поиск пути в графе

Пусть G — граф, а А и Z — две его вершины. Определим отношение

путь( А, Z, G, P)

где P — ациклический путь между А и Z в графе G. Если G — граф, показанный в левой части рис. 9.18, то верно:

путь( a, d, G, [a, b, d] )

путь( а, d, G, [a, b, c, d] )

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

Для того, чтобы найти ациклический путь P между А и Z в графе G, необходимо:

Если А = Z , то положить P = [А], иначе найти ациклический путь P1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из P1.

В этой формулировке неявно предполагается, что существует еще одно отношение, соответствующее поиску пути со следующий ограничением: путь не должен проходить через вершины из некоторого подмножества (в данном случае P1) множества всех вершин графа. В связи с этим мы определим ещё одну процедуру:

путь1( А, P1, G, P)

Аргументы в соответствии с рис. 9.19 имеют следующий смысл:

• А — некоторая вершина,

• G — граф,

• P1 — путь в G,

• P — ациклический путь в G, идущий из А в начальную вершину пути P1, а затем — вдоль пути P1 вплоть до его конца.

Pис. 9.19. Отношение

путь1

:

Путь

— это путь между

А

и

Z

, в своей заключительной части он перекрывается с

Путь1

.

Между

путь

и

путь1

имеется следующее соотношение:

путь( А, Z, G, P) :- путь1( А, [Z], G, P).

На рис. 9.19 показана идея рекурсивного определения отношения

путь1

. Существует "граничный" случай, когда начальная вершина пути P1 (Y на рис. 9.19) совпадает с начальной вершиной А пути P. Если же начальные вершины этих двух путей не совпадают, то должна существовать такая вершина X, что

(1) Y — вершина, смежная с X,

(2) X не содержится в P1 и

(3) для P выполняется отношение

путь1( А, [X | P1], G, P)

.

путь( A, Z, Граф, Путь) :-

 путь1( А, [Z], Граф, Путь).

путь1( А, [А | Путь1, _, [А | Путь1] ).

путь1( А, [Y | Путь1], Граф, Путь) :-

 смеж( X, Y, Граф),

 принадлежит( X, Путь1), % Условие отсутствия цикла

 путь1( А, [ X, Y | Путь1], Граф, Путь).

Рис. 9.20. Поиск в графе

Граф

ациклического пути

Путь

из А в Z.

На рис. 9.20 программа показана полностью. Здесь

принадлежит

— отношение принадлежности элемента списку. Отношение

смеж( X, Y, G)

означает, что в графе G существует дуга, ведущая из X в Y. Определение этого отношения зависит от способа представления графа. Если G представлен как пара множеств (вершин и ребер)

G = граф( Верш, Реб)

то

смеж( X, Y, граф( Верш, Реб) ) :-

 принадлежит( p( X, Y), Реб);

 принадлежит( p( Y, X), Реб).

Классическая задача на графах — поиск Гамильтонова цикла, т.е. ациклического пути, проходящего через все вершины графа. Используя отношение

путь

, эту задачу можно решить так:

гамильтон( Граф, Путь) :-

 путь( _, _, Граф, Путь),

 всевершины( Путь, Граф).

всевершины( Путь, Граф) :-

 not (вершина( В, Граф),

 not принадлежит( В, Путь) ).

Здесь

вершина( В, Граф)

означает:

В

— вершина графа

Граф

.

Каждому пути можно приписать его стоимость. Стоимость пути равна сумме стоимостей входящих в него дуг. Если дугам не приписаны стоимости, то тогда, вместо стоимости, говорят о длине пути.

Для того, чтобы наши отношения

путь

и

путь1

могли работать со стоимостями, их нужно модифицировать, введя дополнительный аргумент для каждого пути:

путь( А, Z, G, P, С)

путь1( A, P1, C1, G, P, С)

Здесь С — стоимость пути P, a C1 — стоимость пути P1. В отношении

смеж

также появится дополнительный аргумент, стоимость дуги. На рис. 9.21 показана программа поиска пути, которая строит путь и вычисляет его стоимость.

путь( А, Z, Граф, Путь, Ст) :-

 путь1( A, [Z], 0, Граф, Путь, Ст).

путь1( А, [А | Путь1], Ст1, Граф, [А | Путь1], Ст).

путь1( А, [Y | Путь1], Ст1, Граф, Путь, Ст) :-

 смеж( X, Y, СтXY, Граф),

 not принадлежит( X, Путь1),

 Ст2 is Ст1 + СтXY,

 путь1( А, [ X, Y | Путь1], Ст2, Граф, Путь, Ст).

Рис. 9.21. Поиск пути в графе:

Путь

— путь между А и Z в графе

Граф

стоимостью Ст.

Эту процедуру можно использовать для нахождения пути минимальной стоимости. Мы можем построить путь минимальной стоимости между вершинами

Верш1

,

Верш2

графа

Граф

, задав цели

путь( Bepш1, Верш2, Граф, МинПуть, МинСт),

 not( путь( Верш1, Верш2, Граф, _, Ст), Ст<МинСт )

Аналогично можно среди всех путей между вершинами графа найти путь максимальной стоимости, задав цели

путь( _, _, Граф, МаксПуть, МаксСт),

 not( путь( _, _, Граф, _, Ст), Ст > МаксСт)

Заметим, что приведенный способ поиска максимальных и минимальных путей крайне неэффективен, так как он предполагает просмотр всех возможных путей и потому не подходит для больших графов из-за своей высокой временной сложности. В искусственном интеллекте задача поиска пути возникает довольно часто. В главах 11 и 12 мы изучим более сложные методы нахождения оптимальных путей.

Дер1 = [а-b, b-c, c-d]

Дер2 = [а-b, b-d, d-с]

Дер3 = [а-b, b-d, b-c]

остдерево( G, T)

расширить( Дер1, Дер, G)

G

Дер1

Дер

G

Дер

G

G

Дер1

Дер1

Дер

% Построение остовного дерева графа

%

% Деревья и графы представлены списками

% своих ребер, например:

% Граф = [а-b, b-с, b-d, c-d]

остдерево( Граф, Дер) :- % Дер - остовное дерево Граф'а

 принадлежит( Ребро, Граф),

 расширить( [Ребро], Дер, Граф).

расширить( Дер1, Дер, Граф) :-

 добребро( Дер1, Дер2, Граф),

 расширить( Дер2, Дер, Граф).

расширить( Дер, Дер, Граф) :-

 not добребро( Дер, _, Граф).

 % Добавление любого ребра приводит к циклу

добребро( Дер, [А-В | Дер], Граф) :-

 смеж( А, В, Граф),   % А и В - смежные вершины

 вершина( А, Дер).    % А содержится в Дер

 not вершина( В, Дер).  % А-В не порождает цикла

смеж( А, В, Граф) :-

 принадлежит ( А-В, Граф);

 принадлежит ( В-А, Граф).

вершина( А, Граф) :-   % А содержится в графе, если

 смеж( А, _, Граф).   % А смежна какой-нибудь вершине

Граф

путь

% Построение остовного дерева

% Графы и деревья представлены списками ребер.

остдерево( Граф, Дер) :-

 подмнож( Граф, Дер),

 дерево( Дер),

 накрывает( Дер, Граф).

дерево( Дер) :-

 связи( Дер),

 not имеетцикл( Дер).

связи( Дер) :-

 not ( вершина( А, Дер), вершина( В, Дер),

 not путь( А, А, Дер, _ ) ).

имеетцикл( Дер) :-

 смеж( А, В, Дер),

 путь( А, В, Дер, [А, X, Y | _ ). % Длина пути > 1

накрывает( Дер, Граф) :-

 not ( вершина( А, Граф), not вершина( А, Дер) ).

подмнож( [], []).

подмнож( [ X | L], S) :-

 подмнож( L, L1),

 ( S = L1; S = [ X | L1] ).

вершина

смеж

Резюме

В данной главе мы изучали реализацию на Прологе некоторых часто используемых структур данных и соответствующих операций над ними. В том числе

• Списки:

варианты представления списков

сортировка списков:

сортировка методом "пузырька"

сортировка со вставками

быстрая сортировка

эффективность этих процедур

• Представление множеств двоичными деревьями и двоичными справочниками:

поиск элемента в дереве

добавление элемента

удаление элемента

добавление в качестве листа или корня

сбалансированность деревьев и его связь с эффективностью этих операций

отображение деревьев

• Графы:

представление графов

поиск пути в графе

построение остовного дерева

В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограммированных в данной главе, можно найти, например, в Aho, Hopcroft and Ullman (1974, 1983) или Baase (1978). В литературе рассматривается также поведение этих алгоритмов, особенно их временная сложность. Хороший и краткий обзор соответствующих алгоритмов и результатов их математического анализа можно найти в Gonnet (1984).

Прологовская программа для внесения нового элемента на произвольный уровень дерева (раздел 9.3) была впервые показана автору М. Ван Эмденом (при личном общении).

Aho А. V., Hopcroft J. E. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. — М.: Мир, 1979.]

Aho А. V., Hopcroft J. E. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.

Baase S. (1978). Computer Algorithms. Addison-Wesley.

Gonnet G. H. (1984). Handbook of Algorithms and Data Structures. Addison-Wesley.

В данной главе мы рассмотрим усовершенствованные методы представления множеств при помощи деревьев. Основная идея состоит в том, чтобы поддерживать сбалансированности или приближенную сбалансированность дерева, с тем чтобы избежать вырождения его в список. Механизмы балансировки деревьев гарантируют, даже в худшем случае, относительно быстрый доступ к элементам данных, хранящихся в дереве, при логарифмическом порядке времени доступа. В этой главе изложено два таких механизма: двоично-троичные (кратко, 2-3) деревья и AVL-деревья. (Для изучения остальных глав понимание данной главы не обязательно.)

10.1. Двоично-троичные справочники

Двоичное дерево называют хорошо сбалансированным, если оба его поддерева имеют примерно одинаковую глубину (или размер) и сами сбалансированы. Глубина сбалансированного дерева приближенно равна log n, где n — число вершин дерева. Время, необходимое для вычислений, производимых отношениями

внутри

добавить

удалить

внутри

добавить

удалить

внутри

добавить

удалить

Рис. 10.1. Полностью разбалансированный двоичный справочник. Производительность его та же, что и у списка.

2-3 дерево определяется следующим образом: оно или пусто, или состоит из единственной вершины, или удовлетворяет следующим условиям:

• каждая внутренняя вершина имеет две или три дочерних вершины, и

• все листья дерева находятся на одном и том же уровне.

Двоично-троичным (2-3) справочником называется 2-3 дерево, все элементы данных которого хранятся в листьях и упорядочены слева направо. На рис. 10.2 показан пример. Внутренние вершины содержат метки, равные минимальным элементам тех или иных своих поддеревьев, в соответствии со следующими правилами:

• если внутренняя вершина имеет два поддерева, то она содержит минимальный элемент второго из них;

• если внутренняя вершина имеет три поддерева, то она содержит минимальные элементы второго и третьего поддеревьев.

Рис. 10.2. 2-3 справочник. Отмеченный путь показывает процесс поиска элемента 10.

При поиске элемента X в 2-3 справочнике мы начинаем с корня и двигаемся в направлении самого нижнего уровня, руководствуясь при этом метками внутренних вершин дерева. Пусть корень содержит метки M1 и M2, тогда

• если X < M1, то поиск продолжается в левом поддереве, иначе

• если X < M2, то поиск продолжается в среднем поддереве, иначе —

• в правом поддереве.

Если в корне находится только одна метка М, то переходим к левому поддереву при X < M и к правому поддереву — в противоположном случае. Продолжаем применять сформулированные выше правила, пока не окажемся на самом нижнем уровне дерева, где и выяснится, найден ли элемент X, или же поиск потерпел неудачу.

Так как все листья 2-3 дерева находятся на одном и том же уровне, 2-3 дерево идеально сбалансировано с точки зрения глубины составляющих его поддеревьев. Все пути от корня до листа, которые мы проходим при поиске, имеют одну и ту же длину порядка log n, где n — число элементов, хранящихся в дереве.

При добавлении нового элемента данных 2-3 дерево может расти не только в глубину, но и в ширину. Каждая внутренняя вершина, имеющая два поддерева, может приобрести новое поддерево, что приводит к росту вширь. Если же, с другой стороны, у вершины уже есть три поддерева, и она должна принять еще одно, то она расщепляется на две вершины, каждая из которых берет на себя по два из имеющихся четырех поддеревьев. Образовавшаяся при этом новая вершина передается вверх по дереву для присоединения к одной из выше расположенных вершин. Если же эта ситуация возникает на самом высоком уровне, то дерево вынуждено "вырасти" на один уровень вверх. Рис. 10.3 иллюстрирует описанный принцип.

Рис. 10.3. Вставление нового элемента в 2-3 справочник. Дерево растет сначала вширь, а затем уже вглубь.

Включение нового элемента в 2-3 справочник мы запрограммируем как отношение

доб23( Дер, X, НовДер)

где дерево

НовДер

X

Дер

встав

встав( Дер, X, НовДер).

Здесь

НовДер

X

Дер

Дер

НовДер

встав( Дер, X, НДа, Mб, НДб).

Имеется в виду, что при вставления

X

Дер

Дер

НДа

НДб

Дер

Мб

НДб

Рис. 10.4. Объекты, показанные на рисунке, удовлетворяют отношению

встав( Дер, 6, НДа, Мб, НДб)

2-3 деревья мы будем представлять в программе следующим образом:

•

nil

•

л( X)

•

в2( Д1, М, Д2)

•

в3( Д1, M2, Д2, М3, Д3)

Между

доб23

встав

доб23( Дер, X, НовДер) :-

 встав( Дер, X, НовДер).

Однако если после вставления элемента глубина дерева увеличивается, то

встав

доб23( Дер, X, в2( Д1, М, Д2) ) :-

 встав( Дер, X, Д1, М, Д2).

Отношение

встав

встав

встав

Случай а

 встав( в2( Д1, M, Д2), X, в2( НД1, M, Д2) ) :-

 больше( M, X), % M больше, чем X

 встав( Д1, X, НД1).

Случай b

 встав( в2( Д1, M, Д2), X, в3( НД1а, Мб, НД1б, M, Д2) ) :-

 больше( M, X),

 встав( Д1, X, НД1а, Мб, НД1б).

Случай с

 встав( в3( Д1, M2, Д2, М3, Д3), X,

 в2( НД1а, Мб, НД1б), M2, в2(Д2, М3, Д3) ) :-

 больше( M2, X),

 встав( Д1, X, НД1а, Мб, НД1б).

Рис. 10.5. Некоторые из случаев работы отношения

встав

встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) )

встав( в2( Д1, М, Д2), X, в3( НД1а, Мб, НД1б, М, Д2) )

встав( в3( Д1, M2, Д2, М3, Д3), X, в2( НД1а, Мб, НД1б), M2, в2( Д2, М3, Д3) )

% Вставление элемента в 2-3 справочник

доб23( Дер, X, Дер1) :-   % Вставить X в Дер, получить Дер1

 встав( Дер, X, Дер1).    % Дерево растет вширь

доб23( Дер, X, в2( Д1, M2, Д2) ) :-

 встав( Дер, X, Д1, M2, Д2). % Дерево растет вглубь

доб23( nil, X, л( X) ).

встав( л( А), X, л( А), X, л( X) ) :-

 больше( X, А).

встав( л( А), X, л( X), А, л( А) ) :-

 больше( А, X).

встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) ) :-

 больше( М, X),

 встав( Д1, X, НД1).

встав( в2( Д1, М, Д2), X, в3( НД1а, Мб, НД1б, М, Д2) ) :-

 больше( М, X),

 встав( Д1, X, НД1а, Мб, НД1б).

встав( в2( Д1, М, Д2), X, в2( Д1, М, НД2) ) :-

 больше( X, М),

 встав( Д2, X, НД2).

встав( в2( Д1, М, Д2), X, в3( Д1, М, НД2а, Мб, НД2б) ) :-

 больше( X, М),

 встав( Д2, X, НД2а, Мб, НД2б).

встав( в3( Д1, M2, Д2, М3, Д3), X,

 в3( НД1, M2, Д2, М3, Д3) :-

 больше( M2, X),

 встав( Д1, X, НД1).

встав( в3( Д1, M2, Д2, М3, Д3), X,

 в2( НД1а, Мб, НД1б), M2, в2( Д2, М3, Д3) ) :-

 больше( M2, X),

 встав( Д1, X, НД1а, Мб, НД1б).

встав( в3( Д1, M2, Д2, М3, Д3), X,

 в3( Д1, M2, НД2, М3, Д3) ) :-

 больше( X, M2), больше( М3, X),

 встав( Д2, X, НД2).

встав( в3( Д1, M2, Д2, М3, Д3), X,

 в2( Д1, M2, НД2а), Мб, в2( НД2б, М3, Д3) ) :-

 больше( X, M2), больше( М3, X),

 встав( Д2, X, НД2а, Мб, НД2б).

встав( в3( Д1, M2, Д2, М3, Д3), X,

 в3( Д1, M2, Д2, М3, НД3) ) :-

 больше( X, М3),

 встав( Д3, X, НД3).

встав( в3( Д1, M2, Д2, М3, Д3), X,

 в2( Д1, M2, Д2), М3, в2( НД3а, Мб, НД3б) ) :-

 больше( X, М3),

 встав( Д3, X, НД3а, Мб, НД3б).

Рис. 10.6. Вставление элемента в 2-3 справочник. В этой программе предусмотрено, что попытка повторного вставления элемента терпит неудачу.

Программа для вставления нового элемента в 2-3 справочник показана полностью на рис. 10.6. На рис. 10.7 показана программа вывода на печать 2-3 деревьев.

Наша программа иногда выполняет лишние возвраты. Так, если

встав

встав

встав

встав2( Дер, X, Деревья)

где

Деревья

Деревья = [ НовДер]

встав( Дер, X, НовДер)

Деревья = [ НДа, Мб, НДб]

если

встав( Дер, X, НДа, Мб, НДб)

Теперь отношение

доб23

доб23( Д, X, Д1) :-

 встав( Д, X, Деревья),

 соединить( Деревья, Д1).

Отношение

соединить

Деревья

% Отображение 2-3 справочников

отобр(Д) :- 

 отобр( Д, 0).

отобр( nil, _ ).

отобр( л(А), H) :-

 tab( H), write( A), nl.

отобр( в2( Д1, М, Д2), H) :-

 H1 is H + 5,

 отобр( Д2, H1),

 tab( H), write( --), nl,

 tab( H), write( M), nl,

 tab( H), write( --), nl,

 отобр( Д1, H1).

отобр( в3( Д1, M2, Д2, М3, Д3), H) :-

 H1 is H + 5

 отобр( Д3, H1),

 tab( H), write( --), nl,

 tab( H), write( M3), nl,

 отобр( Д2, H1),

 tab( H), write( M2), nl,

 tab( H), write( --), nl,

 отобр( Д1, H1).

(a)

      15

   --

    15

    --

     13

  --

  13

  --

    12

   --

   12

    10

   10

   --

     8

--

 8

--

    7

  --

   7

  --

 --

  5

 --

    4

  --

   4

    3

   3

  --

    1

10.2. AVL-дерево: приближенно сбалансированное дерево

AVL-дерево — это дерево, обладающее следующими свойствами:

(1) Левое и правое поддеревья отличаются по глубине не более чем на 1.

(2) Оба поддерева являются AVL-деревьями.

Деревья, удовлетворяющие этому определению, могут быть слегка разбалансированными. Однако можно показать, что даже в худшем случае глубина AVL-дерева примерно пропорциональна log n, где n — число вершин дерева. Таким образом гарантируется логарифмический порядок производительности операций

внутри

добавить

удалить

Операции над AVL-деревом работают по существу так же, как и над двоичным справочником. В них только сделаны добавления, связанные с поддержанием приближенной сбалансированности дерева. Если после вставления или удаления дерево перестает быть приближенно сбалансированным, то специальные механизмы возвращают ему требуемую степень сбалансированности. Для того, чтобы эффективно реализовать этот механизм, нам придется сохранять некоторую дополнительную информацию относительно степени сбалансированности дерева. На самом деле, нам нужно знать только разность между глубинами поддеревьев, которая может принимать значения -1, 0 или +1. Тем не менее для простоты мы предпочтем сохранять сами величины глубин поддеревьев, а не разности между ними.

Мы определим отношение вставления элемента как

доб_avl( Дер, X, НовДер)

где оба дерева

Дер

НовДер

НовДер

Дер

X

д( Лев, А, Прав)/Глуб

где

А

Лев

Прав

Глуб

nil/0

Дер = д( L, A, R)/H

Рис. 10.8. Задача вставления элемента в AVL-справочник (a) AVL-дерево перед вставлением X, X > А; (b) AVL-дерево после вставления X в R; (с) составные части, из которых следует построить новое дерево.

Начнем со случая, когда X больше А. X необходимо вставить в R, поэтому имеем следующее отношение:

доб_аv1( R, X, д( R1, В, R2)/Hb)

На рис. 10.8 показаны составные части, из которых строится дерево

НовДер

L, А, R1, В, R2

Какова глубина деревьев L, R, R1 и R2? L и R могут отличаться по глубине не более, чем на 1. На рис. 10.8 видно, какую глубину могут иметь R1 и R2. Поскольку в R был добавлен только один элемент X, только одно из поддеревьев R1, R2 может иметь глубину h+1.

Рис. 10.9. Три правила построения нового AVL-дepевa.

В случае, когда X меньше, чем А, имеем аналогичную ситуацию, причем левое и правое поддеревья меняются местами. Таким образом, в любом случае мы должны построить дерево

НовДер

Дер1

Дер2

Дер3

НовДер

НовДер

Дер1, А, Дер2, В, Дер3

Рассмотрим три случая:

(1) Среднее дерево

Дер2

(2)

Дер1

Дер2

Дер3

(3)

Дер3

Дер2

Дер1

На рис. 10.9 видно, как можно построить дерево

НовДер

Дер2

НовДер

соединить( Дер, А, Дер2, В, Дер3, НовДер)

Последний аргумент

НовДер

соединить( Д1/Н1, А, д( Д21, В, Д22)/Н2, С, Д3/Н3,

 % Пять частей

 д( д( Д1/Н1, А, Д21)/На, В, д( Д22, С, Д3/Н3)/Нс)/Нb) :-

 % Результат

 H2 > H1, H2 > Н3, % Среднее дерево глубже остальных

 На is Н1 + 1,   % Глубина левого поддерева

 Нс is Н3 + 1,   % Глубина правого поддерева

 Hb is На + 1,   % Глубина всего дерева

Программа

доб_аvl

10.3. Определите отношение

avl( Дер)

для проверки того, является ли

Дер

д( Лев, Кор, Прав) 

nil

% Вставление элемента в AVL-справочник

доб_аvl( nil/0, X, д( nil/0, X, nil/0)/1).

  % Добавить X к пустому дереву

доб_аvl( д( L, Y, R)/Ну, X, НовДер) :-

 % Добавить X к непустому дереву

 больше( Y, X),

 доб_аvl( L, X, д( L1, Z, L2)/ _ ),

 % Добавить к левому поддереву

 соединить( L1, Z, L2, Y, R, НовДер).

 % Сформировать новое дерево

доб_avl( д( L, Y, R)/Ну, X, НовДер) :-

 больше( X, Y),

 доб_avl( R, X, д( R1, Z, R2)/ _ ),

 % Добавить к правому поддереву

 соединить( L1, Y, Rl, Z, R2, НовДер).

соединить( Д1/Н1, А, д( Д21, В, Д22)/Н2, С, Д3/Н3,

 д( д( Д1/Н1, А, Д21)/На, В, д( Д22, С, L3/Н3)/Нс)/Нb) :-

 Н2 > H1, H2 > Н3,   % Среднее дерево глубже остальных

 На is H1 + 1,

 Hс is Н3 + 1,

 Нb is На + 1.

соединить( Д1/Н1, А, д( Д2/Н2, С, Д3/Н3,

 д( Д1/Н1, А, д( Д2/Н2, С, Д3/Н3)/Нс)/На) :-

 H1 >= H2, H1 >= Н3,  % "Глубокое" левое дерево

 max1( H2, Н3, Нс),

 max1( H1, Нс, На).

соединить( Д1/Н1, А, Д2/Н2, С, Д3/Н3,

 д( д( Д1/Н1, А, Д2/Н2)/На, С, Д3/Н3)/Нс) :-

 Н3 >= H2, Н3 >= H1,  % "Глубокое" правое дерево

 max1( H1, H2, На),

 max1( На, Н3, Нс).

max1( U, V, М) :-

 U > V, !, М is U + 1; % М равно 1 плюс max( U, V)

 М is V + 1.

Рис. 10.10. Вставление элемента в AVL-справочник. В этой программе предусмотрено, что попытка повторного вставления элемента терпит неудачу. По поводу процедуры

соединить

Резюме

• 2-3 деревья и AVL-деревья, представленные в настоящей главе, — это примеры сбалансированных деревьев.

• Сбалансированные или приближенно сбалансированные деревья гарантируют эффективное выполнение трех основных операций над деревьями: поиск, добавление и удаление элемента. Время выполнения этих операций пропорционально log n, где n — число вершин дерева.

2-3 деревья детально описаны, например, в Aho, Hopcroft and Ullman (1974, 1983). В книге этих авторов, вышедшей в 1983 г., дается также реализация соответствующих алгоритмов на языке Паскаль. H.Вирт (см. Wirth (1976)) приводит программу на Паскале для работы с AVL-деревьями. 2-3 деревья являются частным случаем более общего понятия В-деревьев. В-деревья, а также несколько других вариантов структур данных, имеющих отношение к 2-3 деревьям в AVL-деревьям, рассматриваются в книге Gonnet (1984). В этой книге, кроме того, даны результаты анализа поведения этих структур.

Программа вставления элемента в AVL-дерево, использующая только величину "перекоса" дерева (т.е. значение разности глубин поддеревьев, равной -1, 0 или 1, вместо самой глубины) опубликована ван Эмденом (1981).

Aho А. V., Hopcroft J. E. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. — М.: Мир, 1979.]

Aho А. V., Hopcroft J. E. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.

Gonnet G. H. (1984). Handbook of Algorithms + Data Structures. Addison-Wesley.

van Emden M. (1981). Logic Programming Newsletter 2.

Wirth N. (1976). Algorithms + Data Structures = Programs. Prentice-Hall. [Имеется перевод: Вирт H. Алгоритмы + структуры данных = программы. — M.: Мир, 1985.]

В данной главе мы сосредоточим свое внимание на одной общей схеме для представления задач, называемой пространством состояний. Пространство состояний — это граф, вершины которого соответствуют ситуациям, встречающимся в задаче ("проблемные ситуации"), а решение задачи сводится к поиску пути в этом графе. Мы изучим на примерах, как формулируются задачи в терминах пространства состояний, а также обсудим общие методы решения задач, представленных в рамках этого формализма. Процесс решения задачи включает в себя поиск в графе, при этом, как правило, возникает проблема, как обрабатывать альтернативные пути поиска. В этой главе будут представлены две основные стратегии перебора альтернатив, а именно поиск в глубину и поиск в ширину.

11.1. Предварительные понятия и примеры

Рассмотрим пример, представленный на рис. 11.1. Задача состоит в выработке плана переупорядочивания кубиков, поставленных друг на друга, как показано на рисунке. На каждом шагу разрешается переставлять только один кубик. Кубик можно взять только тогда, когда его верхняя поверхность свободна. Кубик можно поставить либо на стол, либо на другой кубик. Для того, чтобы построить требуемый план, мы должны отыскать последовательность ходов, реализующую заданную трансформацию.

Эту задачу можно представлять себе как задачу выбора среди множества возможных альтернатив. В исходной ситуации альтернатива всего одна: поставить кубик С на стол. После того как кубик С поставлен на стол, мы имеем три альтернативы:

• поставить А на стол или

• поставить А на С, или

• поставить С на А.

Рис. 11.1. Задача перестановки кубиков.

Ясно, что альтернативу "поставить С на стол" не имело смысла рассматривать всерьез, так как этот ход никак не влияет на ситуацию.

Как показывает рассмотренный пример, с задачами такого рода связано два типа понятий:

(1) Проблемные ситуации.

(2) Разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.

Проблемные ситуации вместе с возможными ходами образуют направленный граф, называемый пространством состояний. Пространство состояний для только что рассмотренного примера дано на рис. 11.2. Вершины графа соответствуют проблемным ситуациям, дуги — разрешенным переходам из одних состояний в другие. Задача отыскания плана решения задачи эквивалентна задаче построения пути между заданной начальной ситуацией ("стартовой" вершиной) и некоторой указанной заранее конечной ситуацией, называемой также целевой вершиной.

На рис. 11.3 показан еще один пример задачи: головоломка "игра в восемь" в ее представление в виде задачи поиска пути. В головоломке используется восемь перемещаемых фишек, пронумерованных цифрами от 1 до 8. Фишки располагаются в девяти ячейках, образующих матрицу 3 на 3. Одна из ячеек всегда пуста, и любая смежная с ней фишка может быть передвинута в эту пустую ячейку. Можно сказать и по-другому, что пустой ячейке разрешается перемещаться, меняясь местами с любой из смежных с ней фишек. Конечная ситуация — это некоторая заранее заданная конфигурация фишек, как показано на рис. 11.3.

Рис. 11.2. Графическое представление задачи манипулирования кубиками. Выделенный путь является решением задачи рис. 11.1.

Нетрудно построить аналогичное представление в виде графа и для других популярных головоломок. Наиболее очевидные примеры — это задача о "ханойской башне" и задача о перевозке через реку волка, козы и капусты. Во второй из этих задач предполагается, что вместе с человекам в лодке помещается только один объект и что человеку приходится охранять козу от волка и капусту от козы. С описанной парадигмой согласуются также многие задачи, имеющие практическое значение. Среди них — задача о коммивояжере, которая может служить моделью для многих практических оптимизационных задач. В задаче дается карта с n городами в указываются расстояния, которые надо преодолеть по дорогам при переезде из города в город. Необходимо найти маршрут, начинающийся в некотором городе, проходящий через все города и заканчивающиеся в том же городе. Ни один город, за исключением начального, не разрешается посещать дважды.

Рис. 11.3. "Игра в восемь" и ее представление в форме графа.

Давайте подытожим те понятия, которые мы ввели, рассматривая примеры. Пространство состояний некоторой задачи определяет "правила игры": вершины пространства состояния соответствуют ситуациям, а дуги — разрешенным ходам или действиям, или шагам решения задачи. Конкретная задача определяется

• пространством состояний

• стартовой вершиной

• целевым условием (т.е. условием, к достижению которого следует стремиться); "целевые вершины" — это вершины, удовлетворяющие этим условиям.

Каждому разрешенному ходу или действию можно приписать его стоимость. Например, в задаче манипуляции кубиками стоимости, приписанные тем или иным перемещениям кубиков, будут указывать нам на то, что некоторые кубики перемещать труднее, чем другие. В задаче о коммивояжере ходы соответствуют переездам из города в город. Ясно, что в данном случае стоимость хода — это расстояние между соответствующими городами.

В тех случаях, когда каждый ход имеет стоимость, мы заинтересованы в отыскании решения минимальной стоимости. Стоимость решения — это сумма стоимостей дуг, из которых состоит "решающий путь" — путь из стартовой вершины в целевую. Даже если стоимости не заданы, все равно может возникнуть оптимизационная задача: нас может интересовать кратчайшее решение.

Прежде тем будут рассмотрены некоторые программы, реализующие классический алгоритм поиска в пространстве состоянии, давайте сначала обсудим. как пространство состояний может быть представлено в прологовской программе.

Мы будем представлять пространство состояний при помощи отношения

после( X, Y)

которое истинно тогда, когда в пространстве состояний существует разрешенный ход из вершины X в вершину Y. Будем говорить, что Y — это преемник вершины X. Если с ходами связаны их стоимости, мы добавим третий аргумент, стоимость хода:

после( X, Y, Ст)

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

после

Рассмотрим в качестве примера задачу манипулирования кубиками, проиллюстрированную на рис. 11.1. Мы будем рассматривать более общий случай, когда имеется произвольное число кубиков, из которых составлены столбики, — один или несколько. Число столбиков мы ограничим некоторым максимальным числом, чтобы задача была интереснее. Такое ограничение, кроме того, является вполне реальным, поскольку рабочее пространство, которым располагает робот, манипулирующий кубиками, ограничено.

Проблемную ситуацию можно представить как список столбиков. Каждый столбик в свою очередь представляется списком кубиков, из которых он составлен. Кубики упорядочены в списке таким образом, что самый верхний кубик находится в голове списка. "Пустые" столбики изображаются как пустые списки. Таким образом, исходную ситуацию рис. 11.1 можно записать как терм

[ [с, а, b], [], [] ]

Целевая ситуация — это любая конфигурация кубиков, содержащая, столбик, составленный из всех имеющихся кубиков в указанном порядке. Таких ситуаций три:

[ [a, b, c], [], [] ]

[ [], [а, b, с], [] ]

[ [], [], [a, b, c] ]

Отношение следования можно запрограммировать, исходя из следующего правила: ситуация

Сит2

Сит1

Сит1

Столб1

Столб2

Столб1

Столб2

Сит2

после( Столбы, [Столб1, [Верх1 | Столб2], Остальные]) :-

 % Переставить Верх1 на Столб2

 удалить( [Верх1 | Столб1], Столб1, Столб1),

 % Найти первый столбик

 удалить( Столб2, Столбы1, Остальные).

 % Найти второй столбик

удалить( X, [X | L], L).

удалить( X, [Y | L], [Y | L1] ) :-

 удалить( L, X, L1).

В нашем примере целевое условие имеет вид:

цель( Ситуация) :-

 принадлежит [а,b,с], Ситуация)

Алгоритм поиска мы запрограммируем как отношение

решить( Старт, Решение)

где

Старт

Решение

Старт

?- решить( [ [с, а, b], [], [] ], Решение).

В результате успешного поиска переменная

Решение

[а, b, с]

11.2. Стратегия поиска в глубину

Существует много различных подходов к проблеме поиска решающего пути для задач, сформулированных в терминах пространства состояний. Основные две стратегии поиска — это поиск в глубину и поиск в ширину. В настоящем разделе мы реализуем первую из них.

Мы начнем разработку алгоритма и его вариантов со следующей простой идеи:

Реш

В

В

Реш = [В]

В

В1

Реш1

В1

Реш = [В | Peш1]

Рис. 11.4. Пример простого пространства состояний: а — стартовая вершина, f и j — целевые вершины. Порядок, в которой происходит проход по вершинам пространства состояний при поиске в глубину: а, b, d, h, e, i, j. Найдено решение

[a, b, e, j]

[а, с, f]

На Пролог это правило транслируется так:

решить( В, [В] ) :-

 цель( В).

решить( В, [В | Реш1] ) :-

 после( В, В1 ),

 решить( В1, Реш1).

Эта программа и есть реализация поиска в глубину. Мы говорим "в глубину", имея в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. Всегда, когда алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в которую следует перейти для продолжения поиска, он предпочитает самую "глубокую" из них. Самая глубокая вершина — это вершина, расположенная дальше других от стартовой вершины. На рис. 11.4 мы видим на примере, в каком порядке алгоритм проходит по вершинам. Этот порядок в точности соответствует результату трассировки процесса вычислений в пролог-системе при ответе на вопрос

?- решить( а, Реш).

Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Причина этого состоит в том, что, обрабатывая цели, пролог-система сама просматривает альтернативы именно в глубину.

Поиск в глубину прост, его легко программировать и он в некоторых случаях хорошо работает. Программа для решения задачи о восьми ферзях (см. гл. 4) фактически была примером поиска в глубину. Для того, чтобы можно было применить к этой задаче описанную выше процедуру

решить

• вершины пространства состояний — позиции, в которых поставлено 0 или более ферзей на нескольких последовательно расположенных горизонтальных линиях доски;

• вершина-преемник данной вершины может быть получена из нее после того, как в соответствующей позиции на следующую горизонтальную линию доски будет поставлен еще один ферзь, причем таким образом, чтобы ни один из уже поставленных ферзей не оказался под боем;

• стартовая вершина — пустая доска (представляется пустым списком);

• целевая вершина — любая позиция с восемью ферзями (правило получения вершины-преемника гарантирует, что ферзи не бьют друг друга).

Позицию на доске будем представлять как список Y-координат поставленных ферзей. Получаем программу:

после( Ферзи, [Ферзь | Ферзи] ) :-

 принадлежит( Ферзь, [1, 2, 3, 4, 5, 6, 7, 8] ),

 % Поместить ферзя на любую вертикальную линию

 небьет( Ферзь, Ферзи).

цель( [ _, _, _, _, _, _, _, _ ] )

 % Позиция с восемью ферзями

Отношение

небьет

Ферзь

Ферзи

?- решить( [], Решение)

будет выглядеть как список позиций с постепенно увеличивающимся количеством поставленных ферзей. Список завершается "безопасной" конфигурацией из восьми ферзей. Механизм возвратов позволит получить и другие решения задачи.

Поиск в глубину часто работает хорошо, как в рассмотренном примере, однако наша простая процедура

решить

Рис. 11.5. Начинаясь в а, поиск в глубину заканчивается бесконечным циклом между d и h: a, b, d, h, d, h, d ….

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

вглубину( Путь, Верш, Решение)

Как видно из рис. 11.6,

Верш

Путь

Верш

Решение

Путь

Рис. 11.6. Отношение

вглубину( Путь, В, Решение)

Для облегчения программирования вершины в списках, представляющих пути, будут расставляться в обратном порядке. Аргумент

Путь

(1) чтобы не рассматривать тех преемников вершины

Верш

(2) чтобы облегчить построение решающего пути

Решение

решить( Верш, Решение) :-

 вглубину( [], Верш, Решение).

вглубину( Путь, Верш, [Верш | Путь] ) :-

 цель( Верш).

вглубину( Путь, Верш, Реш) :-

 после( Верш, Верш1),

 not принадлежит( Верш1, Путь), % Цикл?

 вглубину( [Верш | Путь], Верш1, Реш).

Рис. 11.7. Программа поиска в глубину без зацикливания.

Теперь наметим один вариант этой программы. Аргументы

Путь

Верш

вглубину

[Верш | Путь]

Верш

П = [Верш | Путь]

вглубину( П, Решение)

оставим читателю в качестве упражнения.

Наша процедура поиска в глубину, снабженная механизмом обнаружения циклов, будет успешно находить решающие пути в пространствах состояний, подобных показанному на рис. 11.5. Существуют, однако, такие пространства состоянии, в которых наша процедура не дойдет до цели. Дело в том, что многие пространства состояний бесконечны. В таком пространстве алгоритм поиска в глубину может "потерять" цель, двигаясь вдоль бесконечной ветви графа. Программа будет бесконечно долго обследовать эту бесконечную область пространства, так и не приблизившись к цели. Пространство состояний задачи о восьми ферзях, определенное так, как это сделано в настоящем разделе, на первый взгляд содержит ловушку именно такого рода. Но оказывается, что оно все-таки конечно, поскольку Y-координаты выбираются из ограниченного множества, и поэтому на доску можно поставить "безопасным образом" не более восьми ферзей.

вглубину2( Верш, [Верш], _ ) :-

 цель( Верш).

вглубину2( Верш, [Верш | Реш], МаксГлуб) :-

 МаксГлуб > 0,

 после( Верш, Верш1),

 Maкс1 is МаксГлуб - 1,

 вглубину2( Верш1, Реш, Maкс1).

Рис. 11.8. Программа поиска в глубину с ограничением по глубине.

Для того, чтобы предотвратить бесцельное блуждание по бесконечным ветвям, мы можем добавить в базовую процедуру поиска в глубину еще одно усовершенствование, а именно, ввести ограничение на глубину поиска. Процедура поиска в глубину будет тогда иметь следующие аргументы:

вглубину2( Верш, Решение, МаксГлуб)

Не разрешается вести поиск на глубине большей, чем

МаксГлуб

вглубину2

11.1. Напишите процедуру поиска в глубину (с обнаружением циклов)

вглубину1( ПутьКандидат, Решение)

отыскивающую решающий путь

Решение

ПутьКандидат

Решение

11.2. Напишите процедуру поиска в глубину, сочетающую в себе обнаружение циклов с ограничением глубины, используя рис. 11.7 и 11.8.

11.3. Проведите эксперимент по применению программы поиска в глубину к задаче планирования в "мире кубиков" (рис. 11.1).

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

отобр( Ситуация)

для отображения состояния задачи "перестановки кубиков". Пусть

Ситуация

отобр( [ [a], [e, d], [с, b] ] )

должна отпечатать соответствующую ситуацию, например так:

    e    с

a   d    b

==============

11.3. Поиск в ширину

В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайший к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину, что иллюстрирует рис. 11.9.

Рис. 11.9. Простое пространство состояний: а — стартовая вершина, f и j — целевые вершины. Применение стратегии поиска в ширину дает следующий порядок прохода по вершинам: а, b, c, d, e, f. Более короткое решение

[a, c, f]

найдено раньше, чем более длинное

[а, b, e, j]

Поиск в ширину программируется не так легко, как поиск в глубину. Причина состоят в том, что нам приходится сохранять все множество альтернативных вершин-кандидатов, а не только одну вершину, как при поиске в глубину. Более того, если мы желаем получить при помощи процесса поиска решающий путь, то одного множества вершин недостаточно. Поэтому мы будем хранить не множество вершин-кандидатов, а множество путей-кандидатов. Таким образом, цель

вширину( Пути, Решения)

истинна только тогда, когда существует путь из множества кандидатов

Пути

, который может быть продолжен вплоть до целевой вершины. Этот продолженный путь и есть

Решение

.

[ [СтартВерш] ]

решить( Старт, Решение) :-

 вширину( [ [Старт] ], Решение).

вширину( [ [Верш | Путь] | _ ], [Верш | Путь] ) :-

 цель( Верш).

вширину( [ [В | Путь] | Пути], Решение ) :-

 bagof( [B1, В | Путь ],

 ( после( В, В1), not принадлежит( В1, [В | Путь])),

  НовПути),

  % НовПути - ациклические продолжения пути [В | Путь]

 конк( Пути, НовПути, Пути1), !,

 вширину( Путь1, Решение);

 вширину( Пути, Решение).

 % Случай, когда у В нет преемника

решить( Старт, Решение) :-

 вширь( [ [Старт] | Z ]-Z, Решение).

вширь( [ [Верш | Путь] | _ ]-_, [Верш | Путь] ) :-

 цель( Верш).

вширь( [ [В | Путь] | Пути]-Z, Решение ) :-

 bagof( [B1, В | Путь ],

 ( после( В, В1),

   not принадлежит( В1, [В | Путь]) ),

  Нов ),

 конк( Нов, ZZ, Z), !,

 вширь( Пути-ZZ, Решение);

 Пути \== Z, % Множество кандидатов не пусто

 вширь( Пути-Z, Решение).

[ [а] ]

[а]

[ [b, а], [с, а] ]

[ [d, b, a], [e, b, а] ]

[ [с, а], [d, b, a], [e, b, а] ]

[с, а]

[ [d, b, a], [e, b, а], [f, c, a], [g, c, a] ]

[d, b, a]

[e, b, а]

[[f, c, a], [g, c, a], [h, d, b, a], [i, e, b, a], [j, e, b, a]]

[f, c, a]

f

bagof

bagof

вширину

принадлежит

конк

конк

Пути

Z

Пути-Z

11.3.2. Древовидное представление множества кандидатов

Рассмотрим теперь еще одно изменение нашей программы поиска в ширину. До сих пор мы представляли множества путей-кандидатов как списки путей. Это расточительный способ, поскольку начальные участки путей являются общими для нескольких из них. Таким образом, эти общие части путей приходится хранить во многих экземплярах. Избежать избыточности помогло бы более компактное представление множества кандидатов. Таким более компактным представлением является дерево, в котором общие участки путей хранятся в его верхней части без дублирования. Будем использовать в программе следующее представление дерева. Имеется два случая:

Случай 1: Дерево состоит только из одной вершины В; В этом случае оно имеет вид терма

л( В)

; Функтор

л

указывает на то, что В — это лист дерева.

Случай 2: Дерево состоит из корневой вершины В и множества поддеревьев Д1, Д2, …. Такое дерево представляется термом

д( В, Пд)

где

Пд

— список поддеревьев:

Пд = [ Д1, Д2, ...]

В качестве примера рассмотрим ситуацию, которая возникает после того, как порождены три уровня дерева рис. 11.9. Множество путей-кандидатов в случае спискового представления имеет вид:

[ [d, b, a], [e, b, а], [f, c, a], [g, c, a] ]

В виде дерева это множество выглядит так:

д( а, [д( b, [л( d), л( e)] ), д( с, [л( f), л( g)] )] )

На первый взгляд древовидное представление кажется еще более расточительным, чем списковое, однако это всего лишь поверхностное впечатление, связанное с компактностью прологовской нотации для списков.

В случае спискового представления множества кандидатов эффект распространения процесса в ширину достигался за счет перемещения продолженных путей в конец списка. В нашем случае мы уже не можем использовать этот прием, поэтому программа несколько усложняется. Ключевую роль в нашей программе будет играть отношение

расширить( Путь, Дер, Дер1, ЕстьРеш, Решение)

На рис. 11.12 показано, как связаны между собой аргументы отношения

расширить

. При каждом обращении к

расширить

переменные

Путь

и

Дер

будут уже конкретизированы.

Дер

— поддерево всего дерева поиска, одновременно оно служит для представления множества путей-кандидатов внутри этого поддерева.

Путь

— это путь, ведущий из стартовой вершины в корень поддерева

Дер

. Самая общая идея алгоритма — получить поддерево

Дер1

как результат расширения

Дер

на один уровень. Но в случае, когда в процессе расширения поддерева

Дер

встретится целевая вершина, процедура

расширить

должна сформировать соответствующий решающий путь.

Рис. 11.12. Отношение

paсширить( Путь, Дер, Дер1, ЕстьРеш, Решение)

:

s

— стартовая вершина,

g

— целевая вершина.

Решение

— это

Путь

, продолженный вплоть до

g

.

Дер1

— результат расширения дерева

Дер

на один уровень вниз.

Итак, процедура

расширить

будет порождать два типа результатов. На конкретный вид результата будет указывать значение переменной

ЕстьРеш

:

(1)

ЕстьРеш

= да

Решение

= решающий путь, т.е.

Путь

, продолженный до целевой вершины.

Дер1

= неконкретизировано.

Разумеется, такой тип результата получится только в том случае, когда

Дер

будет содержать целевую вершину. Добавим также, что эта целевая вершина обязана быть листом поддерева

Дер

.

(2)

ЕстьРеш

= нет

Дер1

= результат расширения поддерева

Дер

на один уровень вниз от своего "подножья".

Дер1

не содержит ни одной "тупиковой" ветви из

Дер

, т.е. такой ветви, что она либо не может быть продолжена из-за отсутствия преемников, либо любое ее продолжение приводит к циклу.

Решение

= неконкретизировано.

Если в дереве

Дер

нет ни одной целевой вершины и, кроме того, оно не может быть расширено, то процедура

расширить

терпит неудачу.

Процедура верхнего уровня для поиска в ширину

вширину( Дер, Решение)

отыскивает

Решение

либо среди множества кандидатов

Дер

, либо в его расширении. На рис. 11.3 показано, как выглядит программа целиком. В этой программе имеется вспомогательная процедура

расширитьвсе

. Она расширяет все деревья из некоторого списка, и затем, выбросив все "тупиковые" деревья", собирает все полученные расширенные деревья в один новый список. Используя механизм возвратов, она также порождает все решения, обнаруженные в деревьях из списка. Имеется одна дополнительная деталь: по крайней мере одно из деревьев должно "вырасти". Если это не так, то процедуре

расширитьвсе

не удается получить ни одного расширенного дерева - все деревья из списка оказываются "тупиковыми".

% ПОИСК В ШИРИНУ

% Множество кандидатов представлено деревом

решить( Старт, Решение) :-

 вширину( л( Старт), Решение).

вширину( Дер, Решение) :-

 расширить( [], Дер, Дер1, ЕстьРеш, Решение),

 ( ЕстьРеш = да;

  ЕстьРеш = нет, вширину( Дер1, Решение) ).

расширить( П, Л( В), _, да, [В | П] ) :-

 цель( В).

расширить( П, Л( В), д( В, Пд), нет, _ ) :-

 bagof( л( B1),

 ( после( В, B1), not принадлежит( В1, П)), Пд).

расширить( П, д( В, Пд), д( В, Пд1), ЕстьРеш, Реш) :-

 расширитьвсе( [В | П], Пд, [ ], Пд1, ЕстьРеш, Реш).

расширитьвсе( _, [ ], [Д | ДД], [Д | ДД], нет, _ ).

 % По крайней мере одно дерево должно вырасти

расширитьвсе( П, [Д | ДД], ДД1, Пд1, ЕстьРеш, Реш) :-

 расширить ( П, Д, Д1, ЕстьРеш1, Реш),

 ( ЕстьРеш 1= да, ЕстьРеш = да;

  ЕстьРеш1 = нет, !,

  расширитьвсе( П, ДД, [Д1 | ДД1], Пд1, ЕстьРеш, Реш));

 расширитьвсе( П, ДД, ДД1, Пд1, ЕстьРеш, Реш ).

Рис. 11.13. Реализация поиска в ширину с использованием древовидного представления множества путей-кандидатов.

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

Упражнения

11.5. Перепишите программу поиска в ширину рис. 11.10, используя разностное представление для списка путей-кандидатов и покажите, что в результате получится программа, приведенная на рис. 11.11. Зачем в программу рис. 11.11 включена цель

Пути \== Z

Проверьте, что случится при поиске в пространстве состояний рис. 11.9, если эту цель опустить. Различие в выполнении программы, возникнет только при попытке найти новые решения в ситуации, когда не осталось больше ни одного решения.

11.6. Как программы настоящего раздела можно использовать для поиска, начинающегося от стартового множества вершин, вместо одной стартовой вершины?

11.7. Как программы этой главы можно использовать для поиска в обратном направлении, т.е. от целевой вершины к стартовой вершине (или к одной из стартовых вершин, если их несколько). Указание: переопределите отношение

после

. В каких ситуациях обратный поиск будет иметь преимущества перед прямым поиском?

11.8. Иногда выгодно сделать поиск двунаправленным, т.е. продвигаться одновременно с двух сторон от стартовой и целевой вершин. Поиск заканчивается, когда оба пути "встречаются". Определите пространство поиска (отношение

после

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

11.9. Проведите эксперименты с различными методами поиска применительно к задаче планирования в "мире кубиков".

11.4. Замечания относительно поиска в графах, оптимальности к сложности

Сейчас уместно сделать ряд замечаний относительно программ поиска, разработанных к настоящему моменту: во-первых, о поиске в графах, во-вторых, об оптимальности полученных решений и, в-третьих, о сложности поиска.

Приведенные примеры могли создать ложное впечатление, что наши программы поиска в ширину способны работать только в пространствах состояний, являющихся деревьями, а не графами общего вида. На самом деле, тот факт, что в одной из версий множество путей-кандидатов представлялось деревом, совсем не означает, что и само пространство состояний должно было быть деревом. Когда поиск проводится в графе, граф фактически разворачивается в дерево, причем некоторые пути, возможно, дублируются в разных частях этого дерева (см. рис. 11.14).

Наши программы поиска в ширину порождают решающие пути один за другим в порядке увеличения их длин — самые короткие решения идут первыми. Это является важным обстоятельством, если нам необходима оптимальность (в отношении длины решения). Стратегия поиска в ширину гарантирует получение кратчайшего решения первым. Разумеется, это неверно для поиска в глубину.

Рис. 11.14. (а) Пространство состояний; а — стартовая вершина. (b) Дерево всех возможных ациклических путей, ведущих из а, порожденное программой поиска в ширину.

Наши программы, однако, не учитывают стоимости, приписанные дугам в пространстве состояний. Если критерием оптимальности является минимум стоимости решающего пути (а не его длина), то в этом случае поиска в ширину недостаточно. Поиск с предпочтением из гл. 12 будет направлен на оптимизацию стоимости.

Еще одна типичная проблема, связанная с задачей поиска, — это проблема комбинаторной сложности. Для нетривиальных предметных областей число альтернатив столь велико, что проблема сложности часто принимает критический характер. Легко понять, почему это происходит: если каждая вершина имеет b преемников, то число путей длины l, ведущих из стартовой вершины, равно b^l (в предположении, что циклов нет). Таким образом, вместе с увеличением длин путей наблюдается экспоненциальный рост объема множества путей-кандидатов, что приводит к ситуации, называемой комбинаторным взрывом. Стратегии поиска в глубину и ширину недостаточно "умны" для борьбы с такой степенью комбинаторной сложности: отсутствие селективности приводит к тому, что все пути рассматриваются как одинаково перспективные.

По-видимому, более изощренные процедуры поиска должны использовать какую-либо информацию, отражающую специфику данной задачи, с тем чтобы на каждой стадии поиска принимать решения о наиболее перспективных путях поиска. В результате процесс будет продвигаться к целевой вершине, обходя бесполезные пути. Информация, относящаяся к конкретной решаемой задаче и используемая для управления поиском, называется эвристикой. Про алгоритмы, использующие эвристики, говорят, что они руководствуются эвристиками: они выполняют эвристический поиск. Один из таких методов изложен в следующей главе.

Резюме

• Пространство состояний есть формализм для представления задач.

• Пространство состояний — это направленный граф, вершины которого соответствуют проблемным ситуациям, а дуги — возможным ходам. Конкретная задача определяется стартовой вершиной и целевым условием. Решению задачи соответствует путь в графе. Таким образом, решение задачи сводится к поиску пути в графе.

• Оптимизационные задачи моделируются приписыванием каждой дуге пространства состояний некоторой стоимости.

• Имеются две основных стратегии поиска в пространстве состояний — поиск в глубину и поиск в ширину.

• Поиск в глубину программируется наиболее легко, однако подвержен зацикливаниям. Существуют два простых метода предотвращения зацикливания: ограничить глубину поиска и не допускать дублирования вершин.

• Реализация поиска в ширину более сложна, поскольку требуется сохранять множество кандидатов. Это множество может быть с легкостью представлено списком списков, но более экономное представление — в виде дерева.

• Поиск в ширину всегда первым обнаруживает самое короткое решение, что не верно в отношении стратегии поиска в глубину.

• В случае обширных пространств состояний существует опасность комбинаторного взрыва. Обе стратегии плохо приспособлены для борьбы с этой трудностью. В таких случаях необходимо руководствоваться эвристиками.

• В этой главе были введены следующие понятия:

пространство состояний

стартовая вершина, целевое условие,

решающий путь

стратегия поиска

поиск в глубину, поиск в ширину

эвристический поиск.

Поиск в глубину и поиск в ширину — базовые стратегии поиска, они описаны в любом учебнике по искусственному интеллекту, см., например, Nilsson (1971, 1980) или Winston (1984). P. Ковальский в своей книге Kowalski (1980) показывает, как можно использовать аппарат математической логики для реализации этих принципов.

Kowalski R. (1980). Logic for Problem Solving. North-Holland.

Nilsson N. J. (1971). Problem Solving Methods in Artificial Intelligence. McGraw-Hill.

Nilsson N. J. (1980). Principles of Artificial Intelligence. Tioga; also Springer-Verlag, 1981.

Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. — М.: Мир, 1980.]

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

Один из путей использования эвристической информации о задаче — это получение численных эвристических оценок для вершин пространства состояний. Оценка вершины указывает нам, насколько данная вершина перспективна с точки зрения достижения цели. Идея состоит в том, чтобы всегда продолжать поиск, начиная с наиболее перспективной вершины, выбранной из всего множества кандидатов. Именно на этом принципе основана программа поиска с предпочтением, описанная в данной главе.

12.1. Поиск с предпочтением

Программу поиска с предпочтением можно получить как результат усовершенствования программы поиска в ширину (рис. 11.13). Подобно поиску в ширину, поиск с предпочтением начинается со стартовой вершины и использует множество путей-кандидатов. В то время, как поиск в ширину всегда выбирает для продолжения самый короткий путь (т.е. переходит в вершины наименьшей глубины), поиск с предпочтением вносит в этот принцип следующее усовершенствование: для каждого кандидата вычисляется оценка и для продолжения выбирается кандидат с наилучшей оценкой.

Рис. 12.1. Построение эвристической оценки f(n) стоимости самого дешевого пути из s в t, проходящего через n: f(n) = g(n) + h(n).

Мы будем в дальнейшем предполагать, что для дуг пространства состояний определена функция стоимости с(n, n') — стоимость перехода из вершины n к вершине-преемнику n'.

Пусть f — это эвристическая оценочная функция, при помощи которой мы получаем для каждой вершины n оценку f(n) трудности" этой вершины. Тогда наиболее перспективной вершиной-кандидатом следует считать вершину, для которой f принимает минимальное значение. Мы будем использовать здесь функцию f специального вида, приводящую к хорошо известному А*-алгоритму. Функция f(n) будет построена таким образом, чтобы давать оценку стоимости оптимального решающего пути из стартовой вершины s к одной из целевых вершин при условии, что этот путь проходит через вершину n. Давайте предположим, что такой путь существует и что t — это целевая вершина, для которой этот путь минимален. Тогда оценку f(n) можно представить в виде суммы из двух слагаемых (рис. 12.1):

f(n) = g(n) + h(n)

Здесь g(n) — оценка оптимального пути из s в n; h(n) — оценка оптимального пути из n в t.

Когда в процессе поиска мы попадаем в вершину n, мы оказываемся в следующей ситуация: путь из s в n уже найден, и его стоимость может быть вычислена как сумма стоимостей составляющих его дуг. Этот путь не обязательно оптимален (возможно, существует более дешевый, еще не найденный путь из s в n), однако стоимость этого пути можно использовать в качестве оценки g(n) минимальной стоимости пути из s в n. Что же касается второго слагаемого h(n), то о нем трудно что-либо сказать, поскольку к этому моменту область пространства состояний, лежащая между n и t, еще не "изучена" программой поиска. Поэтому, как правило, о значении h(n) можно только строить догадки на основании эвристических соображений, т.е. на основании тех знаний о конкретной задаче, которыми обладает алгоритм. Поскольку значение h зависит от предметной области, универсального метода для его вычисления не существует. Конкретные примеры того, как строят эти "эвристические догадки", мы приведем позже. Сейчас же будем считать, что тем или иным способом функция h задана, и сосредоточим свое внимание на деталях нашей программы поиска с предпочтением.

Можно представлять себе поиск с предпочтением следующим образом. Процесс поиска состоит из некоторого числа конкурирующих между собой подпроцессов, каждый из которых занимается своей альтернативой, т.е. просматривает свое поддерево. У поддеревьев есть свои поддеревья, их просматривают подпроцессы подпроцессов и т.д. В каждый данный момент среди всех конкурирующих процессов активен только один — тот, который занимается наиболее перспективной к настоящему моменту альтернативой, т.е. альтернативой с наименьшим значением f. Остальные процессы спокойно ждут того момента, когда f-оценки изменятся и в результате какая-нибудь другая альтернатива станет наиболее перспективной. Тогда производится переключение активности на эту альтернативу. Механизм активации-дезактивации процессов функционирует следующим образом: процесс, работающий над текущей альтернативой высшего приоритета, получает некоторый "бюджет" и остается активным до тех пор, пока его бюджет не исчерпается. Находясь в активном состоянии, процесс продолжает углублять свое поддерево. Встретив целевую вершину, он выдает соответствующее решение. Величина бюджета, предоставляемого процессу на данный конкретный запуск, определяется эвристической оценкой конкурирующей альтернативы, ближайшей к данной.

Рис. 12.2. Поиск кратчайшего маршрута из s в t. (а) Карта со связями между городами; связи помечены своими длинами; в квадратиках указаны расстояния по прямой до цели t. (b) Порядок, в котором при поиске с предпочтением происходит обход городов. Эвристические оценки основаны на расстояниях по прямой. Пунктирной линией показано переключение активности между альтернативными путями. Эта линия задает тот порядок, в котором вершины принимаются для продолжения пути, а не тот порядок, в котором они порождаются.

На рис. 12.2 показан пример поведения конкурирующих процессов. Дана карта, задача состоит в том, чтобы найти кратчайший маршрут из стартового города s в целевой город t. В качестве оценки стоимости остатка маршрута из города X до цели мы будем использовать расстояние по прямой расст( X, t) от X до t. Таким образом,

f( X) = g( X) + h( X) = g( X) + расст( X, t)

Мы можем считать, что в данном примере процесс поиска с предпочтением состоит из двух процессов. Каждый процесс прокладывает свой путь — один из двух альтернативных путей: Процесс 1 проходит через а. Процесс 2 — через e. Вначале Процесс 1 более активен, поскольку значения f вдоль выбранного им пути меньше, чем вдоль второго пути. Когда Процесс 1 достигает города с, а Процесс 2 все еще находится в e, ситуация меняется:

f( с) = g( c) + h( c) = 6 + 4 = 10

f( e) = g( e) + h( e) = 2 + 7 = 9

Поскольку f( e) < f( c), Процесс 2 переходит к f, a Процесс 1 ждет. Однако

f( f) = 7 + 4 = 11

f( c) = 10

f( c) < f( f)

Поэтому Процесс 2 останавливается, а Процессу 1 дается разрешение продолжать движение, но только до d, так как f( d) = 12 > 11. Происходит активация Процесса 2, после чего он, уже не прерываясь, доходит до цели t.

Мы реализуем этот механизм программно при помощи усовершенствования программы поиска в ширину (рис. 11.13). Множество путей-кандидатов представим деревом. Дерево будет изображаться в программе в виде терма, имеющего одну из двух форм:

(1)

л( В, F/G)

В

G

g( B)

В

F - f( В)

G + h( В)

(2)

д( В, F/G, Пд)

В

Пд

G

g( B)

F

f( В)

В

Пд

Уточнение значения f необходимо для того, чтобы дать программе возможность распознавать наиболее перспективное поддерево (т.е. поддерево, содержащее наиболее перспективную концевую вершину) на любом уровне дерева поиска. Эта модификация f-оценок на самом деле приводит к обобщению, расширяющему область определения функции f. Теперь функция f определена не только на вершинах, но и на деревьях. Для одновершинных деревьев (листов) n остается первоначальное определение

f( n) = g( n) + h( n)

Для дерева T с корнем n, имеющем преемников m₁, m₂, …, получаем

Программа поиска с предпочтением, составленная в соответствии с приведенными выше общими соображениями, показана на рис 12.3. Ниже даются некоторые дополнительные пояснения.

Так же, как и в случае поиска в ширину (рис. 11.13), ключевую роль играет процедура

расширить

расширить( Путь, Дер, Предел, Дер1, ЕстьРеш, Решение)

Эта процедура расширяет текущее (под)дерево, пока f-оценка остается равной либо меньшей, чем

Предел

% Поиск с предпочтением

эврпоиск( Старт, Решение) :-

 макс_f( Fмакс).     % Fмакс > любой  f-оценки

расширить( [], л( Старт, 0/0), Fмакс, _, да, Решение).

расширить( П, л( В, _ ), _, _, да, [В | П] ) :-

 цель( В).

расширить( П, л( В, F/G), Предел, Дер1, ЕстьРеш, Реш) :-

 F <= Предел,

 ( bagof( B1/C, ( после( В, В1, С), not принадлежит( В1, П)),

  Преемники), !,

 преемспис( G, Преемники, ДД),

 опт_f( ДД, F1),

 расширить( П, д( В, F1/G, ДД), Предел, Дер1,

 ЕстьРеш, Реш);

 ЕстьРеш = никогда).   % Нет преемников - тупик

расширить( П, д( В, F/G, [Д | ДД]), Предел, Дер1,

 ЕстьРеш, Реш) :-

 F <= Предел,

 опт_f( ДД, OF), мин( Предел, OF, Предел1),

 расширить( [В | П], Д, Предел1, Д1, ЕстьРеш1, Реш),

 продолжить( П, д( В, F/G, [Д1, ДД]), Предел, Дер1,

 ЕстьРеш1, ЕстьРеш, Реш).

расширить( _, д( _, _, []), _, _, никогда, _ ) :- !.

 % Тупиковое дерево - нет решений

расширить( _, Дер, Предел, Дер, нет, _ ) :-

 f( Дер, F), F > Предел. % Рост остановлен

продолжить( _, _, _, _, да, да, Реш).

продолжить( П, д( В, F/G, [Д1, ДД]), Предел, Дер1,

 ЕстьРеш1, ЕстьРеш, Реш) :-

 ( ЕстьРеш1 = нет, встав( Д1, ДД, НДД);

  ЕстьРеш1 = никогда, НДД = ДД),

 опт_f( НДД, F1),

 расширить( П, д( В, F1/G, НДД), Предел, Дер1,

  ЕстьРеш, Реш).

преемспис( _, [], []).

преемспис( G0, [В/С | ВВ], ДД) :-

 G is G0 + С,

 h( В, H),        % Эвристика h(B)

 F is G + H,

 преемспис( G0, ВВ, ДД1),

 встав( л( В, F/G), ДД1, ДД).

% Вставление дерева Д в список деревьев ДД с сохранением

% упорядоченности по f-оценкам

встав( Д, ДД, [Д | ДД] ) :-

 f( Д, F), опт_f( ДД, F1),

 F =< F1, !.

встав( Д, [Д1 | ДД], [Д1 | ДД1] ) ) :-

 встав( Д, ДД, ДД1).

% Получение f-оценки

f( л( _, F/_ ), F).   % f-оценка листа

f( д( _, F/_, _ ) F).  % f-оценка дерева

опт_f( [Д | _ ], F) :-  % Наилучшая f-оценка для

 f( Д, F).        % списка деревьев

опт_f( [], Fмакс) :-   % Нет деревьев:

 мaкс_f( Fмакс).     % плохая f-оценка

мин( X, Y, X) :-

 X =< Y, !.

мин( X, Y, Y).

Рис. 12.3. Программа поиска с предпочтением.

Аргументы процедуры

расширить

Путь

Дер

Дер

Предел

Дер1

Дер

Предел

Дер1

Предел

ЕстьРеш

Решение

Дер1

Предел

Переменные

Путь

Дер

Предел

расширить

расширить

расширить

ЕстьРеш

(1)

ЕстьРеш = да

Решение

Дер

Предел

Дер1

(2)

ЕстьРеш = нет

Дер1

Дер

Предел

Решение

(3)

ЕстьРеш = никогда

Дер1

Решение

В последнем случае

Дер

Дер

Предел

Некоторые предложения процедуры

расширить

Дер

Дер = д( В, F/G, [Д | ДД ] )

означает следующее. Во-первых, расширению подвергается наиболее перспективное дерево

Д

Предел

Предел1

ДД

продолжить

Рис. 12.4. Отношение

расширить

Дер

Предел

Дер1

Предложение, относящееся к случаю

Дер = л( В, F/G)

порождает всех преемников вершины

В

В

преемспис

Предел

ЕстьРеш

В

Другие отношения:

после( В, В1, С)

В1

В

С

В

В1

h( В, H)

H

В

макс_f( Fмакс)

Fмакс

Рис. 12.5. Связь между g-оценкой вершины В и f- и g-оценками ее "детей" в пространстве состояний.

В следующих разделах мы покажем на примерах, как можно применить нашу программу поиска с предпочтением к конкретным задачам. А сейчас сделаем несколько заключительных замечаний общего характера относительно этой программы. Мы реализовали один из вариантов эвристического алгоритма, известного в литературе как А*-алгоритм (ссылки на литературу см. в конце главы). А*-алгоритм привлек внимание многих исследователей. Здесь мы приведем один важный результат, полученный в результате математического анализа А*-алгоритма:

Этот результат имеет огромное практическое значение. Даже если нам не известно точное значение h*, нам достаточно найти какую-либо нижнюю грань h* и использовать ее в качестве h в А*-алгоритме — оптимальность решения будет гарантирована.

Существует тривиальная нижняя грань, а именно:

h(n) = 0, для всех вершин n пространства состояний.

И при таком значении h допустимость гарантирована. Однако такая оценка не имеет никакой эвристической силы и ничем не помогает поиску. А*-алгоритм при h=0 ведет себя аналогично поиску в ширину. Он, действительно, превращается в поиск в ширину, если, кроме того, положить с(n, n')=1 для всех дуг (n, n') пространства состояний. Отсутствие эвристической силы оценки приводит к большой комбинаторной сложности алгоритма. Поэтому хотелось бы иметь такую оценку h, которая была бы нижней гранью h* (чтобы обеспечить допустимость) и, кроме того, была бы как можно ближе к h* (чтобы обеспечить эффективность). В идеальном случае, если бы нам была известна сама точная оценка h*, мы бы ее и использовали: А*-алгоритм, пользующийся h*, находит оптимальное решение сразу, без единого возврата.

12.1. Определите отношения

после

цель

h

12.2. Поиск c предпочтением применительно к головоломке "игра в восемь"

Если мы хотим применить программу поиска с предпочтением, показанную на рис. 12.3, к какой-нибудь задаче, мы должны добавить к нашей программе отношения, отражающие специфику этой конкретной задачи. Эти отношения определяют саму задачу ("правила игры"), а также вносят в алгоритм эвристическую информацию о методе ее решения. Эвристическая информация задается в форме эвристической функции.

/* Процедуры, отражающие специфику головоломки

"игра в восемь".

Текущая ситуация представлена списком положений фишек;

первый элемент списка соответствует пустой клетке.

Пример:

 ┌───┐

3│123│ Эта позиция представляется так:

2│8 4│ [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2]

1│765│

 └───┘

  123

"Пусто" можно перемещать в любую соседнюю клетку,

т.е. "Пусто" меняется местами со своим соседом.

*/

после( [Пусто | Спис], [Фшк | Спис1], 1) :-

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

 перест( Пусто, Фшк, Спис, Спис1).

 % Переставив Пусто и Фшк, получаем СПИС1

перест( П, Ф, [Ф | С], [П | С] ) :-

 расст( П, Ф, 1).

перест( П, Ф, [Ф1 | С], [Ф1 | C1] ) :-

 перест( П, Ф, С, C1).

расст( X/Y, X1/Y1, P) :-

 % Манхеттеновское расстояние между клетками

 расст1( X, X1, Рx),

 расст1( Y, Y1, Рy),

 P is Рх + Py.

расст1( А, В, P) :-

 P is А-В, P >= 0, ! ;

 P is B-A.

% Эвристическая оценка h равна сумме расстояний фишек

% от их "целевых" клеток плюс "степень упорядоченности",

% умноженная на 3

h( [ Пусто | Спис], H) :-

 цель( [Пусто1 | Цспис] ),

 сумрасст( Спис, ЦСпис, P),

 упоряд( Спис, Уп),

 H is P + 3*Уп.

сумрасст( [], [], 0).

сумрасст( [Ф | С], [Ф1 | C1], P) :-

 расст( Ф, Ф1, P1),

 сумрасст( С, Cl, P2),

 P is P1 + Р2.

упоряд( [Первый | С], Уп) :-

 упоряд( [Первый | С], Первый, Уп).

упоряд( [Ф1, Ф2 | С], Первый, Уп) :-

 очки( Ф1, Ф2, Уп1),

 упоряд( [Ф2 | С], Первый, Уп2),

 Уп is Уп1 + Уп2.

упоряд( [Последний], Первый, Уп) :-

 очки( Последний, Первый, Уп).

очки( 2/2, _, 1) :- !. % Фишка в центре - 1 очко

очки( 1/3, 2/3, 0) :- !.

 % Правильная последовательность - 0 очков

очки( 2/3, 3/3, 0) :- !.

очки( 3/3, 3/2, 0) :- !.

очки( 3/2, 3/1, 0) :- !.

очки( 3/1, 2/1, 0) :- !.

очки( 2/1, 1/1, 0) :- !.

очки( 1/1, 1/2, 0) :- !.

очки( 1/2, 1/3, 0) :- !.

очки( _, _, 2).     % Неправильная последовательность

цель( [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2] ).

% Стартовые позиции для трех головоломок

старт1( [2/2, 1/3, 3/2, 2/3, 3/3, 3/1, 2/1, 1/1, 1/2] ).

 % Требуется для решения 4 шага

старт2( [2/1, 1/2, 1/3, 3/3, 3/2, 3/1, 2/2, 1/1, 2/3] ).

 % 5 шагов

старт3( [2/2, 2/3, 1/3, 3/1, 1/2, 2/1, 3/3, 1/1, 3/2] ).

 % 18 шагов

% Отображение решающего пути в виде списка позиций на доске

показреш( []).

показреш( [ Поз | Спис] :-

 показреш( Спис),

 nl, write( '---'),

 показпоз( Поз).

% Отображение позиции на доске

показпоз( [S0, S1, S2, S3, S4, S5, S6, S7, S8] ) :-

 принадлежит Y, [3, 2, 1] ),   % Порядок Y-координат

 nl, принадлежит X, [1, 2, 3] ), % Порядок X-координат

 принадлежит( Фшк-X/Y,

 [' '-S0, 1-S1, 2-S2, 3-S3, 4-S4, 5-S5, 6-S6, 7-S7, 8-S8]),

 write( Фшк),

 fail. %Возврат с переходом к следующей клетке

показпоз(_).

Рис. 12.6. Процедуры для головоломки "игра в восемь", предназначенные для использования программой поиска с предпочтением рис. 12.3.

Существуют три отношения, отражающих специфику конкретной задачи:

после( Верш, Верш1, Ст)

Это отношение истинно, когда в пространстве состояний существует дуга стоимостью

Ст

Верш

Верш1

цель( Верш)

Это отношение истинно, если

Верш

h( Верш, H)

Здесь

H

Верш

В данном и следующих разделах мы определим эти отношения для двух примеров предметных областей: для головоломки "игра в восемь" (описанной в разделе 11.1) и планирования прохождения задач в многопроцессорной системе.

Отношения для "игры в восемь" показаны на рис. 12.6. Вершина пространства состояний — это некоторая конфигурация из фишек на игровой доске. В программе она задается списком текущих положений фишек. Каждое положение определяется парой координат

X/Y

(1) текущее положение пустой клетки,

(2) текущее положение фишки 1,

(3) текущее положение фишки 2,

…

Целевая ситуация (см. рис. 11.3) определяется при помощи предложения

цель( [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2] ).

Имеется вспомогательное отношение

расст( K1, K2, P)

P — это "манхеттеновское расстояние" между клетками K1 и K2, равное сумме двух расстояний между K1 и K2: расстояния по горизонтали и расстояния по вертикали.

Рис. 12.7. Три стартовых позиции для "игры в восемь": (а) решение требует 4 шага; (b) решение требует 5 шагов; (с) решение требует 18 шагов.

Наша задача — минимизировать длину решения, поэтому мы положим стоимости всех дуг пространства состояний равными 1. В программе рис. 12. 6. даны также определения трех начальных позиций (см. рис. 12.7).

Эвристическая функция h, запрограммирована как отношение

h( Поз, H)

Поз

H

(1)

сумрасст

Поз

сумрасст

(2)

упоряд

упоряд

• фишка в центральной позиции — 1 очко;

• фишка не в центральной позиции, и непосредственно за ней следует (по часовой стрелке) та фишка, какая и должна за ней следовать в целевой позиции — 0 очков.

• то же самое, но за фишкой следует "не та" фишка — 2 очка.

Например, для начальной позиции рис.12.7(а),

упоряд

Эвристическая оценка

H

H = сумрасст + 3 * упоряд

Эта эвристическая функция хорошо работает в том смысле, что она весьма эффективно направляет поиск к цели. Например, при решении головоломок рис. 12.7(а) и (b) первое решение обнаруживается без единого отклонения от кратчайшего решающего пути. Другими словами, кратчайшие решения обнаруживаются сразу, без возвратов. Даже трудная головоломка рис. 12.7 (с) решается почти без возвратов. Но данная эвристическая функция страдает тем недостатком, что она не является допустимой: нет гарантии, что более короткие пути обнаруживаются раньше более длинных. Дело в том, что для функции h условие h ≤ h* выполнено не для всех вершин пространства состояний. Например, для начальной позиции рис. 12.7 (а)

h = 4 + 3 * 6 = 22, h* = 4

С другой стороны, оценка "суммарное расстояние" допустима: для всех позиций

сумрасст

Доказать это неравенство можно при помощи следующего рассуждения: если мы ослабим условия задачи и разрешим фишкам взбираться друг на друга, то каждая фишка сможет добраться до своего целевого положения по траектории, длина которой в точности равна манхеттеновскому расстоянию между ее начальным и целевым положениями. Таким образом, длина оптимального решения упрощенной задачи будет в точности равна

сумрасст

сумрасст

12.2. Введите в программу поиска с предпочтением, приведенную на рис. 12.3, подсчет числа вершин, порожденных в процессе поиска. Один из простых способов это сделать — хранить текущее число вершин в виде факта, устанавливаемого при помощи

assert

retract

assert

12.3. Применение поиска с предпочтением к планированию выполнения задач

Рассмотрим следующую задачу планирования. Дана совокупность задач t₁, t₂, …, имеющих времена выполнения соответственно T1, Т2, …. Все эти задачи нужно решить на m идентичных процессорах. Каждая задача может быть решена на любом процессоре, но в каждый данный момент каждый процессор решает только одну из задач. Между задачами существует отношение предшествования, определяющее, какие задачи (если таковые есть) должны быть завершены, прежде чем данная задача может быть запущена. Необходимо распределить задачи между процессорами без нарушения отношения предшествования, причем таким образом, чтобы вся совокупность задач была решена за минимальное время. Время, когда последняя задача в соответствии с выработанным планом завершает свое решение, называется временем окончания плана. Мы хотим минимизировать время окончания по всем возможным планам.

На рис. 12.8 показан пример задачи планирования, а также приведено два корректных плана, один из которых оптимален. Из примера видно, что оптимальный план обладает одним интересным свойством, а именно в нем может предусматриваться "время простоя" процессоров. В оптимальном плане рис. 12.8 процессор 1, выполнив задачу t, ждет в течение двух квантов времени, несмотря на то, что он мог бы начать выполнение задачи t.

Рис. 12.8. Планирование прохождения задач в многопроцессорной системе для 7 задач и 3 процессоров. Вверху показано предшествование задач и величины продолжительности их решения. Например, задача t₅ требует 20 квантов времени, причем ее выполнение может начаться только после того, как будет завершено решение трех других задач t₁, t₂ и t₃. Показано два корректных плана: оптимальный план с временем окончания 24 и субоптимальный — с временем окончания 33. В данной задаче любой оптимальный план должен содержать время простоя. Coffman/ Denning, Operating Systems Theory, © 1973, p.86. Приведено с разрешения Prentice-Hall, Englewood Cliffs, New Jersey.

Один из способов построить план можно грубо сформулировать так. Начинаем с пустого плана (с незаполненными временными промежутками для каждого процессора) и постепенно включаем в него задачи одну за другой, пока все задачи не будут исчерпаны. Как правило, на каждом шагу мы будем иметь несколько различных возможностей, поскольку окажется, что одновременно несколько задач-кандидатов ждут своего выполнения. Таким образом, для составления плана потребуется перебор. Мы можем сформулировать задачу планирования в терминах пространства состояний следующим образом:

• состояния — это частично составленные планы;

• преемник частичного плана получается включением в план еще одной задачи; другая возможность — оставить процессор, только что закончивший свою задачу, в состоянии простоя;

• стартовая вершина — пустой план;

• любой план, содержащий все задачи, — целевое состояние;

• стоимость решения (подлежащая минимизации) — время окончания целевого плана;

• стоимость перехода от одного частичного плана к другому равна К₂–К₁ где К₁, К₂ — времена окончания этих планов.

Этот грубый сценарий требует некоторых уточнений. Во-первых, мы решим заполнять план в порядке возрастания времен, так что задачи будут включаться в него слева направо. Кроме того, при добавлении каждой задачи следует проверять, выполнены ли ограничения, связанные с отношениями предшествования. Далее, не имеет смысла оставлять процессор бездействующим на неопределенное время, если имеются задачи, ждущие своего запуска. Поэтому мы разрешим процессору простаивать только до того момента, когда какой-нибудь другой процессор завершит выполнение своей задачи. В этот момент мы еще раз вернемся к свободному процессору с тем, чтобы рассмотреть возможность приписывания ему какой-нибудь задачи.

Теперь нам необходимо принять решение относительно представления проблемных ситуаций, т.е. частичных планов. Нам понадобится следующая информация:

(1) список ждущих задач вместе с их временами выполнения;

(2) текущая загрузка процессоров задачами.

Добавим также для удобства программирования

(3) время окончания (частичного) плана, т.е. самое последнее время окончания задачи среди всех задач, приписанных процессорам.

Список ждущих задач вместе с временами их выполнения будем представлять в программе при помощи списка вида

[ Задача1/Т1, Задача2/Т2, ... ]

Текущую загрузку процессоров будем представлять как список решаемых задач, т.е. список пар вида

[ Задача/ВремяОкончания ]

В списке m таких пар, по одной на каждый процессор. Новая задача будет добавляться к плану в момент, когда закончится первая задача из этого списка. В связи с этим мы должны постоянно поддерживать упорядоченность списка загрузки по возрастанию времен окончания. Эти три компоненты частичного плана (ждущие задачи, текущая загрузка и время окончания плана) будут объединены в одно выражение вида

Ждущие * Активные * ВремяОкончания

Кроме этой информации у нас есть ограничения, налагаемые отношениями предшествования, которые в программе будут выражены в форме отношения

предш( ЗадачаX, ЗадачаY)

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

Нашей эвристической функцией будет оптимистическая оценка времени окончания частичного плана с учетом всех ждущих задач. Оптимистическая оценка будет вычисляться в предположении, что два из ограничений, налагаемых на действительно корректный план, ослаблены:

(1) не учитываются отношения предшествования;

(2) делается (не реальное) допущение, что возможно распределенное выполнение задачи одновременно на нескольких процессорах, причем сумма времен выполнения задачи на процессорах равна исходному времени выполнения этой задачи на одном процессоре.

Пусть времена выполнения ждущих задач равны Т₁, Т₂, …, а времена окончания задач, выполняемых на процессорах — К₁, К₂, …. Тогда оптимистическая оценка времени ОбщКон окончания всех активных к настоящему моменту, а также всех ждущих задач имеет вид:

где m — число процессоров. Пусть время окончания текущего частичного плана равно

Тогда эвристическая оценка H (дополнительное время для включения в частичный план ждущих задач) определяется следующим выражением:

if ОбщКон>Кон then H = ОбщКон-Кон else H=0

Программа, содержащая определения отношений, связанных с пространством состояний нашей задачи планирования, приведена полностью на рис. 12.9. Эта программа включает в себя также спецификацию конкретной задачи планирования, показанной на рис. 12.3. Одно из оптимальных решений, полученных в процессе поиска с предпочтением в определенном таким образом пространстве состояний, показано на рис. 12.8.

/* Отношения для задачи планирования.

Вершины пространства состояний - частичные планы,

записываемые как

 [ Задача1/Т1, Задача2/Т2, ...]*

 [ Задача1/К1, Задача2/К2, ...]* ВремяОкончания

В первом списке указываются ждущие задачи и продолжительности их выполнения; во втором - текущие решаемые задачи и их времена окончания, упорядоченные так, чтобы выполнялись неравенства K1≤K2, K2≤K3, ... .

Время окончания плана - самое последнее по времени время окончания задачи.

*/

после( Задачи1*[ _ /К | Акт1]*Кон1,

 Задачи2*Акт2*Кон2, Ст):-

 удалить( Задача/T, Задачи1, Задачи2),

 % Взять ждущую задачу

 not( принадлежит( Здч1/_, Задачи2),

 раньше( ЗДЧ, Задача) ),

 % Проверить предшествование

 not( принадлежит( Здч1/К1, Акт1), К1<К2,

 раньше( К1, Задача) ),   % Активные задачи

 Время is К + T,

 % Время окончания работающей задачи

 встав( ЗадачаВремя, Акт1, Акт2, Кон1, Кон2),

 Ст is Кон2 - Кон1.

после( Задачи*[ _ /К | Акт1]*Кон, Задачи2*Акт2*Кон, 0):-

 вставпростой( К, Акт1, Акт2).

 % Оставить процессор бездействующим

раньше( Задача1, Задача2) :-

  % В соответствии с предшествованием

 предш( Задача1, Задача2).

 % Задача1 раньше, чем Задача2

раньше( Здч1, Здч2) :-

 предш( Здч, Здч2),

 раньше( Здч1, Здч).

встав( Здч/А, [Здч1/В | Спис], [Здч/А, Здч1/В | Спис], К, К):-

  % Список задач упорядочен

 А =< В, !.

встав( Здч/А, [Здч1/В | Спнс], [Здч1/В | Спис1], К1, К2) :-

 встав( Здч/А, Спис, Спис1, Kl, К2).

встав( Здч/А, [ ], [Здч/А], _, А).

вставпростой( А, [Здч/В | Спис], [простой/В, Здч/В | Спис]):-

       % Оставить процессор бездействующим

 А < В, !. % До ближайшего времени окончания

вставпростой( А, [Здч/В | Спис], [Здч/В | Спис1]) :-

 вставпростой( А, Спис, Спис1 ).

удалить( А, [А | Спис], Спис ).

 % Удалить элемент из списка

удалить( А, [В | Спис], [В | Спис1] ):-

 удалить( А, Спис, Спис1 ).

цель( [] *_*_ ). % Целевое состояние: нет ждущих задач

% Эвристическая оценка частичного плана основана на

% оптимистической оценке последнего времени окончания

% этого частичного плана,

% дополненного всеми остальными ждущими задачами.

h( Задачи * Процессоры * Кон, H) :-

 сумвремя( Задачи, СумВремя),

 % Суммарная продолжительность

 % ждущих задач

 всепроц( Процессоры, КонВремя, N),

 % КонВремя - сумма времен окончания

 % для процессоров, N - их количество

 ОбщКон is ( СумВремя + КонВремя)/N,

 ( ОбщКон > Кон, !, H is ОбщКон - Кон; H = 0).

сумвремя( [], 0).

сумвремя( [ _ /T | Задачи], Вр) :-

 сумвремя( Задачи, Вр1),

 Вр is Bp1 + T.

всепроц( [], 0, 0).

всепроц( [ _ /T | СписПроц], КонВр, N) :-

 всепроц( СписПроц, КонВр1, N1),

 N is N1 + 1,

 КонВр is КонВр1 + T.

% Граф предшествования задач

 предш( t1, t4). предш( t1, t5). предш( t2, t4).

 предш( t2, t5). предш( t3, t5). предш( t3, t6).

 предш( t3, t7).

% Стартовая вершина

старт( [t1/4, t2/2, t3/2, t4/20, t5/20, t6/11, t7/11] *

 [простой/0, простой/0, простой/0] * 0 ).

Рис. 12.9. Отношения для задачи планирования. Даны также определения отношений для конкретной задачи планирования с рис. 12.8: граф предшествования и исходный (пустой) план в качестве стартовой вершины.

Вообще говоря, задачи планирования характеризуются значительной комбинаторной сложностью. Наша простая эвристическая функция не обеспечивает высокой эффективности управления поиском. Предложите другие эвристические функции и проведите с ними эксперименты.

Резюме

• Для оценки степени удаленности некоторой вершины пространства состояний от ближайшей целевой вершины можно использовать эвристическую информацию. В этой главе были рассмотрены численные эвристические оценки.

• Эвристический принцип поиска с предпочтением направляет процесс поиска таким образом, что для продолжения поиска всегда выбирается вершина, наиболее перспективная с точки зрения эвристической оценки.

• В этой главе был запрограммирован алгоритм поиска, основанный на указанном принципе и известный в литературе как А*-алгоритм.

• Для того, чтобы решить конкретную задачу при помощи А*-алгоритма, необходимо определить пространство состояний и эвристическую функцию. Для сложных задач наиболее трудным моментом является подбор хорошей эвристической функции.

• Теорема о допустимости помогает установить, всегда ли А*-алгоритм, использующий некоторую конкретную эвристическую функцию, находит оптимальное решение.

Программа поиска с предпочтением, представленная в настоящей главе, — это один из многих вариантов похожих друг на друга программ, из которых А*-алгоритм наиболее популярен. Общее описание А*-алгоритма можно найти в книгах Nillson (1971, 1980) или Winston (1984). Теорема о допустимости впервые доказана авторами статьи Hart, Nilsson, and Raphael (1968). Превосходное и строгое изложение многих разновидностей алгоритмов поиска с предпочтением и связанных с ними математических результатов дано в книге Pearl (1984). В статье Doran and Michie (1966) впервые изложен поиск с предпочтением, управляемый оценкой расстояния до цели.

Головоломка "игра в восемь" использовалась многими исследователями в области искусственного интеллекта в качестве тестовой задачи при изучении эвристических принципов (см., например, Doran and Michie (1966), Michie and Ross (1970) и Gaschnig (1979)).

Задача планирования, рассмотренная в настоящей главе, также как и многие ее разновидности, возникает во многих прикладных областях в ситуации, когда необходимо спланировать обслуживание запросов на ресурсы. Один из примеров — операционные системы вычислительных машин. Задача планирования со ссылкой на это конкретное приложение изложена в книге Coffman and Denning (1973).

Найти хорошую эвристику — дело важное и трудное, поэтому изучение эвристик — одна из центральных тем в искусственном интеллекте. Существуют, однако, некоторые границы, за которые невозможно выйти, двигаясь в направлении улучшения качества эвристик. Казалось бы, все, что необходимо для эффективного решения комбинаторной задачи — это найти мощную эвристику. Однако есть задачи (в том числе многие задачи планирования), для которых не существует универсальной эвристики, обеспечивающей во всех случаях как эффективность, так и допустимость. Многие теоретические результаты, имеющие отношение к этому ограничению, собраны в работе Garey and Johnson (1979).

Coffman E.G. and Denning P.J. (1973). Operating Systems Theory. Prentice-Hall.

Doran J. and Michie D. (1966). Experiments with the graph traverser program. Proc. Royal Socieiy of London 294(A): 235-259.

Garey M. R. and Johnson D. S. (1979). Computers and Intractability. W. H. Freeman. [Имеется перевод: Гэри M., Джонсон Д. С- Вычислительные машины и труднорешаемые задачи. — M.: Мир, 1982.]

Gaschnig J. (1979). Performance measurement and analysis of certain search algorithms. Carnegie-Mellon University: Computer Science Department-Technical Report CMU-CS-79-124 (Ph. D. Thesis).

Hart P.E., Nilsson N.J. and Raphael B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Sciences and Cybernetics SSC-4(2):100-107

Michie D. and Ross R. (1970). Experiments with the adaptive graph traverser. Machine Intelligence 5: 301–308.

Nilsson N.J. (1971). Problem — Solving Methods in Artificial Intelligence. McGraw-Hill. [Имеется перевод: Нильсон H. Искусственный интеллект. Методы поиска решений. — M: Мир, 1973.]

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.

Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. — M.: Мир, 1980.]

Представление в виде И/ИЛИ-графов наиболее хорошо приспособлено для задач, которые естественным образом разбиваются на взаимно независимые подзадачи. Примерами таких задач могут служить поиск маршрута, символическое интегрирование, а также игровые задачи, доказательство теорем и т.п. В этой главе мы разработаем программы для поиска в И/ИЛИ-графах, в том числе программу поиска с предпочтением, управляемого эвристиками.

13.1. Представление задач в виде И/ИЛИ-графов

В главах 11 и 12, говоря о решении задач, мы сконцентрировали свое внимание на пространстве состояний как средстве представления этих задач. В соответствии с таким подходом решение задач сводилось к поиску пути в графе пространства состояний. Однако для некоторых категорий задач представление в форме И/ИЛИ-графа является более естественным. Такое представление основано на разбиении задач на подзадачи. Разбиение на подзадачи дает преимущества в том случае, когда подзадачи взаимно независимы, а, следовательно, и решать их можно независимо друг от друга.

Проиллюстрируем это на примере. Рассмотрим задачу отыскания на карте дорог маршрута между двумя заданными городами, как показано на рис. 13.1. Не будем пока учитывать длину путей. Разумеется, эту задачу можно сформулировать как поиск пути в пространстве состояний. Соответствующее пространство состояний выглядело бы в точности, как карта рис. 13.1: вершины соответствуют городам, дуги — непосредственным связям между городами. Тем не менее давайте построим другое представление, основанное на естественном разбиении этой задачи на подзадачи.

Рис. 13.1. Поиск маршрута из а в z на карте дорог. Через реку можно переправиться в городах f и g. И/ИЛИ-представление этой задачи показано на рис. 13.2.

На карте рис. 13.1 мы видим также реку. Допустим, что переправиться через нее можно только по двум мостам: один расположен в городе f, другой — в городе g. Очевидно, что искомый маршрут обязательно должен проходить через один из мостов, а значит, он должен пройти либо через f, либо через g. Таким образом, мы имеем две главных альтернативы:

Для того, чтобы найти путь из а в z, необходимо найти одно из двух:

(1) путь из а в z, проходящий через f, или

(2) путь из а в z, проходящий через g.

Рис. 13.2. И/ИЛИ-представление задачи поиска маршрута рис. 13.1. Вершины соответствуют задачам или подзадачам, полукруглые дуги означают, что все (точнее, обе) подзадачи должны быть решены.

Теперь каждую из этих двух альтернативных задач можно, в свою очередь, разбить следующим образом:

(1) Для того, чтобы найти путь из a в z через f, необходимо:

1.1 найти путь из а и f и

1.2 найти путь из f в z.

(2) Для того, чтобы найти путь из a в z через g, необходимо:

2.1 найти путь из а в g и

2.2 найти путь из g в z.

Рис. 13.3. (а) Решить P — это значит решить P₁ или Р₂ или … (б) Решить Q — это значит решить все: Q₁ и Q₂ и ….

Итак, мы имеем две главных альтернативы для решения исходной задачи: (1) путь через f или (2) путь через g. Далее, каждую из этих альтернатив можно разбить на подзадачи (1.1 и 1.2 или 2.1 и 2.2 соответственно). Здесь важно то обстоятельство, что каждую из подзадач в обоих альтернативах можно решать независимо от другой. Полученное разбиение исходной задачи можно изобразить в форме И/ИЛИ-графа (рис. 13.2). Обратите внимание на полукруглые дуги, которые указывают на отношение И между соответствующими подзадачами. Граф, показанный на рис. 13.2 — это всего лишь верхняя часть всего И/ИЛИ-дерева. Дальнейшее разбиение подзадач можно было бы строить на основе введения дополнительных промежуточных городов.

Какие вершины И/ИЛИ-графа являются целевыми? Целевые вершины — это тривиальные, или "примитивные" задачи. В нашем примере такой подзадачей можно было бы считать подзадачу "найти путь из а в с", поскольку между городами а и с на карте имеется непосредственная связь.

Рассматривая наш пример, мы ввели ряд важных понятий. И/ИЛИ-граф — это направленный граф, вершины которого соответствуют задачам, а дуги — отношениям между задачами. Между дугами также существуют свои отношения. Это отношения И и ИЛИ, в зависимости от того, должны ли мы решить только одну из задач-преемников или же несколько из них (см. рис. 13.3). В принципе из вершины могут выходить дуги, находящиеся в отношении И вместе с дугами, находящимися в отношении ИЛИ. Тем не менее, мы будем предполагать, что каждая вершина имеет либо только И-преемников, либо только ИЛИ-преемников; дело в том, что в такую форму можно преобразовать любой И/ИЛИ граф, вводя в него при необходимости вспомогательные ИЛИ-вершины. Вершину, из которой выходят только И-дуги, называют И-вершиной; вершину, из которой выходят только ИЛИ-дуги, — ИЛИ-вершиной.

Когда задача представлялась в форме пространства состояний, ее решением был путь в этом пространстве. Что является решением в случае И/ИЛИ-представления? Решение должно, конечно, включать в себя все подзадачи И-вершины. Следовательно, это уже не путь, а дерево. Такое решающее дерево T определяется следующим образом:

• исходная задача P — это корень дерева T;

• если P является ИЛИ-вершиной, то в T содержится только один из ее преемников (из И/ИЛИ-графа) вместе со своим собственным решающим деревом;

• если P — это И-вершина, то все ее преемники (из И/ИЛИ-графа) вместе со своими решающими деревьями содержатся в T.

Рис. 13.4. (а) Пример И/ИЛИ-графа: d, g и h — целевые вершины; a — исходная задача. (b) и (с) Два решающих дерева, стоимости которых равны 9 и 8 соответственно. Здесь стоимость решающего дерева определена как сумма стоимостей всех входящих в него дуг.

Иллюстрацией к этому определению может служить рис. 13.4. Используя стоимости, мы можем формулировать критерии оптимальности решения. Например, можно определить стоимость решающего графа как сумму стоимостей всех входящих в него дуг. Тогда, поскольку обычно мы заинтересованы в минимизации стоимости, мы отдадим предпочтение решающему графу, изображенному на рис. 13.4(с).

Однако мы не обязательно должны измерять степень оптимальности решения, базируясь на стоимостях дуг. Иногда более естественным окажется приписывать стоимость не дугам, а вершинам, или же и тем, и другим одновременно.

Подведем итоги:

• И/ИЛИ-представление основано на философии сведения задач к подзадачам.

• Вершины И/ИЛИ-графа соответствуют задачам; связи между вершинами — отношениям между задачами.

• Вершина, из которой выходят ИЛИ-связи, называется ИЛИ-вершиной. Для того, чтобы решить соответствующую задачу, нужно решить одну из ее задач-преемников.

• Вершина, из которой выходят И-связи, называется И-вершиной. Для того, чтобы решить соответствующую задачу, нужно решить все ее задачи-преемники.

• При заданном И/ИЛИ-графе конкретная задача специфицируется заданием

стартовой вершины и

целевого условия для распознавания

целевых вершин.

• Целевые вершины (или "терминальные вершины") соответствуют тривиальным (или "примитивным") задачам.

• Решение представляется в виде решающего графа — подграфа всего И/ИЛИ-графа.

• Представление задач в форме пространства состояний можно рассматривать как специальный частный случай И/ИЛИ-представления, когда все вершины И/ИЛИ-графа являются ИЛИ-вершинами.

• И/ИЛИ-представление имеет преимущество в том случае, когда вершинами, находящимися в отношении И, представлены подзадачи, которые можно решать независимо друг от друга. Критерий независимости можно несколько ослабить, а именно потребовать, чтобы существовал такой порядок решения И-задач, при котором решение более "ранних" подзадач не разрушалось бы при решении более "поздних" под задач.

• Дугам или вершинам, или и тем, и другим можно приписать стоимости с целью получить возможность сформулировать критерий оптимальности решения.

13.2. Примеры И/ИЛИ-представления задач

13.2.1. И/ИЛИ-представление задачи поиска маршрута

Для задачи отыскания кратчайшего маршрута (рис. 13.1) И/ИЛИ-граф вместе с функцией стоимости можно определить следующим образом:

• ИЛИ-вершины представляются в форме X-Z, что означает: найти кратчайший путь из X в Z.

• И-вершины имеют вид

X-Z через Y

что означает: найти кратчайший путь из X в Z, проходящий через Y.

• Вершина X-Z является целевой вершиной (примитивной задачей), если на карте существует непосредственная связь между X и Z.

• Стоимость каждой целевой вершины X-Z равна расстоянию, которое необходимо преодолеть по дороге, соединяющей X с Z.

• Стоимость всех остальных (нетерминальных) вершин равна 0.

Стоимость решающего графа равна сумме стоимостей всех его вершин (в нашем случае это просто сумма стоимостей всех терминальных вершин). В задаче рис. 13.1 стартовая вершина — это а-z. На рис. 13.5 показан решающий граф, имеющий стоимость 9. Это дерево соответствует пути

[a, b, d, f, i, z]

, который можно построить, если пройти по всем листьям решающего дерева слева направо.

Рис. 13.5. Решающее дерево минимальной стоимости для задачи поиска маршрута рис. 13.1, сформулированной в терминах И/ИЛИ-графа.

13.2.2. Задача о ханойской башне

Задача о ханойской башне (рис. 13.6) — это еще один классический пример эффективного применения метода разбиения задачи на подзадачи и построения И / ИЛИ-графа. Для простоты мы рассмотрим упрощенную версию этой задачи, когда в ней участвует только три диска:

Имеется три колышка 1, 2 и 3 и три диска а, b и с (а — наименьший из них, а с — наибольший). Первоначально все диски находятся на колышке 1. Задача состоит в том, чтобы переложить все диски на колышек 3. На каждом шагу можно перекладывать только один диск, причем никогда нельзя помещать больший диск на меньший.

Эту задачу можно рассматривать как задачу достижения следующих трех целей:

(1) Диск а — на колышек 3.

(2) Диск b — на колышек 3.

(3) Диск с — на колышек 3.

Беда в том, что эти цели не независимы. Например, можно сразу переложить диск а на колышек 3, и первая цель будет достигнута. Но тогда две другие цели станут недостижимыми (если только мы не отменим первое наше действие). К счастью, существует такой удобный порядок достижения этих целей, из которого можно легко вывести искомое решение.

Рис. 13.6. Задача о ханойской башне

Порядок этот можно установить при помощи следующего рассуждения: самая трудная цель — это цель 3 (диск с — на колышек 3), потому что на диск c наложено больше всего ограничений. В подобных ситуациях часто срабатывает хорошая идея: пытаться достичь первой самую трудную цель. Этот принцип основан на следующей логике: поскольку другие цели достигнуть легче (на них меньше ограничений), можно надеяться на то, что их достижение возможно без отмены действий на достижение самой трудной цели.

Применительно к нашей задаче это означает, что необходимо придерживаться следующей стратегии:

Первой достигнуть цель "диск с — на колышек 3", а затем — все остальные.

Но первая цель не может быть достигнута сразу, так как в начальной ситуации диск с двигать нельзя. Следовательно, сначала мы должны подготовить этот ход, и наша стратегия принимает такой вид

(1) Обеспечить возможность перемещения диска с с 1 на 3.

(2) Переложить с с 1 на 3.

(3) Достигнуть остальные цели (а на 3 и b на 3).

Переложить c с 1 на 3 возможно только в том случае, если диск а и b оба надеты на колышек 2. Таким образом наша исходная задача перемещения а, b и с с 1 на 3 сводится к следующим трем подзадачам:

Для того, чтобы переложить a, b и с с 1 на 3, необходимо

(1) переложить а и b с 1 на 2, и

(2) переложить с с 1 на 3, и

(3) переложить а и b с 2 на 3.

Задача 2 тривиальна (она решается за один шаг). Остальные две подзадачи можно решать независимо от задачи 2, так как диски а и b можно двигать, не обращая внимание на положение диска с. Для решения задач 1 и 3 можно применить тот же самый принцип разбиения (на этот раз диск b будет самым "трудным"). В соответствии с этим принципом задача 1 сводится к трем тривиальным подзадачам:

Для того, чтобы переложить а и b с 1 на 2, необходимо:

(1) переложить а с 1 на 3, и

(2) переложить b с 1 на 2, и

(3) переложить а с 3 на 2.

13.2.3. Формулировка игровых задач в терминах И/ИЛИ-графов

Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И/ИЛИ-графами. Игры такого рода называются играми двух лиц с полной информацией. Будем считать, что существует только два возможных исхода игры: ВЫИГРЫШ и ПРОИГРЫШ. (Об играх с тремя возможными исходами — ВЫИГРЫШ, ПРОИГРЫШ и НИЧЬЯ, можно также говорить, что они имеют только два исхода: ВЫИГРЫШ и НЕВЫИГРЫШ). Так как участники игры ходят по очереди, мы имеем два вида позиций, в зависимости от того, чей ход. Давайте условимся называть участников игры "игрок" и "противник", тогда мы будем иметь следующие два вида позиций: позиция с ходом игрока ("позиция игрока") и позиция с ходом противника ("позиция противника"). Допустим также, что начальная позиция P — это позиция игрока. Каждый вариант хода игрока в этой позиции приводит к одной из позиций противника Q₁, Q₂, Q₃, … (см. рис. 13.7). Далее каждый вариант хода противника в позиции Q₁ приводит к одной из позиций игрока R₁₁, R₁₂, …. В И/ИЛИ-дереве, показанном на рис. 13.7, вершины соответствуют позициям, а дуги — возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Для того, чтобы выиграть в позиции P, нужно найти ход, переводящий P в выигранную позицию Q_i. (при некотором i). Таким образом, игрок выигрывает в позиции P, если он выигрывает в Q₁, или Q₂, или Q₃, или …. Следовательно, P — это ИЛИ-вершина. Для любого i позиция Q_i — это позиция противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого варианта хода противника. Другими словами, игрок выигрывает в Q_i, если он выигрывает во всех позициях R_i1 и R_i2 и …. Таким образом, все позиции противника — это И-вершины. Целевые вершины — это позиции, выигранные согласно правилам игры, например позиции, в которых король противника получает мат. Позициям проигранным соответствуют задачи, не имеющие решения. Для того, чтобы решить игровую задачу, мы должны построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе.

Рис. 13.7. Формулировка игровой задачи для игры двух лиц в форме И/ИЛИ-дерева; участники игры: "игрок" и "противник".

13.3. Базовые процедуры поиска в И/ИЛИ-графах

В этом разделе нас будет интересовать какое-нибудь решение задачи независимо от его стоимости, поэтому проигнорируем пока стоимости связей или вершин И/ИЛИ-графа. Простейший способ организовать поиск в И/ИЛИ-графах средствами Пролога — это использовать переборный механизм, заложенный в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурный смысл Пролога это и есть не что иное, как поиск в И/ИЛИ-графе. Например, И/ИЛИ-граф рис. 13.4 (без учета стоимостей дуг) можно описать при помощи следующих предложений:

а :- b.  % а - ИЛИ-вершина с двумя преемниками

а :- с.  % b и  с

b :- d, e. % b - И-вершина с двумя преемниками d и e

с :- h.

с :- f, g.

f :- h, i.

d. g. h.  % d, g и h - целевые вершины

Для того, чтобы узнать, имеет ли эта задача решение, нужно просто спросить:

?- а.

Получив этот вопрос, пролог-система произведет поиск в глубину в дереве рис. 13.4 и после того, как пройдет через все вершины подграфа, соответствующего решающему дереву рис. 13.4(b), ответит "да".

Преимущество такого метода программирования И/ИЛИ-поиска состоит в его простоте. Но есть и недостатки:

• Мы получаем ответ "да" или "нет", но не получаем решающее дерево. Можно было бы восстановить решающее дерево при помощи трассировки программы, но такой способ неудобен, да его и недостаточно, если мы хотим иметь возможность явно обратиться к решающему дереву как к объекту программы.

• В эту программу трудно вносить добавления, связанные с обработкой стоимостей.

• Если наш И/ИЛИ-граф — это граф общего вида, содержащий циклы, то пролог-система, следуя стратегии в глубину, может войти в бесконечный рекурсивный цикл.

Попробуем постепенно исправить эти недостатки. Сначала определим нашу собственную процедуру поиска в глубину для И/ИЛИ-графов.

Прежде всего мы должны изменить представление И/ИЛИ-графов. С этой целью введём бинарное отношение, изображаемое инфиксным оператором '

--->

а ---> или : [b, с].

Оба символа '

--->

:

:- op( 600, xfx, --->).

:- op( 500, xfx, :).

Весь И/ИЛИ-граф рис. 13.4 теперь можно задать при помощи множества предложений

а ---> или : [b, с].

b ---> и : [d, e].

с ---> и : [f, g].

e ---> или : [h].

f ---> или : [h, i].

цель( d). цель( g). цель( h).

Процедуру поиска в глубину в И/ИЛИ-графах можно построить, базируясь на следующих принципах:

Для того, чтобы решить задачу вершины В, необходимо придерживаться приведенных ниже правил:

(1) Если В — целевая вершина, то задача решается тривиальным образом.

(2) Если вершина В имеет ИЛИ-преемников, то нужно решить одну из соответствующих задач-преемников (пробовать решать их одну за другой, пока не будет найдена задача, имеющая решение).

(3) Если вершина В имеет И-преемников, то нужно решить все соответствующие задачи (пробовать решать их одну за другой, пока они не будут решены все).

Если применение этих правил не приводит к решению, считать, что задача не может быть решена.

Соответствующая программа выглядит так:

решить( Верш) :-

 цель( Верш).

решить( Верш) :-

 Верш ---> или : Вершины, % Верш - ИЛИ-вершина

 принадлежит( Верш1, Вершины),

 % Выбор преемника  Верш1  вершины  Верш

 решить( Bepш1).

решить( Верш) :-

 Верш ---> и : Вершины,  % Верш - И-вершина

 решитьвсе( Вершины).

 % Решить все задачи-преемники

решитьвсе( []).

решитьвсе( [Верш | Вершины]) :-

 решить( Верш),

 решитьвсе( Вершины).

Здесь

принадлежит

Эта программа все еще имеет недостатки:

• она не порождает решающее дерево, и

• она может зацикливаться, если И/ИЛИ-граф имеет соответствующую структуру (циклы).

Программу нетрудно изменить с тем, чтобы она порождала решающее дерево. Необходимо так подправить отношение

решить

решить( Верш, РешДер).

Решающее дерево представим следующим образом. Мы имеем три случая:

(1) Если

Верш

(2) Если

Верш

Верш ---> Поддерево

где

Поддерево

Верш

(3) Если

Верш

Верш ---> и : Поддеревья

где

Поддеревья

Верш

% Поиск в глубину для И/ИЛИ-графов

% Процедура решить( Верш, РешДер) находит решающее дерево для

% некоторой вершины в И / ИЛИ-графе

решить( Верш, Верш) :-  % Решающее дерево для целевой

 цель( Верш).       % вершины - это сама вершина

решить( Верш, Верш ---> Дер) :-

 Верш ---> или : Вершины, % Верш - ИЛИ-вершина

 принадлежит( Верш1, Вершины),

 % Выбор преемника  Верш1  вершины  Верш

 решить( Bepш1, Дер).

решить( Верш, Верш ---> и : Деревья) :-

 Верш ---> и : Вершины,  % Верш - И-вершина

 решитьвсе( Вершины, Деревья).

 % Решить все задачи-преемники

решитьвсе( [], []).

решитьвсе( [Верш | Вершины], [Дер | Деревья]) :-

 решить( Верш, Дер),

 решитьвсе( Вершины, Деревья).

отобр( Дер) :-      % Отобразить решающее дерево

 отобр( Дер, 0), !.    % с отступом 0

отобр( Верш ---> Дер, H) :-

 % Отобразить решающее дерево с отступом H

 write( Верш), write( '--->'),

 H1 is H + 7,

 отобр( Дер, H1), !.

отобр( и : [Д], H) :-

 % Отобразить И-список решающих деревьев

 отобр( Д, H).

отобр( и : [Д | ДД], H) :-

 % Отобразить И-список решающих деревьев

 отобр( Д, H),

 tab( H),

 отобр( и : ДД, H), !.

отобр( Верш, H) :-

 write( Верш), nl.

Рис. 13.8. Поиск в глубину для И/ИЛИ-графов. Эта программа может зацикливаться. Процедура

решить

отобр

отобр 

Например, при поиске в И/ИЛИ-графе рис. 13.4 первое найденное решение задачи, соответствующей самой верхней вершине а, будет иметь следующее представление:

а ---> b ---> и : [d, c ---> h]

Три формы представления решающего дерева соответствуют трем предложениям отношения

решить

решить

отобр

отобр

а ---> b ---> d

        e ---> h

Программа рис. 13.8 все еще сохраняет склонность к вхождению в бесконечные циклы. Один из простых способов избежать бесконечных циклов — это следить за текущей глубиной поиска и не давать программе заходить за пределы некоторого ограничения по глубине. Это можно сделать, введя в отношение

решить

решить( Верш, РешДер, МаксГлуб)

Как и раньше, вершиной

Верш

РешДер

МаксГлуб

МаксГлуб

МаксГлуб

МаксГлуб

Верш

МаксГлуб

решить( Верш, Верш ---> Дер, МаксГлуб) :-

 МаксГлуб > 0,

 Верш ---> или : Вершины, % Верш - ИЛИ-вершина

 принадлежит ( Верш1, Вершины),

 % Выбор преемника  Верш1  вершины  Верш

 Глуб1 is МаксГлуб - 1,  % Новый предел по глубине

 решить( Bepш1, Дер, Глуб1).

 % Решить задачу-преемник с меньшим ограничением

Нашу процедуру поиска в глубину с ограничением можно также использовать для имитации поиска в ширину. Идея состоит в следующем: многократно повторять поиск в глубину каждый раз все с большим значением ограничения до тех пор, пока решение не будет найдено, То есть попробовать решить задачу с ограничением по глубине, равным 0, затем — с ограничением 1, затем — 2 и т.д. Получаем следующую программу:

имитация_в_ширину( Верш, РешДер) :-

 проба_в_глубину( Верш, РешДер, 0).

  % Проба поиска с возрастающим ограничением, начиная с 0

проба_в_глубину( Верш, РешДер, Глуб) :-

 решить( Верш, РешДер, Глуб);

 Глуб1 is Глуб + 1, % Новый предел по глубине

 проба_в_глубину( Верш, РешДер, Глуб1).

 % Попытка с новым ограничением

Недостатком имитации поиска в ширину является то, что при каждом увеличении предела по глубине программа повторно просматривает верхнюю область пространства поиска.

13.1. Закончите составление программы поиска в глубину (с ограничением) для И/ИЛИ-графов, намеченную в настоящем разделе.

13.2. Определите на Прологе И/ИЛИ-пространство для задачи "ханойская башня" и примените к нему процедуры поиска настоящего раздела.

13.3. Рассмотрите какую-нибудь простую детерминированную игру двух лиц с полной информацией и дайте определение ее И/ИЛИ-представления. Используйте программу поиска в И/ИЛИ-графах для построения выигрывающих стратегий в форме И/ИЛИ-деревьев.

13.4. Поиск с предпочтением в И/ИЛИ-графах

13.4.1. Эвристические оценки и алгоритм поиска

Базовые процедуры поиска предыдущего раздела производят систематический и полный просмотр И/ИЛИ-дерева, не руководствуясь при этом какими-либо эвристиками. Для сложных задач подобные процедуры весьма не эффективны из-за большой комбинаторной сложности пространства поиска. В связи с этим возникает необходимость в эвристическом управлении поиском, направленном на уменьшение комбинаторной сложности за счет исключения бесполезных альтернатив. Управление эвристиками, излагаемое в настоящем разделе, будет основано на численных эвристических оценках "трудности" задач, входящих в состав И/ИЛИ-графа. Программу, которую мы составим, можно рассматривать как обобщение программы поиска с предпочтением в пространстве состояний гл. 12.

Начнем с того, что сформулируем критерий оптимальности, основанный на стоимостях дуг И/ИЛИ-графа. Во-первых, мы расширим наше представление И/ИЛИ-графов, дополнив его стоимостями дуг. Например, И/ИЛИ-граф рис. 13.4 можно представить следующими предложениями:

а ---> или : [b/1, с/3].

b ---> и : [d/1, e/1].

с ---> и : [f/2, g/1].

e ---> или : [h/6].

f ---> или : [h/2, i/3].

цель( d). цель( g). цель( h).

Стоимость решающего дерева мы определим как сумму стоимостей его дуг. Цель оптимизации - найти решающее дерево минимальной стоимости. Как и раньше, иллюстрацией служит рис. 13.4.

Будет полезным определить стоимость вершины И/ИЛИ-графа как стоимость оптимального решающего дерева для этой вершины. Стоимость вершины, определенная таким образом, соответствует "трудности" соответствующей задачи.

Мы будем предполагать, что стоимости вершин И/ИЛИ-графа можно оценить (не зная соответствующих решающих деревьев) при помощи эвристической функции h. Эти оценки будут использоваться для управления поиском. Наша программа поиска начнет свою работу со стартовой вершины и, распространяя поиск из уже просмотренных вершин на их преемников, будет постепенно наращивать дерево поиска. Этот процесс будет строить дерево даже в том случае, когда сам И/ИЛИ-граф не является деревом; при этом граф будет разворачиваться в дерево за счет дублирования своих отдельных частей.

Для продолжения поиска будет всегда выбираться "наиболее перспективное" решающее дерево-кандидат. Каким же образом используется функция h для оценки степени перспективности решающего дерева-кандидата или, точнее, вершины-кандидата — корня этого дерева?

Рис. 13.9. Получение оценки H трудности задач И/ИЛИ-графа.

Обозначим через H(В) оценку трудности вершины В. Для самой верхней вершины текущего дерева поиска H(В) просто совпадает с h(В). С другой стороны, для оценки внутренней вершины дерева поиска нам не обязательно использовать непосредственно значение h, поскольку у нас есть некоторая дополнительная информация об этой вершине: мы знаем ее преемников. Следовательно, как показано на рис. 13.9, мы можем приближенно оценить трудность внутренней ИЛИ-вершины как

где с(В, В_i) — стоимость дуги, ведущей из В в В_i. Взятие минимума в этой формуле оправдано тем обстоятельством, что для того, чтобы решить задачу В, нам нужно решить только одну из ее задач-преемников. Трудность И-вершины В можно приближенно оценить так:

Будем называть H-оценку внутренней вершины "возвращенной" (backed-up) оценкой.

Более практичной с точки зрения использования в нашей программе поиска является другая величина F, которую можно определить в терминах H следующим образом. Пусть В1 — вершина-предшественник вершины В в дереве поиска, причем стоимость дуги, ведущей из В1 в В, равна с(В1, В), тогда положим

F( B) = с( В1, В) + H( В)

Пусть В1 — родительская вершина вершины В, а В₁, В₂, … — ее дочерние вершины, тогда, в соответствии с определениями F и H, имеем

, если В — ИЛИ-вершина

, если В — И-вершина

Хотя стартовая вершина А и не имеет предшественника, будем считать, что стоимость ведущей в нее (виртуальной) дуги равна 0. Если положить h равным 0 для всех вершин И/ИЛИ-дерева, то для любого найденного оптимального решающего дерева окажется, что его стоимость, т.е. сумма стоимостей его дуг, в точности равна F(A).

На любой стадии поиска каждый преемник ИЛИ-вершины соответствует некоторому альтернативному решающему дереву-кандидату. Процесс поиска всегда принимает решение продолжать просмотр того дерева-кандидата, для которого F-оценка минимальна. Вернемся еще раз к рис. 13.4 и посмотрим, как будет вести себя процесс, поиска на примере И/ИЛИ-графа, изображенного на этом рисунке. В начале дерево поиска состоит всего из одной вершины — стартовой вершины а, далее дерево постепенно "растет" до тех пор, пока не будет найдено решающее дерево. На рис. 13.10, показан ряд "мгновенных снимков", сделанных в процессе роста дерева поиска. Для простоты мы предположим, что h = 0 для всех вершин. Числа, приписанные вершинам на рис. 13.10 — это их F-оценки (разумеется, по мере накопления информации в процессе поиска они изменяются). Ниже даются некоторые пояснительные замечания к рис. 13.10.

После распространения поиска из первоначального дерева (снимок А) получается дерево В. Вершина а — это ИЛИ-вершина, поэтому мы имеем два решающих дерева-кандидата: b и с. Поскольку F( b) = 1 < 3 = F( c), для продолжения поиска выбирается альтернатива b. Насколько далеко может зайти процесс роста поддерева b? Этот процесс может продолжаться до тех пор, пока не произойдет одно из двух событий:

(1) F-оценка вершины b станет больше, чем F-оценка ее конкурента с, или

(2) обнаружится, что найдено решающее дерево.

В связи с этим, начиная просмотр поддерева-кандидата b, мы устанавливаем верхнюю границу для F( b): F( b) ≤ 3 = F( c). Сначала порождаются преемники d и e вершины b (снимок С),после чего F-оценка b возрастает до 3. Так как это значение не превосходит верхнюю границу, рост дерева-кандидата с корнем в b продолжается. Вершина d оказывается целевой вершиной, а после распространения поиска из вершины e на один шаг получаем дерево, показанное на снимке D. В этот момент выясняется, что F( b) = 9 > 3, и рост дерева b прекращается. В результате процесс поиска не успевает "осознать", что h — это тоже целевая вершина и что порождено решающее дерево. Вместо этого происходит переключение активности на конкурирующую альтернативу с. Поскольку в этот момент F( b) = 9, устанавливается верхняя граница для F( c), равная 9. Дерево-кандидат с корнем с наращивается (с учетом установленного ограничения) до тех пор, пока не возникает ситуация, показанная на снимке E. Теперь процесс поиска обнаруживает, что найдено решающее дерево (включающее в себя целевые вершины h и g), на чем поиск заканчивается. Заметьте, что в качестве результата процесс поиска выдает наиболее дешевое из двух возможных решающих деревьев, а именно решающее дерево рис. 13.4(с).

Рис. 13.10. Трассировка процесса поиска с предпочтением в И/ИЛИ-графе (h = 0) при решении задачи рис. 13.4.

13.4.2. Программа поиска

Программа, в которой реализованы идеи предыдущего раздела, показана на рис. 13.12. Прежде, чем мы перейдем к объяснению отдельных деталей этой программы, давайте рассмотрим тот способ представления дерева поиска, который в ней используется.

Существует несколько случаев, как показано на рис. 13.11. Различные формы представления поискового дерева возникают как комбинации следующих возможных вариантов, относящихся к размеру дерева и к его "решающему статусу".

• Размер:

(1) дерево состоит из одной вершины (листа) или

(2) оно имеет корень и (непустые) поддеревья.

• Решающий статус:

(1) обнаружено, что дерево соответствует решению задачи (т.е. является решающим деревом) или

(2) оно все еще решающее дерево-кандидат.

Рис. 13.11. Представление дерева поиска.

Основной функтор, используемый для представления дерева, указывает, какая из комбинаций этих воз-можностей имеется в виду. Это может быть одна из следующих комбинаций:

лист  решлист дер решдер

Далее, в представление дерева входят все или некоторые из следующих объектов:

• корневая вершина дерева,

• F-оценка дерева,

• стоимость С дуги И/ИЛИ-графа, ведущей в корень дерева,

• список поддеревьев,

• отношение (И или ИЛИ) между поддеревьями.

Список поддеревьев всегда упорядочен по возрастанию F-оценок. Поддеревья, являющиеся решающими деревьями, помещаются в конец списка.

Обратимся теперь к программе рис. 13.12. Отношение самого высокого уровня — это

и_или( Верш, РешДер)

где

Верш

— стартовая вершина. Программа строит решающее дерево (если таковое существует), рассчитывая на то, что оно окажется оптимальным решением. Будет ли это решение в действительности самым дешевым, зависит от той функции h, которую использует алгоритм. Существует теорема, в которой говорится о том, как оптимальность решения зависит от h. Эта теорема аналогична теореме о допустимости алгоритма поиска с предпочтением в пространстве состояний (гл. 12). Обозначим через С( В) стоимость оптимального решающего дерева для вершины В. Если для каждой вершины В И/ИЛИ-графа эвристическая оценка h(B)≤C(B), то гарантируется, что процедура

и_или

найдет оптимальное решение. Если же h не удовлетворяет этому условию, то найденное решение может оказаться субоптимальным. Существует тривиальная эвристическая функция, удовлетворяющая условию оптимальности, а именно h = 0 для всех вершин. Ее недостатком является отсутствие эвристической силы.

Основную роль в программе рис. 13.12 играет отношение

расширить( Дер, Предел, Дер1, ЕстьРеш)

Дер

и

Предел

— его "входные" аргументы, а

Дер1

и

ЕстьРеш

— "выходные". Аргументы имеют следующий смысл:

Дер

— дерево поиска, подлежащее расширению.

Предел

— предельное значение F-оценки, при котором еще разрешено наращивать дерево

Дер

.

ЕстьРеш

— индикатор, значения которого указывают на то, какой из следующих трех случаев имеет место:

(1)

ЕстьРеш = да

:

Дер

можно "нарастить" (с учетом ограничения

Предел

) таким образом, чтобы образовалось решающее дерево

Дер1

.

(2)

ЕстьРеш = нет

: дерево

Дер

можно расширить до состояния

Дер1

, для которого F-оценка превосходит

Предел

, но прежде чем F-оценка превзошла

Предел

, решающее дерево не было обнаружено.

(3)

ЕстьРеш = никогда

:

Дер

не содержит решения.

В зависимости от случая

Дер1

— это либо решающее дерево, либо

Дер

, расширенное до момента перехода через

Предел

; если

ЕстьРеш = никогда

, то переменная

Дер1

неинициализирована.

Процедура

расширспис( Деревья, Предел, Деревья1, ЕстьРеш)

аналогична процедуре

расширить

. Так же, как и в процедуре

расширить

,

Предел

задает ограничение на рост дерева, а

ЕстьРеш

— это индикатор, указывающий, каков результат расширения ("да", "нет" или "никогда"). Первый аргумент — это, на этот раз, список деревьев (И-список или ИЛИ-список):

Деревья = или:[Д1, Д2, ...]

или

Деревья = и : [Д1, Д2, ...]

Процедура

расширспис

выбирает из списка

Деревья

наиболее перспективное дерево (исходя из F-оценок). Так как деревья в списке упорядочены, таким деревом является первый элемент списка. Наиболее перспективное дерево подвергается расширению с новым ограничением

Предел1

. Значение

Предел1

зависит от

Предел

, а также от других деревьев списка. Если

Деревья

— это ИЛИ-список, то

Предел1

устанавливается как наименьшая из двух величин:

Предел

и F-оценка следующего по "качеству" дерева из списка

Деревья

. Если

Деревья

— это И-дерево, то

Предел1

устанавливается равным

Предел

минус сумма F-оценок всех остальных деревьев из списка. Значение переменной

Деревья1

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

ЕстьРеш

. Если

ЕстьРеш = нет

, то

Деревья1

— это то же самое, что и список

Деревья

, причем наиболее перспективное дерево расширено с учетом ограничения

Предел1

. Если

ЕстьРеш = да

, то

Деревья1

— это решение для всего списка

Деревья

(найденное без выхода за границы значения

Предел

). Если

ЕстьРеш = никогда

, то переменная

Деревья1

неинициализирована.

Процедура

продолжить

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

расширить

. Эта процедура либо строит решающее дерево, либо уточняет дерево поиска и продолжает процесс его наращивания, либо выдает сообщение "никогда" в случае, когда было обнаружено, что список деревьев не содержит решения.

/* ПРОГРАММА И/ИЛИ-ПОИСКА С ПРЕДПОЧТЕНИЕМ

Эта программа порождает только одно решение. Гарантируется, что это решение самое дешевое при условии, что используемая эвристическая функция является нижней гранью реальной стоимости решающих деревьев.

Дерево поиска имеет одну из следующих форм:

дер( Верш, F, С, Поддеревья) дерево-кандидат

лист( Верш, F, C)      лист дерева поиска

решдер( Верш, F, Поддеревья) решающее дерево

решлист( Верш, F)      лист решающего дерева

С - стоимость дуги, ведущей в Верш

F = С + H, где H - эвристическая оценка оптимального решающего дерева с корнем Верш

Список Поддеревья упорядочен таким образом, что

(1) решающие поддеревья находятся в конце списка;

(2) остальные поддеревья расположены в порядке возрастания F-оценок

*/

:- op( 500, xfx, :).

:- op( 600, xfx, --->).

и_или( Верш, РешДер) :-

 расширить( лист( Верш, 0, 0), 9999, РешДер, да).

 % Предполагается, что 9999  >  любой F-оценки

% Процедура расширить( Дер, Предел, НовДер, ЕстьРеш)

% расширяет Дер в пределах ограничения Предел

% и порождает НовДер с "решающим статусом" ЕстьРеш.

% Случай 1:  выход за ограничение

расширить( Дер, Предел, Дер, нет) :-

 f( Дер, F),  F > Предел, !. % Выход за ограничение

% В остальных случаях F ≤ Предел

% Случай 2:  встретилась целевая вершина

расширить( лист( Верш, F, С), _, решлист( Верш, F), да) : -

 цель( Верш), !.

% Случай 3:  порождение преемников листа

расширить( лист( Верш, F,C), Предел, НовДер, ЕстьРеш) :-

 расшлист( Верш, С, Дер1), !,

 расширить( Дер1, Предел, НовДер, ЕстьРеш);

 ЕстьРеш = никогда, !.    % Нет преемников, тупик

% Случай 4:  расширить дерево

расширить( дер( Верш, F, С, Поддеревья),

 Предел, НовДер, ЕстьРеш) :-

 Предел1 is Предел - С,

 расширспис( Поддеревья, Предел1, НовПоддер, ЕстьРеш1),

 продолжить( ЕстьРеш1, Верш, С, НовПоддер, Предел,

 НовДер, ЕстьРеш).

% расширспис( Деревья, Предел, Деревья1, ЕстьРеш)

% расширяет деревья из заданного списка с учетом

% ограничения Предел и выдает новый список Деревья1

% с "решающим статусом" ЕстьРеш.

расширспис( Деревья, Предел, Деревья1, ЕстьРеш) :-

 выбор( Деревья, Дер, ОстДер, Предел, Предел1),

 расширить( Дер, Предел1, НовДер, ЕстьРеш1),

 собрать( ОстДер, НовДер, ЕстьРеш1, Деревья1, ЕстьРеш).

% "продолжить" решает, что делать после расширения

% списка деревьев

продолжить( да, Верш, С, Поддеревья, _,

 решдер( Верш, F, Поддеревья), да): -

 оценка( Поддеревья, H), F is С + H, !.

продолжить( никогда, _, _, _, _, _, никогда) :- !.

продолжить( нет, Верш, С, Поддеревья, Предел,

 НовДер, ЕстьРеш) :-

 оценка( Поддеревья, H), F is С + H, !,

 расширить( дер( Верш, F, С, Поддеревья), Предел,

 НовДер, ЕстьРеш).

% "собрать" соединяет результат расширения дерева со списком деревьев

собрать( или : _, Дер, да, Дер, да):- !. % Есть решение ИЛИ-списка

собрать( или : ДД, Дер, нет, или : НовДД, нет) :-

 встав( Дер, ДД, НовДД), !. % Нет решения ИЛИ-списка

собрать( или : [], _, никогда, _, никогда) :- !.

 % Больше нет кандидатов

собрать( или:ДД, _, никогда, или:ДД, нет) :- !.

 % Есть еще кандидаты

собрать( и : ДД, Дер, да, и : [Дер Э ДД], да ) :-

 всереш( ДД), !.       % Есть решение И-списка

собрать( и : _, _, никогда, _, никогда) :- !.

 % Нет решения И-списка

собрать( и : ДД, Дер, ДаНет, и : НовДД, нет) :-

 встав( Дер, ДД, НовДД), !. % Пока нет решения И-списка

% "расшлист" формирует дерево из вершины и ее преемников

расшлист( Верш, С, дер( Верш, F, С, Оп : Поддеревья)) :-

 Верш---> Оп : Преемники,

 оценить( Преемники, Поддеревья),

 оценка( Оп : Поддеревья, H), F is С + H.

 оценить( [], []).

оценить( [Верш/С | ВершиныСтоим], Деревья) :-

 h( Верш, H), F is С + H,

 оценить( ВершиныСтоим, Деревья1),

 встав( лист( Верш, F, С), Деревья1, Деревья).

% "всереш" проверяет, все ли деревья в списке "решены"

всереш([]).

всереш( [Дер | Деревья] ) :-

 реш( Дер),

 всереш( Деревья).

реш( решдер( _, _, _ ) ).

реш( решлист( _ , _) ).

f( Дер, F) :-       % Извлечь F-оценку дерева

 arg( 2, Дер, F), !.    % F - это 2-й аргумент Дер

% встав( Дер, ДД, НовДД) вставляет Дер в список

% деревьев ДД; результат - НовДД

встав( Д, [], [Д] ) :- !.

встав( Д, [Д1 | ДД], [Д, Д1 | ДД] ) :-

 реш( Д1), !.

встав( Д, [Д1 | ДД], [Д1 | ДД1] ) :-

 реш( Д),

 встав( Д, ДД, ДД1), !.

встав( Д, [Д1 | ДД], [Д, Д1 | ДД] ) :-

 f( Д, F), f( Д1, F1), F=< F1, !.

встав( Д, [Д1 | ДД], [ Д1 | ДД1] ) :-

 встав( Д, ДД, ДД1).

% "оценка" находит "возвращенную" F-оценку И/ИЛИ-списка деревьев

оценка( или :[Дер | _ ], F) :-

 % Первое дерево ИЛИ-списка - наилучшее

 f( Дер, F), !.

оценка( и :[], 0) :- !.

оценка( и : [Дер1 | ДД], F) :-

 f( Дер1, F1),

 оценка( и : ДД, F2),

 F is F1 + F2, !.

оценка( Дер, F) :-

 f( Дер, F).

% Отношение выбор( Деревья, Лучшее, Остальные, Предел, Предел1):

% Остальные - И/ИЛИ-список Деревья без его "лучшего" дерева

% Лучшее; Предел - ограничение для Списка Деревья, Предел1 -

% ограничение для дерева Лучшее

выбор( Оп : [Дер], Дер, Оп : [], Предел, Предел) :- !.

 % Только один кандидат

выбор( Оп : [Дер | ДД], Дер, Оп : ДД, Предел, Предел1) :-

 оценка( Оп : ДД, F),

 ( Оп = или, !, мин( Предел, F, Предел1);

  Оп = и, Предел1 is Предел - F).

мин( А, В, А) :- А < В, !.

мин( А, В, В).

Рис. 13.12. Программа поиска с предпочтением в И/ИЛИ-графе.

Еще одна процедура

собрать( ОстДер, НовДер, ЕстьРеш1, НовДеревья, ЕстьРеш)

связывает между собой несколько объектов, с которыми работает

расширспис

.

НовДер

— это расширенное дерево, взятое из списка деревьев процедуры

расширспис

,

ОстДер

— остальные, не измененные деревья из этого списка, а

ЕстьРеш1

указывает на "решающий статус" дерева

НовДер

. Процедура

собрать

имеет дело с несколькими случаями в зависимости от значения

ЕстьРеш1

, а также от того, является ли список деревьев И-списком или ИЛИ-списком. Например, предложение

собрать( или : _, Дер, да, Дер, да).

означает: в случае, когда список деревьев — это ИЛИ-список и при только что проведенном расширении получено решающее дерево, считать, что задача, соответствующая всему списку деревьев, также решена, а ее решающее дерево и есть само дерево

Дер

. Остальные случаи легко понять из текста процедуры

собрать

.

Для отображения решающего дерева можно определить процедуру, аналогичную процедуре

отобр

(рис. 13.8). Оставляем это читателю в качестве упражнения.

и_или

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

Гор1

Гор2

P

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

Гор1

Гор2

Гор3

Гор3

Гор1

Гор2

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

X-Z     

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

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

и_или

отобр

отобр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.

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

Для того, чтобы построить экспертную систему, мы должны создать механизмы, обеспечивающие выполнение следующих функций: решение задач, взаимодействие с пользователем и работа в условиях неопределенности. В данной главе мы разработаем и peaлизуем основные идеи построения экспертных систем.

14.1. Функции, выполняемые экспертной системой

Экспертная система — это программа, которая ведет себя подобно эксперту в некоторой, обычно узкой, прикладной области. Типичные применения экспертных систем включают в себя такие задачи, как медицинская диагностика, локализация неисправностей в оборудовании и интерпретация результатов измерений. Экспертные системы должны решать задачи, требующие для своего решения экспертных знаний в некоторой конкретной области. В той или иной форме экспертные системы должны обладать этими знаниями. Поэтому их также называют системами, основанными на знаниях. Однако не всякую систему, основанную на знаниях, можно рассматривать как экспертную. Экспертная система должна также уметь каким-то образом объяснять свое поведение и свои решения пользователю, так же, как это делает эксперт-человек. Это особенно необходимо в областях, для которых характерна неопределенность, неточность информации (например, в медицинской диагностике). В этих случаях способность к объяснению нужна для того, чтобы повысить степень доверия пользователя к советам системы, а также для того, чтобы дать возможность пользователю обнаружить возможный дефект в рассуждениях системы. В связи с этим в экспертных системах следует предусматривать дружественное взаимодействие с пользователем, которое делает для пользователя процесс рассуждения системы "прозрачным".

Часто к экспертным системам предъявляют дополнительное требование — способность иметь дело с неопределенностью и неполнотой. Информация о поставленной задаче может быть неполной или ненадежной; отношения между объектами предметной области могут быть приближенными. Например, может не быть полной уверенности в наличии у пациента некоторого симптома или в том, что данные, полученные лри измерении, верны; лекарство может стать причиной осложнения, хотя обычно этого не происходит. Во всех этих случаях необходимы рассуждения с использованием вероятностного подхода.

В самом общем случае для того, чтобы построить экспертную систему, мы должны разработать механизмы выполнения следующих функций системы:

• решение задач с использованием знаний о конкретной предметной области — возможно, при этом возникнет необходимость иметь дело с неопределенностью

• взаимодействие с пользователем, включая объяснение намерений и решений системы во время и после окончания процесса решения задачи.

Каждая из этих функций может оказаться очень сложной и зависит от прикладной области, а также от различных практических требований. В процессе разработки и реализации могут возникать разнообразные трудные проблемы. В данной главе мы ограничился наметками основных идей, подлежащих в дальнейшем детализации и усовершенствованию.

14.2. Грубая структура экспертной системы

При разработке экспертной системы принято делить ее на три основных модуля, как показано на рис. 14.1:

(1) база знаний,

(2) машина логического вывода,

(3) интерфейс с пользователем.

База знаний содержит знания, относящиеся к конкретной прикладной области, в том числе отдельные факты, правила, описывающие отношения или явления, а также, возможно, методы, эвристики и различные идеи, относящиеся к решению задач в этой прикладной области. Машина логического вывода умеет активно использовать информацию, содержащуюся в базе знаний. Интерфейс с пользователем отвечает за бесперебойный обмен информацией между пользователем и системой; он также дает пользователю возможность наблюдать за процессом решения задач, протекающим в машине логического вывода. Принято рассматривать машину вывода и интерфейс как один крупный модуль, обычно называемый оболочкой экспертной системы, или, для краткости, просто оболочкой.

Рис. 14.1. Структура экспертной системы.

В описанной выше структуре собственно знания отделены от алгоритмов, использующих эти знания. Такое разделение удобно по следующим соображениям. База знаний, очевидно, зависит от конкретного приложения. С другой стороны, оболочка, по крайней мере в принципе, независима от приложений. Таким образом, разумный способ разработки экспертной системы для нескольких приложений сводится к созданию универсальной оболочки, после чего для каждого приложения достаточно подключить к системе новую базу знаний. Разумеется, все эти базы знаний должны удовлетворять одному и тому же формализму, который оболочка "понимает". Практический опыт показывает, что для сложных экспертных систем наш сценарий с одной оболочкой и многими базами знаний работает не так гладко, как бы этого хотелось, за исключением тех случаев, когда прикладные области очень близки. Тем не менее даже если переход от одной прикладной области к другой требует модификации оболочки, то по крайней мере основные принципы ее построения обычно удается сохранить.

В этой главе мы намерены разработать относительно простую оболочку, при помощи которой, несмотря на. ее простоту, мы сможем проиллюстрировать основные идеи и методы в области экспертных систем. Мы будем придерживаться следующего плана:

(1) Выбрать формальный аппарат для представления знаний.

(2) Разработать механизм логического вывода, соответствующий этому формализму.

(3) Добавить средства взаимодействия с пользователем.

(4) Обеспечить возможность работы в условиях неопределенности.

14.3. Правила типа "если-то" для представления знаний

В качестве кандидата на использование в экспертной системе можно рассматривать, в принципе, любой непротиворечивый формализм, в рамках которого можно описывать знания о некоторой проблемной области. Однако самым популярным формальным языком представления знаний является язык правил типа "если-то" (или кратко: "если-то"-правил), называемых также продукциями. Каждое такое правило есть, вообще говоря, некоторое условное утверждение, но возможны и различные другие интерпретации. Вот примеры:

• если предварительное условие P то заключение (вывод) С

• если ситуация S то действие А

• если выполнены условия C1 и C2 то не выполнено условие С

"Если-то"-правила обычно оказываются весьма естественным выразительным средством представления знаний. Кроме того, они обладают следующими привлекательными свойствами:

• Модульность: каждое правило описывает небольшой, относительно независимый фрагмент знаний.

• Возможность инкрементного наращивания: добавление новых правил в базу знаний происходит относительно независимо от других правил.

• Удобство модификации (как следствие модульности): старые правила можно изменять и заменять на новые относительно независимо от других правил.

• Применение правил способствует прозрачности системы.

Последнее свойство — это важное, отличительное свойство экспертных систем. Под прозрачностью мы понимаем способность системы к объяснению принятых решений и полученных результатов. Применение "если-то"-правил облегчает получение ответов на следующие основные типы вопросов пользователя:

(1) Вопросы типа "как": Как вы пришли к этому выводу?

(2) Вопросы типа "почему": Почему вас интересует эта информация?

Механизмы, основанные на "если-то"-правилах, для формирования ответов на подобные вопросы мы обсудим позже.

если

1 тип инфекции — это первичная бактериемия и

2 материал для посева был отобран стерильно, и

3 предполагаемые ворота инфекции — желудочно-кишечный тракт

то

имеются веские аргументы (0.7) за то,

что инфекционный агент является бактерией

Рис. 14.2. "Если-то"-правило медицинской консультативной системы MYCIN (Shortliffe, 1976). Параметр 0.7 показывает степень доверия этому правилу.

"Если-то"-правила часто применяют для определения логических отношений между понятиями предметной области. Про чисто логические отношения можно сказать, что они принадлежат к "категорическим знаниям", "категорическим" — потому, что соответствующие утверждения всегда, абсолютно верны. Однако в некоторых предметных областях, таких, как медицинская диагностика, преобладают "мягкие" или вероятностные знания. Эти знания являются "мягкими"; в том смысле, что говорить об их применимости к любым практическим ситуациям можно только до некоторой степени ("часто, но не всегда"). В таких случаях используют модифицированные "если-то"-правила, дополняя их логическую интерпретацию вероятностной оценкой. Например:

если условие А то заключение В с уверенностью F

Рис. 14.2, 14.3 и 14.4 дают представление о разнообразии способов, которыми знания могут быть выражены при помощи "если-то"-правил. На этих рисунках приведены примеры правил из трех различных систем, основанных на знаниях: медицинской консультативной системы MYCIN, системы AL/X для диагностики неисправностей в оборудовании и системы AL3 для решения шахматных задач.

Вообще говоря, если вы хотите разработать серьезную экспертную систему для некоторой выбранной вами предметной области, вы должны провести консультации с экспертами в этой области и многое узнать о ней сами. Достигнуть определенного понимания предметной области после общения с экспертами и чтения литературы, а затем облечь это понимание в форму представления знаний в рамках выбранного формального языка — это искусство, называемое инженерией знаний. Как правило, это сложная задача, требующая больших усилий, чего мы не можем себе позволить в данной книге. Но какая-нибудь предметная область и какая-нибудь база данных нам необходимы в качестве материала для экспериментов. С практической точки зрения нам для этой цели вполне подойдет "игрушечная" база знаний. На рис. 14.5 показана часть такой базы знаний. Она состоит из простых правил, помогающих идентифицировать животных по их основным признаками в предположении, что задача идентификации ограничена только небольшим числом разных животных.

если

давление в v-01 достигло уровня открытия выпускного клапана

то

выпускной клапан в v-01 открылся

[N=0.005, S=400]

если

давление в v-01 не достигло уровня открытия выпускного клапана и выпускной клапан в v-01 открылся

то

преждевременное открытие выпускного клапана (сместилась установка порогового давления)

[N=0.001, S=2000]

Рис. 14.3. Два правила из демонстрационной базы знаний системы AL/X для диагностики неисправностей (Reiter 1980). N и S — величины "необходимости" и "достаточности", детально описанные в разд. 14.7. Величина S указывает степень, с которой условие влечет за собой заключение (вывод). Величина N указывает, до какой степени истинность условия необходима для того, чтобы заключение было истинным.

если

1 существует гипотеза H, что план P ведет к успеху, и

2 существуют две гипотезы

H1, что план P1 опровергает план P, и

Н2, что план Р2 опровергает план P, и

3 имеют место факты:

гипотеза H1 ложна и

гипотеза Н2 ложна

то

1 породить гипотезу Н3, что составной план "P1 или Р2" опровергает план P, и

2 породить факт: из Н3 следует не( H)

Рис. 14.4. Правило уточнения плана из системы AL3 для решения шахматных задач (Bratko 1982).

Правила, содержащиеся в базе знаний, имеют вид

ИмяПравила : если Условие то Заключение

где

Заключение

Условие

и

или

не

и

или

% Небольшая база знаний для идентификации животных

:- op( 100, xfx, [имеет, 'кормит детенышей',

 'не может', ест, откладывает, это]).

:- op( 100, xf, [плавает, летает, хорошо]).

прав1: если

 Животное имеет шерсть

 или

 Животное 'кормит детенышей' молоком

то

 Животное это млекопитающее.

прав2: если

 Животное имеет перья

 или

 Животное летает и

 Животное откладывает яйца

то

 Животное это птица.

прав3: если

 Животное это млекопитающее и

 ( Животное ест мясо

  или

  Животное имеет 'острые зубы' и

  Животное имеет когти и

  Животное имеет

  'глаза, направленные вперед' )

то

 Животное это хищник.

прав4: если

 Животное это хищник и

 Животное имеет

 'рыжевато-коричневый цвет' и

 Животное имеет 'темные пятна'

то

 Животное это гепард.

прав5: если

 Животное это хищник и

 Животное имеет

 'рыжевато-коричневый цвет' и

 Животное имеет 'черные полосы'

то

 Животное это тигр.

прав6: если

 Животное это птица и

 Животное 'не может' летать и

 Животное плавает

то

 Животное это пингвин.

прав7: если

 Животное это птица и

 Животное летает хорошо

то

 Животное это альбатрос.

факт: X это животное :-

 принадлежит( X, [гепард, тигр, пингвин, альбатрос]).

можно_спросить( _ 'кормит детенышей' _,

 'Животное' 'кормит детенышей' 'Чем').

можно_спросить( _ летает, 'Животное' летает).

можно_спросить( _ откладывает яйца,

 'Животное' откладывает яйца).

можно_спросить( _ ест _, 'Животное' ест 'Что').

можно_спросить( _ имеет _,'Животное' имеет 'Нечто').

можно_спросить( _ 'не может' _,

 'Животное' 'не может' 'Что делать').

можно_спросить( _ плавает, 'Животное' плавает).

можно_спросить( _ летает хорошо,

 'Животное' летает хорошо).

Рис. 14.5. Простая база знаний для идентификации животных. Заимствовано из Winston (1984). Отношение "можно_спросить" определяет вопросы, которые можно задавать пользователю. Операторы

если

то

и

или

Рассмотрим еще одну небольшую базу знаний, которая может помочь локализовать неисправности в простой электрической схеме, состоящей из электрических приборов и предохранителей. Электрическая схема показана на рис. 14.6. Вот одно из возможных правил:

если

лампа1 включена и

лампа1 не работает и

предохранитель1 заведомо цел

то

лампа1 заведомо неисправна.

Вот другой пример правила:

если

радиатор работает

то

предохранитель1 заведомо цел.

Рис. 14.6. Соединения между предохранителями и приборами в простой электрической схеме.

Эти два правила опираются на некоторые факты (относящиеся к нашей конкретной схеме), а именно что лампа1 соединена с предохранитель1 и что лампа1 и радиатор имеют общий предохранитель. Для другой схемы нам понадобится еще один набор правил. Поэтому было бы лучше сформулировать правила в более общем виде (используя прологовские переменные) так, чтобы они были применимы к любой схеме, а затем уже дополнять их информацией о конкретной схеме. Например, вот одно из полезных правил: если прибор включен, но не работает, а соответствующий предохранитель цел, то прибор неисправен. На наш формальный язык это транслируется так: