Эвристические оценки и алгоритм поиска

В простых процедурах поиска, приведенных в предыдущем разделе, предусматри­валось проведение в графах AND/OR систематического и исчерпывающего поиска, без каких-либо эвристических средств управления поиском. При решении сложных задач такие процедуры являются слишком неэффективными из-за комбинаторной сложности пространства поиска. Поэтому возникает необходимость в использовании эвристических средств управления поиском, которые предназначены для уменьше­ния этой сложности за счет исключения бесполезных вариантов. Эвристические средства управления поиском, представленные в этом разделе, основаны на числовых эвристических оценках сложности задач, представленных в виде графа AND/OR. Разрабатываемая здесь программа представляет собой реализацию алгоритма,из­вестного под названием АО*. Она может рассматриваться как обобщение программы поиска по заданному критерию А*, которая была предназначена для представления пространства состояний, описанного в главе 12.

Вначале введем критерий оптимизации, основанный на стоимостях дуг в графе
AND/OR Прежде всего дополним применяемое представление графов AND/OR, что­
бы в нем учитывались стоимости дуг. Например, граф AND/OR (см. рис. 13.4) может
быть представлен с помощью следующих предложений:
а------ > or:[b/l,c/3].

Ь----- > and: [d/1, е/1] .

С----- > and: [f/2,g/l] .

е------ > or: [h/й] .

f------ > or:[h/2,i/3] .

goalС d). goa] ( g). goal ( h).

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

Стоимость узла в графе AND/OR удобно определить как стоимость оптимального дерева решения для этого узла. После такого определения стоимость узла будет соот­ветствовать сложности достижения данного узла.

Теперь предположим, что можно оценить стоимости узлов (не зная их деревьев решения) в графе AND/OR с помощью некоторой эвристической функции h. Такие оценки будут использоваться для управления поиском. Рассматриваемая эвристиче­ская программа поиска должна начинать поиск с начального узла и постепенно на­ращивать дерево поиска, развертывая уже посещенные узлы. В этом процессе дерево будет расти даже в тех случаях, если сам граф AND/OR не представляет собой дере­во; в подобных случаях граф развертывается в дерево в результате дублирования частей этого графа.

В данном процессе поиска в любой момент поиска для очередного развертывания выбирается "наиболее перспективное" возможное дерево решения. Но как при этом используется функция h для оценки того, насколько перспективным является воз­можное дерево решения? Или, иначе говоря, как узнать, насколько перспективным является узел (кореньвозможного дерева решения)?

Для узла N в дереве поиска обозначим как Н{Й) оценку его сложности. Для кон­цевого узла Nв текущем дереве поиска Н(К)равно h{M). С другой стороны, для внутреннего узла дерева поиска не следует использовать функцию h непосредственно, поскольку уже имеется некоторая дополнительная информация об этом узле; это оз­начает, что уже известны его преемники. Поэтому, как показано на рис. 13.S,для внутреннего узла N типа OR сложность этого узла можно приближенно представить следующим образом:

H[N> - rain (cost (N, Hi) +H(N_;)J

Глава 13.Декомпозиция задач и графы AND/OR

гдеcost{N,Ni) представляет собой стоимость дуги от N до К . Применение правила минимизации в этой формуле оправдано следующим фактом: чтобы найти дерево решения, которое включает узел К {вместо этого выражения будет также применять­ся краткая формулировка "чтобы решить узел N"), достаточно найти дерево решения для одного из его преемников.

_!_ eOR

H(N) = mitfcoslfN.NJ+HfNJ)

cosiW.N1)

ЩЫ) =X.(cos1iN,Nt) +H(H,))

Рис. 13.8. Оценка сложности, и. задач, пред­ставленных узлами в графе AND /OR

Сложность узла N типа AND можно приближенно представить следующим образом:

H(N>

McoSN, NiJ+HtSi) )

В дальнейшем Н-значение внутреннего узла будем также называть резервной ко­пией его оценки.

В рассматриваемой программе поиска целесообразно использовать вместо Н-значекий другой критерий, Е, определенный в терминах Н следующим образом. До­пустим, что узел N — предшественник узла N в дереве поиска, а стоимость дуги от И до N выражается как cost ( И, N); в таком случае можно определить следующее:

F(N)=cost(M,N}+H(N)

В соответствии с этим, если И — родительский узел узла N, a щ, N₂, ... — дочер­ние узлы узла В, то имеет место следующее: F(N) = cost( И, К) + rain F(Ni), если N * узел OR

F(N)

lb 1

»t( M, N) + ZrF(Ni), если и - узел A N D

Начальный узел поиска S не имеет предшественника, но предположим, что он имеет (воображаемую) входящую дугу со стоимостью 0. Итак, если значение h для всех целевых узлов в графе AND/OR равно 0 и найдено оптимальное дерево решения, то F[5) — это стоимость такого дерева решения (иными словами, сумма всех стои­мостей его дуг).

На любом этапе поиска один из возможных вариантов поддерева решения представ­ляет любой преемник узла OR. В процессе поиска должно всегда приниматься решение о продолжении исследования графа с того преемника, для которого F-значение являет­ся минимальным. Снова вернемся к рис. 13.4 и проследим за подобным процессом по­иска на примере поиска в графе AND/OR. Первоначально дерево поиска состоит только

Часть II. Применение языка Prolog в области искусственного интеллекта

из начального узла а, после чего дерево растет до тех пор, пока не будет найдено дерево решения. На рис. 13.9 показаны некоторые снимки, полученные в процессе роста этого дерева поиска. Для упрощения будем предполагать, что h = 0 для всех узлов. Числа, стоящие рядом с узлами на рис. 13.9, представляют собой F-значения этих узлов (безусловно, они изменяются в ходе поиска по мере накопления дополнительной ин­формации). Ниже приведены некоторые пояснения к рис. 13.9.

А

0»

кандидат 1

кандидат 2

кандидат 2

кандидат 2

кандидат 1

кандидат 1

Рис. 13.9. Трассировка поиска в графе AND/OR no заданному критерию (с использованием h ■ 0) е процессе решения задачи, приведенной на рис. 13.4

Глава 13, Декомпозиция задач играфы AND/OR

В результате развертывания первоначального дерева поиска (снимок А) формиру­ется дерево, показанное на снимке Б. Узел а является узлом OR, поэтому теперь имеются два возможных варианта поддерева решения — Ь и с. Поскольку F(b) = 1 < 3 = F(c), то для развертывания выбирается вариант Ь. Возникает вопрос, на­сколько далеко может быть развернут вариант Ь. Развертывание может продолжать­ся до тех пор, пока не возникнет одна из следующих ситуаций.

1. F-значекне узла b станет больше, чем у его конкурента, узла с.

2. Станет очевидно, что дерево решения найдено.

Итак, возможное поддерево решения b начинает расти в пределах верхней грани­цы для F (Ь), которая составляет F{b) < 3 = F(c). Вначале формируются преемни­ки узла Ь, узлы d и е (снимок В), и F-значение узла b возрастает до 3.

Поскольку это значение не превышает верхнего предела, возможное дерево реше­ния, корнем которого является узел to, продолжает расширяться. Обнаруживается, что d — целевой узел, а затем развертывается узел е, что приводит к получению снимка Г. В этот момент F {b> = 9 > 3, и это вызывает прекращение развертывания варианта Ь. Таким образом, в данном процессе исключается возможность определить, что h также является целевым узлом и что дерево решения уже сформировано. Вме­сто этого активность теперь переключается на конкурирующий вариант с. Предель­ное значение F I с) для развертывания этого варианта теперь устанавливается равным 9, поскольку в данный момент F(b) = Э. В этих пределах возможное дерево реше­ния с корнем в узле с развертывается до тех пор, пока не будет достигнута ситуация, показанная на снимке Д. Теперь в этом процессе обнаруживается, что найдено дерево решения (которое включает целевые узлы h и д) и весь процесс поиска заканчивает­ся. Обратите внимание на то, что в результате данного процесса получено сообщение о дереве решения с наименьшей стоимостью из двух возможных, т.е. о дереве реше­ния, показанном на рис. 13.4, в.