Intel_Nils (526801), страница 13
Текст из файла (страница 13)
Дать этой вершине имя и. (В случае совпадения значений Г для нескольких вершин выбирать вершину с минимальным Г произвольно, но всегда отдавая предпочтение целевой вершине.) (4) Если п — целевая вершина, то на выход подать решающий путь, получаемый прослеживанием соответствуюшнх указателей; в противном случае переходить к следующему этапу.
(5) Раскрыть вершину и, построив все непосредственно следуюшие за ней вершины. (Если таковых не оказалось, переходить сразу к (2).) Для каждой такой дочерней вершины и; вычислить значение Г(пс). (6) Связать с теми из вершин пь которых еще нет в списках ОТКРЫТ или ЗАКРЫТ, только что подсчитанные значения ~(пт). Поместить эти вершины в список ОТКРЫТ,и провести от них к вершине и указатели. (7) Связать с теми из непосредствейно следующих за п вершинами, которые уже были в списках ОТКРЫТ или ЗАКРЫТ, меньшее из прежних и только что вычисленных значений г. Поместить в список ОТКРЫТ те из непосредственно следующих за и вершин, для которых новое значение Г оказалось ниже, и изменить направление указателей от всех вершин, для которых значение Г уменьшилось, направив их к и.
(8) Перейти к (2). Общая структура алгоритма идентична структуре алгоритма равных цен (см.' рис. 3.3), поэтому мы не приводим для него блок-схему. Отметим, что множество вершин и указателей, порождаемых этим алгоритмом, образует дерево (дерево пере- 67 8.6.
Использование оценоинмк функций бора), причем на концах этого дерева расположены вершины нз списка ОТКРЫТ. Работу алгоритма проще всего пояснить, рассмотрев вновь тот же самый пример игры в восемь. Мы будем пользоваться следующей простой оценочной функцией: г(п) = й(п) + В'(и), где Й(л) — дллна пути в дереве перебора от начальной вершины до вершины п,' а Ф'(л) — это число фишек, которые лежат не на своем месте в описании состояния, связанного с вершиной п. Так, для начальной вершины значение 7 равно 0 + 4 = 4 р По предположению с ббльшей вероятностью на оптимальном пути находится та вершина, которая имеет наименьшую оценку.
На рис. З.б показан результат применения к игре в восемь алгоритма упорядоченного перебора и использования такой оценочной функции. Значение 7 для каждой вершины приведено внутри кружка. Отдельно стоящие цифры показывают порядок, в котором раскрывались вершины. Мы видим, что найден тот же самый путь решения, который был получен другими методами перебора, но использование оценочной функции привело к существенно меньшему числу раскрытий вершин. Выбор оценочной функции сильно влияет на результат перебора.
Использование оценочной функции, не учитывающей истинной перспективности некоторых вершин, может привести к построению путей, не обладающих минимальной стоимостью. С другой стороны, использование оценочной функции, которая Гя. 8.
АГетоди поиска в пространстве состопние придает слишком большое значение возможной перспективности всех вершин (такой, как в алгоритме равных цен), приведет к тому, что придется раскрыть очень много вершин. В следуютцих нескольких разделах будет получен ряд теоретических результатов, относящихся к некоторой специальной оценочной функции, использование которой приводит к раскрытию наименьшего числа вершин, совместимого с гарантией нахождения пути минимальной стоимости. 3.7. ОПТИМАЛЬНЫИ АЛГОРИТМ ПЕРЕБОРА Сейчас мы дадим описание некоторой специальной оценочной функции и покажем, что ее использование максимизирует одну меру эффективности перебора и в то же время гарантирует обнаружение пути минимальной стоимости, ведущего к цели.
Определим оценочную функцию г так, чтобы значение г(п) для любой вершины и представляло собой сумму оценки стоимости пути минимальной стоимости от начальной вершины в к вершине п и оценки стоимости пути минимальной стоимости от вершины л к целевой вершине. Таким образом, г(л) представляет собой оценку стоимости пути минимальной стоимости при условии, что этот путь проходит через вершину л. По этой оценке та вершина списка ОТКРЫТ, которая имеет наименьшее значение Г, считается лежащей на пути минимальной стоимости, и поэтому следующей должна быть раскрыта именно она. Для демонстрации некоторых из свойств этой оценочной функции мы введем вначале ряд обозначений.
Пусть функция й(пап;) дает действительную стоимость пути минимальной стоимости между двумя произвольными вершинами лт и пь (Функ. ция й не определена для вершин, между которыми нет пути.) Если Т вЂ” множество целевых вершин, то стоимость пути минимальной стоимости от вершины пт до цели обозначим й(пт)= ппп й(п„пг). «гят (Функция 6 не определена для тех вершин л, из которых недостижима ни одна из целевых вершин.) Мы будем говорить, что любой путь от вершины лт к целевой вершине, для которого достигается й(пт), является оптимальным путем из вершины лт к цели. Нам часто будет нужно знать стоимость оптимального пути й(з, л) от данной начальной вершины з до некоторой произвольной вершины и.
Наши обозначения несколько упростятся, если ввести новую функцию у, определяемую следующим образом: йт(л) = й (з, и) дня всех и, достижимых из в. Д7. Оптимальный алгоритм перебора Далее, определим функцию 7 так, что ее значение )(и) для любой вершины п есть сумма дейстрительной стоимости оптимального пути от вершины з до вершины и и стоимости оптимального пути от вершины и до какой-нибудь из целевых вершин. Таким образом, 1(п) = у (и) + й (и).
Иными словами, значение 7(п) есть стоимость оптимального пути при условии, что он проходит через вершину и. (Заметим, что 7(э) = й(в) представляет собой действительную стоимость оптимального пути от вершины з к цели без всяких ограничений.) Мы хотим, чтобы наша оценочная функция 7 была оценкой функции 7.
Будем считать, что наша оценка дается выражением 7 (и) = у (и) + й (и), где у — оценка для д, а й — оценка для й. Естественно выбрать в качестве у(п) стоимость пути от з до и в дереве перебора, которая получается после суммирования стоимостей дуг, лежащих на пути, даваемом указателями, иду- т шими от и назад к з. (Этот путь есть путь наименьшей стоимости .
7 от з к и, найденный алгоритмом к настояшему моменту.) Заме- ну тим, что из определения следует, что д(п) .= у(п). На следующем простом примере будет видно, что эта оценка легко вычисляется в процессе работы алгоритма. Рассмотрим 7 подграф, показанный на рис. 3.7. Он состоит из начальной верши- р»с, 3.7. пример вычислен»» ны з и трех других вершин пь пг Фу"»""" и и пг. На рисунке указаны стоимости дуг и их направления. Рассмотрим работу алгоритма при переборе на таком подграфе. Отправляясь от вершины з, получаем две непосредственно следующие за ней вершины п, и пэ Оценки у(п,) и у (п,) будут тогда равны соответственно 3 и 7.
Предположим, что следующей, согласно алгоритму, раскрывается вершина и, и строятся вершины пт и пг. На этом шаге й(пг) = 3+ 2 = 5, а у(па) снижается до 3 + 3 = 6 (поскольку теперь к этой'вершине найден менее дорогой путь). Значение к(п1) остается равным трем.
Далее нам требуется оценка й(п) для й(п). Здесь мы опи- раемся на любую эвристическую информацию, связанную Гл 3. Методы поиска в пространстве состояннй 70 с самой задачей. Эта информация может оказаться подобной той информации, которая была использована при решении вопроса о функции Ю'(л) в примере игры в восемь. Мы назовем Л" эвристической функцией и более подробно рассмотрим ее позже. Предположим, что теперь мы используем оценочную функцию ) (л) = ст(л) + л (л). Назовем алгоритм упорядоченного перебора, в котором используется эта оценочная функция, алгоритмом А *. Заметим, что если А'= — О, то алгоритм А* совпадает с описанным выше алгоритмом равных цен. Раньше мы сделали утверждение (без доказательства), что в алгоритме равных цен гарантируется' нахождение пути до цели, имеющего минимальную стоимость.
Сейчас мы покажем, что если л — нижняя граница для й, то алгоритм А * также находит оптимальный путь к цели. (Так как 6 О, безусловно, служит нижней границей для й, то факт, что алгоритм равных цен позволяет находить оптимальные пути, будет следовать как частный случай этого более общего результата для А*.) 38. ДОПУСТИМОСТЬ АЛГОРИТМА А* В общем случае будем называть алгоритм перебора допусти иылт, если для произвольного графа он оканчивает свою работу построением оптимального пути к цели (при условии, что такой путь существует).
В этом разделе мы докажем, что если 6 — нижняя граница для 6, то алгоритм А" допустим. Идея доказательства состоит в том, чтобы сначала убедиться, что (при нашем ограничении на л) до завершения работы алгоритма А' в списке ОТКРЫТ и на некотором оптимальном пути имеется некоторая вершина, значение 7 для которой не больше действительной стоимости )(з) оптимального пути. Используя этот результат, мы видим, что допустимость алгоритма А' следует из того факта, что вершина из списка ОТКРЫТ, имеющая минимальное значение 7, не может оказаться целевой вершиной (на которой заканчивает работу алгоритм А") до тех пор, пока не будет найдена целевая вершина, значение 7 для которой равно Г(з). Таким образом, мы прежде всего докажем лемму, утверждающую, что если эвристическая функция й' является нижней границей для й, то до того, как алгоритм А' закончит свою работу, на любом оптимальном пути будет находиться открытая ') ') Любую вершнну списка ОТКРЫТ мы будем называть открытой, а любую вершину списка ЗАКРЫТ вЂ” закрытой.
Незакрытой вершнноя является та, которая либо находится в списке ОТКРЫТ, либо еше не была построена в процессе перебора. З.8, допустимость алгоритма А* 71 вершина, величина 7 для которой не превышает действительной стоимости 1(е) оптимального пути. Лемма 3.1. Если для всех и выполняется условие Л'(л) ( ( 'п(п), то в любой момент времени до того, как алгоритм А' закончит свою работу, на любом оптимальном луги Р от вершины е к цели существует открытая вершина л', для которой ")(и') ()(з).
Доказательство. Предположим, что оптимальный путь Р представляется упорядоченной последовательностью (э = = ло,пи ам, ..,лд), где ль — целевая вершина. Пусть и' — первая открытая вершина в этой последовательности. (Должна существовать по крайней мере одна такая вершина, так как если пи закрыта, то алгоритм А' уже закончил свою работу.) По определению 7 имеем 1 (и') = д (и') + й (л').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
