Зависимость производительности поиска от точности эвристической функции
Одним из критериев, позволяющих охарактеризовать качество эвристической функции, является эффективный коэффициент ветвления Ь*. Если общее количество узлов, вырабатываемых в процессе поиска А* решения конкретной задачи, равно N, а глубина решения равна d, то Ь* представляет собой коэффициент ветвления, который должно иметь однородное дерево с глубиной d для того, чтобы в нем содержалось №-1 узлов. Поэтому справедлива следующая формула:
N+1 = 1+ Ь*+ (Ь*)2 + ... + (b*)d
Например, если алгоритм А* находит решение на глубине 5 с использованием 52 узлов, то эффективный коэффициент ветвления равен 1,92. Эффективный коэффициент ветвления может изменяться от одного экземпляра одной и той же задачи к другому, но обычно в случае достаточно трудных задач остается относительно постоянным. Поэтому экспериментальные измерения коэффициента Ь* на небольшом множестве задач могут служить хорошим критерием общей полезности рассматриваемой эвристической функции. Хорошо спроектированная эвристическая функция должна иметь значение Ь*, близкое к 1, что позволяет быстро решать довольно большие задачи.
Для проверки эвристических функций h± и h2 авторы сформировали случайным образом 1200 экземпляров задачи с длиной решения от 2 до 24 (по 100 экземпляров для каждого четного значения длины) и нашли их решения с помощью поиска с итеративным углублением и поиска в дереве по алгоритму А* с применением эвристических функций hi и h2. Данные о среднем количестве узлов, развернутых при использовании каждой стратегии и эффективном коэффициенте ветвления, приведены в табл. 4.2. Эти результаты показывают, что эвристическая функция h2 лучше чем h± и намного лучше по сравнению с использованием поиска с итеративным углублением. Применительно к найденным авторами решениям с длиной 14 применение поиска А* с эвристической функцией h2 становится в 30 000 раз более эффективным по сравнению с неинформированным поиском с итеративным углублением.
Интерес представляет вопрос о том, всегда ли эвристическая функция h2 лучше чем h±. Ответ на этот вопрос является положительным. На основании определений этих двух эвристических функций можно легко прийти к выводу, что для любого узла п справедливо выражение h2 (п) >h± (п). Таким образом, можно утверждать, что эвристика h2 доминирует над h±. Доминирование напрямую связано с эффективностью: при поиске А* с использованием функции h2 никогда не происходит развертывание большего количества узлов, чем при поиске А* с использованием h± (возможно, за исключением нескольких узлов с f (п) =С*). Доказательство этого утверждения является несложным. Напомним приведенное на с. 161 замечание, что каждый узел со значением f{n)