3.7. ОПТИМАЛЬНЫЙ АЛГОРИТМ ПЕРЕБОРА

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

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

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

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

для всех достижимых из

Далее, определим функцию так, что ее значение для любой вёршины есть сумма действительной стоимости оптимального пути от вершины до вершины и стоимости оптимального пути от вершины до какой-нибудь из целевых вершин. Таким образом,

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

Мы хотим, чтобы наша оценочная функция была оценкой функции Будем считать, что наша оценка дается выражением

где — оценка для оценка для .

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

Рис. 3.7. Пример вычисления функции .

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

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

Далее нам требуется оценка для Здесь мы опираемся на любую эвристическую информацию, связанную

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

Предположим, что теперь мы используем оценочную функцию

Назовем алгоритм упорядоченного перебора, в котором используется эта оценочная функция, алгоритмом Заметим, что: если то алгоритм А совпадает с описанным выше алгоритмом равных цен.

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