Intel_Nils (526801), страница 14
Текст из файла (страница 14)
Мы знаем, что алгоритм А' нашел оптимальный путь до вершины и', так как л' лежит на Р и все ее предшественницы на Р закрыты. Следовательно, ф(п') = д(л') и ((л') = д (п') + п(п'). Так как мы принимаем, что б(л') ( Ь(л'), то мы можем записать ) (л') ~ (у (и') + й (и') = г (и'). Но значение ) для любой вершины на оптимальном пути равно просто )(з), т. е. минимальной стоимости; следовательно, 1(п') ()(з), что и утверждает наша лемма. Теперь мы докажем, что если й" — нижняя граница для Ь, то алгоритм А' допустим. Теорема 3.1.
Если для всех вершин л выполняется условие б(п) ( Ь(п) и если стоимости всех дуг превосходят некоторов малое положительное число 6, то алгоритм А* допустим. Доказательство. Мы будем доказывать эту теорему, предположив противное, а именно, что не всегда работа алгоритма А* заканчивается отысканием оптимального пути от начальной вершины з к цели.
Нужно рассмотреть три случая: либо работа алгоритма А* заканчивается, но целевая вершина остается не найденной, либо работа алгоритма вообще никогда не заканчивается, либо заканчивается на некоторой целевой вершине, но при этом не достигается минимальная стоимость. Случай 1. Работа алгоритма заканчивается, но целевая вершина не найдена. Шаг 4 алгоритма (стр. 66) показывает, что успешное окончание не может произойти до тех пор, пока не Гм д Методы поиска е пространстее состопний будет найдена целевая вершина.
Единственный другой случай окончания работы — окончание, свидетельствующее о неудаче (шаг 2), может произойти лишь тогда, когда список ОТКРЫТ пуст. Но по лемме 3.1, если путь от з к целевой вершине существует, то перед окончанием работы алгоритма список ОТКРЫТ не может оказаться пустым. Случай 2. Нет окончания работы алгоритма. Пусть ( — некоторая целевая вершина, достижимая из начальной вершины за конечное число шагов с соответствующей минимальной стоимостью !(з).
Так как стоимость любой дуги не меньше, чем б, то для любой вершины п, расположенной на расстоянии, большем, чем М = 1(з)/б шагов от э, мы имеем ~ (и) ) ф (п) ) й (и) ) Мб = ) (з). Ясно, что никогда не будет раскрыта вершина, расположенная на расстоянии большем М шагов от з, так как по лемме 3.1 на оптимальном пути найдется такая открытая вершина и', что 1(п') ( )(в) < ) (и), и поэтому, согласно шагу 3 алгоритма, алгоритм А» выберет вершину п' вместо п. Отсюда заключаем, что ' невозможность окончания работы алгоритма А* может быть вызвана лишь продолжающимся переоткрытием вершин (на шаге 7) в пределах М шагов от з. Пусть д(М) — множество вершин, достижимых в пределах М шагов из з, и пусть ч(М)— число вершин в х(М). Далее, каждая вершина и из х(М) может бысть переоткрыта самое большее конечное число раз, скаже»е р(п, М), так как имеется лишь конечное число путей от з к и, проходящих только через вершины, расположенные в пределах М шагов от вершины з.
Пусть р(М)= гпах р(п, М) х(м> — максимальное число раз, которое может быть переоткрыта любая вершина. Следовательно, после самое большее ч(М)р(М) раскрытий вершин все вершины из т(М) должны навсегда остаться закрытыми. Так как ни одна из вершин вне множества у(М) не может быть раскрыта, то алгоритм А» обязан прекратить свою работу. Случай 3. Окончание работы на целевой вершине без постижения минимальной стоимости. Предположим, что работа алгоритма А' оканчивается на некоторой вершине ( с 1(1) = = й(() ) 1(з). Но по лемме 3.1 как раз перед окончанием работы на оптимальном пути существует такая открытая вершина и', что 1(п') (1(з) (1(1).
Таким образом, на этом шаге для раскрытия была бы выбрана вершина и', а не 1, что противоречит предположению об окончании работы алгоритма А». Доказательство теоремы 3.1 теперь завершено. В следующем разделе мы покажем, что при задании другого разумного ограничения на функцию 6(п) алгоритм А' будет не только допу- ДД Оатимаяьиоать алторитма А' стимым, но и оптимальным в том смысле, что не существует другого сравнимого допустимого алгоритма, в котором раскрывалось бы меньшее число вершин. 3 9. ОПТИМАЛЬНОСТЬ АЛГОРИТМА А* Точность нашей эвристической функции б зависит от объема тех эвристических знаний, которыми мы располагаем относительно задачи, моделируемой нашим графом.
Ясно, что использование условия В(и) = О соответствует полному отсутствию какой-либо эвристической информации о задаче, хотя такая оценка н является нижней границей для й(л), и, следовательно, она приводит к допустимому алгоритму (описанному ранее алгоритму равных цен). Мы будем говорить, что алгоритм А более информирован, чем алгоритм В, если эвристическая информация, используемая в алгоритме А, позволяет вычислять такую нижнюю границу для й(п), которая всюду строго больше (для всех вершин тт, не являюшихся целевыми вершинами), чем та, которая вычисляется по эвристической информации, используемой в алгоритме В.
Как пример рассмотрим игру в восемь, решенную на рис. 3.6. Там была использована оценочная функция г'(л) = Й(тт) + )Г'(и). Мы можем интерпретировать процесс упорядоченного перебора в этом примере как применение алгоритма А* с условием б(п) = ты(п). Так как Ж'(л) есть нижняя граница для числа шагов, остающихся до цели, то алгоритм А* в этом' случае допустимый. Кроме того, алгоритм А* с условием л(л) = )Тт(п), очевидно, более информирован, чем алгоритм равных цен, в котором принимается б(п) = — О.
Интуитивно мы ожидаем, что в более информированном алгоритме придется раскрыть меньшее число вершин, прежде чем будет найден путь минимальной стоимости. Для игры в восемь это соображение подтверждается сопоставлением рис.3.2 и рис. 3.6. Конечно, то обстоятельство, что один алгоритм раскрывает меньшее число вершин, чем другой, еще не означает, что он более эффективен. В более информированном алгоритме могут потребоваться более дорогостоящие вычисления, которые ослабят его эффективность. Тем не менее число вершин, которые раскрываются в процессе работы алгоритма, — один из факторов, определяющий эффективность, н это как раз тот фактор, который позволяет делать простые сравнения, Если теперь наложить еще одно слабое ограничение на функцию ~, то можно показать, что алгоритм Аа оптимален в следующем смысле.
В алгоритме Аь никогда не раскрывается больше вершин, чем в любом другом допустимом алгоритме А, таком, что А* более информирован, чем А. формальному доказательству оптимальности алгоритма А' мы предпошлем краткое описание плана рассуждений. 74 Гь. 8. Методы ооисиа е ооостоаистее состояния Рассмотрим любой допустимый алгоритм А, такой, что А более информирован, чем А. Мы покажем, что алгоритм А раскрывает каждую вершину и, которую раскрывает алгоритм А". Чтобы сделать это, прежде всего мы должны доказать, что класс вершин, раскрываемых алгоритмом А*, подчиняется следующим ограничениям: Когда в алгоритме Ае раскрывается некоторая 'вершина и, оптимальный путь к п уже найден, т. е.
я(п) = д(п). Когда в алгоритме А* раскрывается некоторая вершина п, то оценка ((и) не больше, чем оптимальная стоимость )(з). Пользуясь этими ограничениями, мы покажем, что если в алгоритме А не происходит раскрытия вершины п, раскрываемой в алгоритме Ае, то алгоритм А должен знать, что любой путь к цели, проходящий через вершину а, не оптимален.
Короче говоря, алгоритм Ае не может быть более информированным, чем алгоритм А, если алгоритм А может избежать раскрытия тех вершин, которые в алгоритме А* раскрываются. Таким образом, наша первая задача состоит в доказательстве двух сформулированных выше предварительных результатов.
Очевидно, что в случае деревьев для всех вершин выполняется равенство ф(п) = д(а), ибо по дереву существует только один путь от начальной вершины к любой вершине и дерева. Но в общем случае нам придется наложить еще одно ограничение на 6, для того чтобы показать, что как только в алгоритме А* происходит раскрытие некоторой вершины графа, то оказывается, что оптимальный путь к этой вершине уже был найден. Мы будем предполагать, что для любых двух вершин гп и п, для которых й(т,а) существует, выполняется условие пт (т) — пс (и) (~ й (гп, и). Иными словами, разность между оценками стоимостей путей от любой пары вершин т и п до цели должна быть нижней границей стоимости оптимального пути от т до а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
