Получение оценки Н трудности задач И / ИЛИграфа
Рисунок 13. 9. Получение оценки Н трудности задач И / ИЛИ-графа.
Обозначим через Н( В) оценку трудности вершины В. Для самой верхней вершины текущего дерева поиска H( В) просто совпадает с h( В). С другой стороны, для оценки внутренней вершины дерева поиска нам не обязательно использовать непосредственно значение h, поскольку у нас есть некоторая дополнительная информация об этой вершине: мы знаем ее преемников. Следовательно, как показано на Рисунок 13.9, мы можем приближенно оценить трудность внутренней ИЛИ-вершины как
H( B) = min ( c( B, Bi) + H( Bi) )
i
где с( В, В) - стоимость дуги, ведущей из В в Вi. Взятие минимума в этой формуле оправдано тем обстоятельством, что для того, чтобы решить задачу В, нам нужно решить только одну из ее задач-преемников. Трудность И-вершины В можно приближенно оценить так:
