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

F( B) = с( В1, В) + H( В)

Пусть В1 — родительская вершина вершины В , а В 1, В 2, … — ее дочерние вершины, тогда, в соответствии с определениями 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.12. Прежде, чем мы перейдем к объяснению отдельных деталей этой программы, давайте рассмотрим тот способ представления дерева поиска, который в ней используется.

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

• Размер:

(1) дерево состоит из одной вершины (листа) или

(2) оно имеет корень и (непустые) поддеревья.