3.7. Оптимальный алгоритм перебора

Сейчас мы дадим описание некоторой специальной оценоч­ной функции и покажем, что ее использование максимизирует одну меру эффективности перебора и в то же время гаранти­рует обнаружение пути минимальной стоимости, ведущего к цели. Определим оценочную функцию ĵ так, чтобы значение ĵ(n) для любой вершины п представляло собой сумму оценки стои­мости пути минимальной стоимости от начальной вершины s К вершине п и оценки стоимости пути минимальной стоимости от вершины п к целевой вершине. Таким образом, ĵ(n) пред­ставляет собой оценку стоимости пути минимальной стоимости при условии, что этот путь проходит через вершину п. По этой оценке та вершина списка ОТКРЫТ, которая имеет наименьшее значение ĵ, считается лежащей на пути минимальной стоимости, и поэтому следующей должна быть раскрыта именно она. Для демонстрации некоторых из свойств этой оценочной функции мы введем вначале ряд обозначений. Пусть функция k(п_i,п_j) дает действительную стоимость пути минимальной стои­мости между двумя произвольными вершинами п_i и n_j. (Функ­ция k не определена для вершин, между которыми нет пути.) Если Т — множество целевых вершин, то стоимость пути мини­мальной стоимости от вершины n_i до цели обозначим

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

Нам часто будет нужно знать стоимость оптимального пути k(s,n) от данной начальной вершины s до некоторой произволь­ной вершины п. Наши обозначения несколько упростятся, если ввести новую функцию g, определяемую следующим образом: g(n) = k(s, п) для всех п, достижимых из s.

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

ĵ(n) = g(n) + h(n).

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

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

ĵ(n) = g(n) + ĥ(n),

где ĝ — оценка для g, а ĥ — оценка для h.

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

На следующем простом при­мере будет видно, что эта оцен­ка легко вычисляется в процессе работы алгоритма. Рассмотрим подграф, показанный на рис. 3.7. Он состоит из начальной вершины s и трех других вершин n₁, п₂ и п₃. На рисунке указаны стоимости дуг и их направления. Рассмотрим работу алгоритма при переборе на таком подграфе. Отправляясь от вершины s, получаем две непосредственно следующие за ней вершины п₁ и п₂. Оценки ĝ(n₁) и ĝ(n₂) будут тогда равны соответственно 3 и 7. Предположим, что следующей, согласно алгоритму, раскрывается вершина п₁ и строятся вершины п₂ и n₃. На этом шаге ĝ(n₃) =3 + 2 = 5, a ĝ(n₂) снижается до 3 + 3 = 6 (поскольку теперь к этой вершине найден менее дорогой путь). Значение ĝ(n₁) остается равным трем.

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

Далее нам требуется оценка ĥ(п) для h(п) Здесь мы опи­раемся на любую эвристическую информацию, связанную с самой задачей. Эта информация может оказаться подобной той информации, которая была использована при решении вопроса о функции W(n) в примере игры в восемь. Мы назовем И эвристической функцией и более подробно рассмотрим ее позже. Предположим, что теперь мы используем оценочную функ­цию

ĵ(n) = ĝ(n) + ĥ(n).

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

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