3.8. ДОПУСТИМОСТЬ АЛГОРИТМА А*

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

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

вершина, величина для которой не превышает действительной стоимости оптимального пути.

Лемма 3.1. Если для всех выполняется условие то в любой момент времени до того, как алгоритм А закончит свою работу, на любом оптимальном пути Р от вершины к цели существует открытая вершина для которой

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

Мы знаем, что алгоритм А нашел оптимальный путь до вершины я, так как лежит на Р и все ее предшественницы на Р закрыты. Следовательно, и

Так как мы принимаем, что то мы можем записать

Но значение для любой вершины на оптимальном пути равно просто т. е. минимальной стоимости; следовательно, что и утверждает наша лемма.

Теперь мы докажем, что если — нижняя граница для А, то алгоритм А допустим.

Теорема 3.1. Если для всех вершин выполняется условие и если стоимости всех дуг превосходят некоторое малое положительное число то алгоритм А допустим.

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

Случай 1. Работа алгоритма заканчивается, но целевая вершина не найдена. Шаг 4 алгоритма (стр. 66) показывает, что успешное окончание не может произойти до тех пор, пока не

будет найдена целевая вершина. Единственный другой случай окончания работы — окончание, свидетельствующее о неудаче (шаг 2), может произойти лишь тогда, когда список ОТКРЫТ пуст. Но по лемме 3.1, если путь от к целевой вершине существует, то перед окончанием работы алгоритма список ОТКРЫТ не может оказаться пустым.

Случай 2. Нет окончания работы алгоритма. Пусть — некоторая целевая вершина, достижимая из начальной вершины за конечное число шагов с соответствующей минимальной стоимостью Так как стоимость любой дуги не меньше, чем то для любой вершины расположенной на расстоянии, большем, чем шагов от мы имеем

Ясно, что никогда не будет раскрыта вершина, расположенная на расстоянии большем М шагов от так как по лемме 3.1 на оптимальном пути найдется такая открытая вершина что и поэтому, согласно шагу 3 алгоритма, алгоритм А выберет вершину вместо Отсюда заключаем, что невозможность окончания работы алгоритма А может быть вызвана лишь продолжающимся переоткрытием вершин (на шаге 7) в пределах М шагов от Пусть -множество вершин, достижимых в пределах М шагов из и пусть — число вершин в Далее, каждая вершина из может переоткрыта самое большее конечное число раз, скажем ), так как имеется лишь конечное число путей от к проходящих только через вершины, расположенные в пределах М шагов от вершины Пусть

— максимальное число раз, которое может быть переоткрыта любая вершина. Следовательно, после самое большее раскрытий вершин все вершины из должны навсегда остаться закрытыми. Так как ни одна из вершин вне множества не может быть раскрыта, то алгоритм А обязан прекратить свою работу.

Случай 3. Окончание работы на целевой вершине без достижения минимальной стоимости. Предположим, что работа алгоритма А оканчивается на некоторой вершине Но по лемме 3.1 как раз перед окончанием боты на оптимальном пути существует такая открытая вершина что Таким образом, на этом шаге для раскрытия была бы выбрана вершина а не что противоречит предположению об окончании работы алгоритма А.

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

допустимым, но и оптимальным в том смысле, что не существует другого сравнимого допустимого алгоритма, в котором раскрывалось бы меньшее число вершин.