Prolog

когда сам И / ИЛИ-граф не является деревом; при этом граф будет разворачиваться в дерево за счет дублирования своих отдельных частей.

Для продолжения поиска будет всегда выбираться 'наиболее перспективное' решающее дерево-кандидат. Каким же образом используется функция   h   для оценки степени перспективности решающего дерева-кандидата или, точнее, вершины-кандидата - корня этого дерева?

Рис. 13. 9.  Получение оценки  Н  трудности задач  И / ИЛИ-графа.

Обозначим через Н( В) оценку трудности вершины  В.  Для самой верхней вершины текущего дерева поиска  H( В)  просто совпадает с  h( В).  С другой стороны, для оценки внутренней вершины дерева поиска нам не обязательно использовать непосредственно значение  h,  поскольку у нас есть некоторая дополнительная информация об этой вершине: мы знаем ее преемников. Следовательно, как показано на рис. 13.9, мы можем приближенно оценить трудность внутренней ИЛИ-вершины как

        H( B) = min ( c( B, B_i) + H( B_i) )

                                ⁱ

где  с( В, В)  -  стоимость дуги, ведущей из  В  в  В_i.   Взятие минимума в этой формуле оправдано тем обстоятельством, что для того, чтобы решить задачу  В,  нам нужно решить только одну из ее задач-преемников. Трудность И-вершины  В   можно приближенно оценить так:

       

Будем называть H-оценку внутренней вершины 'возвращенной' (backed-up) оценкой.

Более практичной с точки зрения использования в нашей программе поиска является другая величина  F,  которую можно определить в терминах  H  следующим образом. Пусть   В1  -  вершина-предшественник вершины  В  в дереве поиска, причем стоимость дуги, ведущей из  В1  в  В,   равна  с( В1, В),  тогда положим

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

Пусть  В1  -  родительская вершина вершины  В,  а  В₁,  В₂,   ... - ее дочерние вершины, тогда, в соответствии с определениями  F  и  H, имеем

        F( B) = c( B1, B) + minF( B_i),             если  В   -  ИЛИ-вершина

                                          ⁱ

                       если  В    -  И-вершина

Хотя стартовая вершина  А  и не имеет предшественника, будем считать, что стоимость ведущей в нее (виртуальной) дуги равна 0. Если положить  h  равным 0 для всех вершин И / ИЛИ-дерева, то для любого найденного оптимального решающего дерева окажется, что его стоимость, т.е. сумма стоимостей его дуг, в точности равна  F( A).

На любой стадии поиска каждый преемник ИЛИ-вершины соответствует некоторому альтернативному решающему дереву-кандидату. Процесс поиска всегда принимает решение продолжать просмотр того дерева-кандидата, для которого  F-оценка минимальна. Вернемся еще раз к рис. 13.4 и посмотрим, как будет вести себя процесс, поиска на примере И / ИЛИ-графа, изображенного на этом рисунке. В начале дерево поиска состоит всего из одной вершины - стартовой вершины  а, далее дерево постепенно 'растет' до тех пор, пока не будет найдено решающее дерево. На рис. 13.10, показан ряд 'мгновенных снимков', сделанных в процессе роста дерева поиска. Для простоты мы предположим, что h = 0 для всех вершин. Числа, приписанные