3.9. ОПТИМАЛЬНОСТЬ АЛГОРИТМА А*

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

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

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

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

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

Когда в алгоритме А раскрывается некоторая вершина то оценка не больше, чем оптимальная стоимость

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

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

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

Пользуясь предположением о непротиворечивости, мы можем доказать в общем случае, что когда при работе алгоритма А происходит раскрытие некоторой вершины, то оказывается, что оптимальный путь к этой вершине уже найден. Этот факт важен по двум причинам. Во-первых, он используется при доказательстве теоремы об оптимальности алгоритма А, проводимом ниже. Во-вторых, в нем утверждается, что в алгоритме А никогда не придется изменять направление указателя, идущего от закрытой вершины, так как оптимальный путь к этой вершине уже найден. Таким образом, возможность переоткрытия вершин, предусмотренная на шаге 7 работы алгоритма упорядоченного поиска (стр. 66), оказывается излишней и может быть удалена из него, если удовлетворяется предположение о непротиворечивости.

Лемма 3.2. Предположим, что выполнено предположение о непротиворечивости, и предположим, что вершина закрыта алгоритмом А. Тогда

Доказательство. Рассмотрим дерево перебора вершин, порожденных алгоритмом А непосредственно перед закрытием вершины и предположим противное, т. е. предположим, что Далее, существует некоторый оптимальный путь Р из в Так как то этот путь не найден алгоритмом А. Но по лемме 3.1 существует открытая вершина на пути Р с Если то лемма доказана. В противном случае

Таким образом, если мы предполагаем, что то

Прибавляя к обеим частям выписанного неравенства, получаем

Мы можем применить предположение о непротиворечивости к правой части предыдущего неравенства и получить

или

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

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

не может быть больше стоимости оптимального пути от к целевой вершине.

Лемма 3.3. Для любой вершины закрытой алгоритмом А, если Н — нижняя граница для то

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

После доказательства этих двух лемм мы можем доказать оптимальность алгоритма А.

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

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

откуда мы получаем, что

Далее, согласно приведенным выше соображениям, алгоритму А «известно», что , следовательно, ему известно, что

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

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

Из леммы 3.3 известно, что

Таким образом, мы знаем, что

Следовательно, какова бы ни была функция использованная в алгоритме А, она должна удовлетворять неравенству

Далее, когда по алгоритму А раскрывается вершина то, согласно лемме , таким образом,

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