3.6. ИСПОЛЬЗОВАНИЕ ОЦЕНОЧНЫХ ФУНКЦИЙ

Как мы уже отмечали, обычный способ использования эвристической информации связан с употреблением для упорядочения перебора оценочных функций. Оценочная функция должна обеспечивать возможность ранжирования вершин — кандидатов на раскрытие — с тем, чтобы выделить ту вершину, которая с наибольшей вероятностью находится на лучшем пути к цели. Оценочные функции строились на основе различных соображений. Делались попытки определить вероятность того, что вершина расположена на лучшем пути. Предлагалось также использовать расстояние или другие меры различия между произвольной вершиной и множеством целевых вершин. В салонных играх или головоломках позиции часто ставится в соответствие определенное число очков на основе тех черт, которыми она обладает и которые представляются связанными со степенью уверенности в том, что это шаг к поставленной цели.

Предположим, что задана некоторая функция которая могла бы быть использована для упорядочения вершин перед их раскрытием. Через обозначим значение этой функции на вершине Пока мы будем считать, что — произвольная функция. Позднее же мы предположим, что она совпадает с оценкой стоимости того из путей, идущих от начальной вершины к целевой и проходящих через вершину стоимость которого — наименьшая (из всех таких путей).

Условимся располагать вершины, предназначенные для раскрытия, в порядке возрастания их значений функции Тогда можно использовать некоторый алгоритм (подобный алгоритму равных цен), в котором для очередного раскрытия выбирается та вершина списка ОТКРЫТ, для которой значение f оказывается наименьшим. Будем называть такую процедуру алгоритмом упорядоченного перебора (ordered-search algorithm).

Чтобы этот алгоритм упорядоченного перебора был применим для перебора на произвольных графах (а не только на

деревьях), необходимо предусмотреть в нем возможность работы в случае построения вершин, которые уже имеются либо в списке ОТКРЫТ, либо в списке ЗАКРЫТ. При использовании некоторой произвольной функции нужно учесть, что величина для некоторой вершины из списка ЗАКРЫТ может понизиться, если к ней найден новый путь может зависеть от пути из к даже для вершин списка ЗАКРЫТ). Следовательно, мы должны тогда перенести такие вершины назад в список ОТКРЫТ и позаботиться об изменении направлений соответствующих указателей.

После принятия этих необходимых мер алгоритм упорядоченного поиска может быть представлен такой последовательностью шагов:

(1) Поместить начальную вершину в список, называемый ОТКРЫТ, и вычислить

(2) Если список ОТКРЫТ пуст, то на выход дается сигнал о неудаче; противном случае переходить к следующему этапу.

(3) Взять из списка ОТКРЫТ ту вершину, для которой имеет наименьшее значение, и поместить ее в список, называемый ЗАКРЫТ. Дать этой вершине имя (В случае совпадения значений для нескольких вершин выбирать вершину с минимальным произвольно, но всегда отдавая предпочтение целевой вершине.)

(4) Если — целевая вершина, то на выход подать решающий иуть, получаемый прослеживанием соответствующих указателей; в противном случае переходить к следующему этапу.

(5) Раскрыть вершину построив все непосредственно следующие за ней вершины. (Если таковых не оказалось, переходить сразу к Для каждой такой дочерней вершины вычислить значение

(6) Связать с теми из вершин которых еще нет в списках ОТКРЫТ или ЗАКРЫТ, только что подсчитанные значения Поместить эти вершины в список ОТКРЫТ, и провести от них к вершине указатели.

(7) Связать с теми из непосредственно следующих за вершинами, которые уже были в списках ОТКРЫТ или ЗАКРЫТ, меньшее из прежних и только что вычисленных значений Поместить в список ОТКРЫТ те из непосредственно следующих за вершин, для которых новое значение оказалось ниже, и изменить направление указателей от всех вершин, для которых значение уменьшилось, направив их к

(8) Перейти к (2).

Общая структура алгоритма идентична структуре алгоритма равных цен (см. рис. 3.3), поэтому мы не приводим для него блок-схему. Отметим, что множество вершин и указателей, порождаемых этим алгоритмом, образует дерево (дерево

перебора), причем на концах этого дерева расположены вершины из списка ОТКРЫТ.

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

где — длина пути в дереве перебора от начальной вершины до вершины — это число фишек, которые лежат не на своем месте в описании состояния, связанного с вершиной

Так, для начальной вершины

значение равно

По предположению с большей вероятностью на оптимальном пути находится та вершина, которая имеет наименьшую оценку.

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

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

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

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