Intel_Nils (526801), страница 16
Текст из файла (страница 16)
Имеется лишь небольшое число ответвлений в сторону, и сосредоточены они йблизи начальной вершины. 1 4 ° В г!6 753 з г!О 716 48а ф463 763 7 ° з 216 фазв 753 2 1О ф.',.". 6 1 О ф?КЗ 7 ° 5 Н ° г! ЗН! г!О 518 ф ?ИО ф 466 ф 483 ф 1 ° 5 755 75 1 а75 765 281 ф а4 6 755 ф?6 ° ф 458 7 фан! ф 78! ф гза ф'.",:,', ф 14 281 2 ° 1 281 ф а43 ф 483 ф 43 ° 765 ОЗ 765 г8! ф аО 5 8 13 264 7 ° 5 !В 813 2 4 ° 763 Р н с. 3.8. Дерево, построенное в процессе упорядоченного перебора.
16 ° 81 фг4з 765 16 фза! ?65 17 ф 3 ф243 ф,'.„"' ф 216 21 ° 748 ф486 ° 53 753 7 фг ° ! 7 13 11 2Н! ф 4 О:! 56 12 261 463 7 ° 1 13 281 4 ° 3 765 813 244 ф 813 2 ° 4 7 66 В ° 3 214 ф 813 ° 24 765 8!5 724 ° О 5 ф 4Ра а 22 ООР6846а ° 13 1 ° 3 123 424 824 3 ° 4 ф ф ф 1 За 824 763 Гя. 8. Методы поиска в пространстве состояний Другим фактором, определяющим эвристическую силу алгоритма упорядоченного перебора, является объем усилий, связанных с вычислением 6.
Лучшей функцией 6 была бы функция, в точности совпадающая с й, и она бы обеспечивала абсолютный минимум числа раскрытий вершин. Такая функция И могла бы, например, быть определена в результате отдельного полного перебора на каждой вершине, что, очевидно, не привело бы к уменьшению объема вычислений в целом. Иногда намного'легче вычислить некоторую функцию й', отличную от нижней границы для й, чем такую, которая с ней совпадает. В этом случае эвристическая сила алгоритма может быть увеличена по двум причинам — как благодаря уменьшению общего числа раскрываемых вершин (ценою отказа от допустимости), так и благодаря уменьшению объема вычислений.
В ряде случаев эвристическая сила данной функции И может быть повышена просто путем умножения ее на некоторую положительную константу, большую единицы. Если этот множитель очень велик, то мы получаем ситуацию, аналогичную условию Й(п) = — О. Такой выбор, безусловно, приведет к недопустимому, но тем не менее способному удовлетворительно работать алгоритму. Опираясь на интуицию, можно было бы предположить, что выбор я(л) = — О приведет к повышению эффективности перебора в тех случаях, когда желательно получить любой путь к цели (не обязательно имеющий минимальную стоимость).
В следующем разделе мы приведем некоторые результаты, противоречащие такого рода интуиции. Суммируя, отметим, что имеются три важных фактора, влияющих на эвристическую силу алгоритма упорядоченного поиска: 1. Стоимость пути. 2. Число вершин, раскрытых в процессе поиска пути. 3. Объем вычислений, требуемых для подсчета ' значений функции л". Выбор соответствуюшей функции й" позволяет получить для каждой задачи требуемый компромисс между этими тремя факторами, при котором максимизируется эвристическая сила алгоритма.
3.11. ВАЖНАЯ РОЛЬ ФУНКЦИИ Я Во многих задачах нам необходимо просто найти какой- нибудь путь к целевой вершине, а стоимость результируюшего пути значения не имеет. (Но, конечно, объем трудностей перебора при нахождении такого пути нас интересует.) В таких случаях можно привести интуитивные соображения как за включение функции ф в оценочную функцию, так и за то, чтобы этого не делать, 8! зйд Виниал ролв фуикции й Интуитивное соображение против включения функции ц в оценочную функцию Если нам требуется найти какой-нибудь путь до цели, то функцию я можно не учитывать, поскольку на любом шаге перебора нам не важны стоимости уже построенных путей.
Для нас существенны только те затраты на перебор, которые еще потребуются, прежде чем будет найдена целевая вершина, а они, возможно, и зависят от величин 6 для открытых вершин, но уж заведомо не зависят от значений ф для этих открытых вершин. Следовательно, в таких задачах мы должны бы пользоваться оценочной 'функцией ~ = л. Интуитивное соображение за включение функции я в оценочную функцию Даже в том случае, когда не существенно, чтобы найденный путь имел минимальную стоимость, функцию ~ следует включить в )' для того, чтобы быть уверенным, что хотя бы какой- нибудь путь будет в конечном итоге найден. Такой уверенностью необходимо заручаться всегда, когда й" не достаточно хорошая оценка для 6, поскольку если всегда раскрываются вершины с минимальным а", то может случиться так, что в нашем процессе перебора будут все время раскрываться ложные вершины, а целевая вершина достигаться не будет.
Включение функции й как бы вносит определенную компоненту полного перебора и гарантирует, что нет такой части у графа, которую процесс перебора постоянно обходит. Каждое из приведенных соображений представляется разумным, хотя нам кажется, что второе более оправдано логически. В ряде частных случаев второе соображение может быть даже подкреплено соответствующим точным анализом. , Рассмотрим случай бесконечного графа в форме бесконечного гп-арного дерева. (Бесконечное т-арное дерево — это дерево, в котором у каждой вершины имеются в точности и непосредственно следующих за ней вершин,) В этом графе имеется единственная целевая вершина, которая расположена на й-м уровне. Заметим, что цель достижима из любой вершины этого конкретного графа.
Пример такого графа приведен на рнс. 3.9; стоимости ребер предполагаются едйничными, Предположим, что при переборе на этом графе мы пользуемся следующей функцией л'; 6(п) = й(п) + Е для вершин и на кратчайшем пути, 6(п) = Ь(п) — Е для вершин и вне кратчайшего пути, Гя. 8. Методы поиска в пространстве состояний где Š— некоторая целочисленная ошибка.
То есть наша функция й' всегда содержит ошибку, величина которой равна некоторому целому Е'). Кроме того, знак этой ошибки выбран так, чтобы вызвать наибольшие затруднения. Нроанализировав самый худший слу- сне еерсанн на греми д Цвневан иа удав Рис. 3.9. Граф, изображающий бесконечное щ-арное дерево. чай, мы покажем, что при такой функции 6 перебор с функцией ! =ф+а более эффективен, чем перебор с функцией г = й, если только Е ) 1. Мы должны сопоставить следующие два случая; Случай 1. г = ~+ й. Пусть Фвчл — число вершин, которые были раскрыты до достижения цели. Здесь мы обязаны раскрывать вершину, если она расположена в пределах Е единиц от какой-либо вершины на кратчайшем пути.
(В духе рассматриваемого нами самого худшего случая мы всегда будем выбирать наихудшую из возможностей, если число вершин равно Е.) Видно тогда, что Ф +» — — Й(1+(т — 1) (число вершин в т-арном дереве и глубиной (Š— 1))) = й ~1+ (т — 1) ~ ~ ~ = йта, '! Заметим, что функции 6 ие дает в атом случае нижней границы для 6. ез 8.Г2.
И«зол»»о«ание другик »вру«гик Случай 2. ! = Ю. Пусть )ӄ— число вершин, которые были раскрыты до достижения цели. Здесь мы обязаны раскрывать вершину, если она расположена в пределах 2Š—.1 единиц от вершины на кратчайшем пути. (Обманчиво перспективные вершины в этом случае заставляют процесс перебора отойти на большее расстояние от кратчайшего пути к цели.) Итак, для Е ) 1 имеем Л/» =Й(1+(т — !) (число вершин в т-арном дереве, зв-~ глубины (2Š— 2))) = й (1+(т —.!)~ ~, ]~ = йтза-'. (Отдельно можно показать, что Мь = й для Е = 0.) Мы видим, что й!ь больше Ух+» для Е ) 1, а это означает, что (для нашего графа) для эффективного перебора необходимо в оценочную функцию включить функцию ~.
Отношение М~+ь/Л~ь не зависит от й и дается просто выражением А~у+» ! — — для Е~:!. з-~ » Хотя в реальных задачах это различие в эффективности может оказаться существенно меньше, наше исследование наихудшего случая показывает, что интуитивное соображение о необходимости включения функции К в оценочную функцию имеет ощутимую ценность. зда.
ИСПОЛЬЗОВАНИЕ ДРУГИХ ЭВРИСТИК Перебор этапами До сих пор в настоящей главе мы обсуждали вопрос о том, что использование эвристической информации может существенно уменьшить объем перебора, необходимого для поиска приемлемого пути. Следовательно, ее использование позволяет также осуществлять перебор на гораздо больших графах. И тем не менее могут возникнуть случаи, когда имеющаяся в нашем распоряжении память оказывается исчерпанной раньше, чем будет найден удовлетворительный путь. В этих случаях может быть полезным не отказываться полностью от продолжения перебора, а «отсечь» часть ветвей дерева, построенного к этому моменту в процессе перебора, освободив тем самым пространство памяти, необходимое для углубления перебора.
Такой процесс перебора может осуществляться этапами, которые отделяются друг от друга операциями отсечения дерева, необходимыми для освобождения памяти. В конце каждого этапа удерживается некоторое подмножество открытых вершин, Гл. 8. Метода яоисяи е яростриистее состояний например вершины с наименьшими значениями г. Наилучшие пути к этим вершинам запоминаются, а остальная часть дерева отбрасывается. Затем начинается перебор снова, уже от этих «лучших» открытых вершин. Этот процесс продолжается до тех пор, пока либо будет найдена целевая вершина, либо будут исчерпаны все ресурсы.
Ясно, что даже если на каждом этапе используется алгоритм А', то хотя весь процесс заканчивается построением некоторого пути, тем не менее у нас нет теперь гарантии, что этот путь будет оптимальным. Ограничение числа дочерних вершин Раньше в этой главе было отмечено, что другой путь уменьшения объема перебора состоит в том, чтобы использовать более информированный оператор Г, который не порождал бы слишком много ненужных последующих вершин. В пределе «полностью информированный» оператор Г порождал бы лищь вершины, расположенные на оптимальном пути, снимая тем самым полностью необходимость перебора. Один из приемов, который может позволить снизить требуемый объем перебора, состоит в том, чтобы сразу же после раскрытия вершины отбросить почти все дочерние вершины, оставив лишь небольшое их число с наименьшими значениями функции г. Конечно, отброшенные вершины могут оказаться расположенными на наилучших (и даже только на наилучших) путях, так что только эксперимент может определить пригодность такого метода отсечения ветвей графа для конкретных задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
