Одним из критериев, позволяющих охарактеризовать качество эвристической функции, является эффективный коэффициент ветвления b*. Если общее количество узлов, вырабатываемых в процессе поиска А* решения конкретной задачи, равно N, а глубина решения равна d, то b* представляет собой коэффициент ветвления, который должно иметь однородное дерево с глубиной d для того, чтобы в нем содержалось N-1 узлов. Поэтому справедлива следующая формула:

Например, если алгоритм А* находит решение на глубине 5 с использованием 52 узлов, то эффективный коэффициент ветвления равен 1,92. Эффективный коэффициент ветвления может изменяться от одного экземпляра одной и той же задачи к другому, но обычно в случае достаточно трудных задач остается относительно постоянным. Поэтому экспериментальные измерения коэффициента b* на небольшом множестве задач могут служить хорошим критерием общей полезности рассматриваемой эвристической функции. Хорошо спроектированная эвристическая функция должна иметь значение Ь*, близкое к 1, что позволяет быстро решать довольно большие задачи.

Для проверки эвристических функций h1 и h2 авторы сформировали случайным образом 1200 экземпляров задачи с длиной решения от 2 до 24 (по 100 экземпляров для каждого четного значения длины) и нашли их решения с помощью поиска с итеративным углублением и поиска в дереве по алгоритму А* с применением эвристических функций h1 и h2. Данные о среднем количестве узлов, развернутых при использовании каждой стратегии и эффективном коэффициенте ветвления, приведены в табл. 4.2. Эти результаты показывают, что эвристическая функция h2 лучше чем h1 и намного лучше по сравнению с использованием поиска с итеративным углублением. Применительно к найденным авторами решениям с длиной 14 применение поиска А* с эвристической функцией h2 становится в 30 000 раз более эффективным по сравнению с неинформированным поиском с итеративным углублением.