Таблица 4.2. Сравнение значений стоимости поиска и эффективного коэффициента ветвления для алгоритмов Iterative-Deepening-Search и А* с h1, h2. Данные усреднялись по 100 экземплярам задачи игры в восемь применительно к различным значениям длины решения

Интерес представляет вопрос о том, всегда ли эвристическая функция h2 лучше чем h1. Ответ на этот вопрос является положительным. На основании определений этих двух эвристических функций можно легко прийти к выводу, что для любого узла п справедливо выражение. Таким образом, можно утверждать, что эвристика h2 доминирует над h1. Доминирование напрямую связано с эффективностью: при поиске А* с использованием функции h2 никогда не происходит развертывание большего количества узлов, чем при поиске А* с использованием h1 (возможно, за исключением нескольких узлов с f (п) =С*). Доказательство этого утверждения является несложным. Напомним приведенное на с. 161 замечание, что каждый узел со значениемнаверняка должен быть развернут. Это аналогично утверждению, что должен быть наверняка развернут каждый узел со значением ..Но поскольку для всех узлов значение h2, по крайней мере, не меньше значения h1 то каждый узел, который должен быть наверняка развернут в поиске А* с h2, будет также наверняка развернут при поиске c h1 а применение эвристической функции h1 может к тому же вызвать и развертывание других узлов. Поэтому всегда лучше использовать эвристическую функцию с более высокими значениями, при тех условиях, что эта функция не переоценивает длину пути решения и что время вычисления этой эвристической функции не слишком велико.