3.8. Эвристическая сила функции ĥ

При определении эвристической силы алгоритма упорядочен­ного поиска выбор функции ĥ играет решающую роль Исполь­зование условия ĥ  0 гарантирует допустимость, но ведет к. слепому перебору и поэтому обычно оказывается неэффек­тивным. Выбор в качестве ĥ наибольшей из возможных нижних границ для h приводит к тому, что раскрывается наименьшее число вершин, при котором еще сохраняется допустимость.

Часто эвристическая сила алгоритма может быть повышена ценой отказа от допустимости при использовании в качестве п некоторой функции, не являющейся нижней границей для h. Такая дополнительная эвристическая сила позволяет решать существенно более трудные задачи. Для игры в восемь функ­ция ĥ(n) = W(n) (где W(n) —число фишек, находящихся не на своих местах) есть нижняя граница для h(n), но эта оценка не обеспечивает очень хорошей оценки трудности данного располо­жения фишек (в смысле числа шагов, отделяющих от цели). Лучшую оценку дает функция ĥ(n)=P(n), где Р(п)—сумма расстояний каждой фишки от «своего места» (без учета фишек, расположенных на ее пути). Однако даже эта оценка слишком груба, так как в ней не учитывается должным образом труд­ность обмена местами двух соседних фишек.

Следующая оценка достаточно хороша для игры в восемь:

ĥ(n) = P(n) + 3S(n);

здесь S(n)—число очков, учитывающее порядок расположения фишек. Для его вычисления нужно последовательно просмотреть все нецентральные фишки в данной конфигурации и за каждую

а фишку, за которой не идет та фишка, которая должна бы идти (в целевой конфигурации), начисляется два очка, а в противном случае берется нуль очков. За фишку, находящуюся в центре, начисляется одно очко. Отметим, что такая функция ĥ не дает нижней границы для h.

Используя такую функцию ĥ в оценочной функции ĵ(n) = ĝ(n) + ĥ(n), мы можем легко находить решения в намного более сложных случаях игры в восемь, чем рассмотренные ниже. На рис. 3.8 приведено дерево, возникающее в результате приме­нения алгоритма упорядоченного перебора с этой оценочной функцией к задаче преобразования левой из следующих конфи­гураций в правую.

Как и раньше, значение ĵ для каждой вершины помещено в кружок, а цифры без кружков указывают порядок, в котором рас­крывались вершины

Оказалось, что решающий путь имеет минимальную длину (18 шагов), хотя, поскольку функция ĥ не есть нижняя граница для h, нахождение оптимального пути не было гарантировано. Заметим, что такая функция ĥ приводит к перебору, направ­ленному достаточно прямо к цели. Имеется лишь небольшое число ответвлений в сторону, и сосредоточены они вблизи на­чальной вершины.

•Другим фактором, определяющим эвристическую силу алго­ритма упорядоченного перебора, является объем усилий, связан­ных с вычислением ĥ. Лучшей функцией ĥ была бы функция, в точности совпадающая с Л, и она бы обеспечивала абсолютный минимум числа раскрытий вершин. Такая функция ĥ могла бы, например, быть определена в результате отдельного полного перебора на каждой вершине, что, очевидно, не привело бы к уменьшению объема вычислений в целом.

Иногда намного легче вычислить некоторую функцию К, от­личную от нижней границы для А, чем такую, которая с ней совпадает. В этом случае эвристическая сила алгоритма может быть увеличена по двум причинам — как благодаря уменьшению общего числа раскрываемых вершин (ценою отказа от допусти­мости), так и благодаря уменьшению объема вычислений. В ряде случаев эвристическая сила данной функции ĥ может быть повышена просто путем умножения ее на некоторую поло­жительную константу, большую единицы. Если этот множитель очень велик, то мы получаем ситуацию, аналогичную условию ĝ(n)*= 0. Такой выбор, безусловно, приведет к недопустимому, но тем не менее способному удовлетворительно работать алго­ритму. Опираясь на интуицию, можно было бы предположить, что выбор ĝ(n)*= 0 приведет к повышению эффективности пере­бора в тех случаях, когда желательно получить любой путь к цели (не обязательно имеющий минимальную стоимость). В следующем разделе мы приведем некоторые результаты, про­тиворечащие такого рода интуиции.

Рис. 3.8. Дерево, построенное в процессе упорядоченного перебора.

Суммируя, отметим, что имеются три важных фактора, влия­ющих на эвристическую силу алгоритма упорядоченного поиска:

1. Стоимость пути.

2. Число вершин, раскрытых в процессе поиска пути.

3. Объем вычислений, требуемых для подсчета значений функции К.

Выбор соответствующей функции ĥ позволяет получить для каждой задачи требуемый компромисс между этими тремя фак­торами, при котором максимизируется эвристическая сила алго­ритма.