Intel_Nils (526801), страница 17
Текст из файла (страница 17)
Существуют также задачи перебора, в которых все вершины, непосредственно следующие за некоторой, могут быть перечислены и значения 6 для них могут быть подсчитаны еще до построения соответствующих описаний состояний в явной форме. Более того, может оказаться полезным отложить получение описания состояния, связанного с некоторой вершиной, до той поры, когда она сама будет раскрыта.
Тогда в нашем процессе никогда не будут строиться излишние дочерние вершины, которые в дальнейшем в ходе процесса так и остались бы не раскрытыми. Поочередное построение дочерних вершин Когда вершины, непосредственно следующие за некоторой, вычисляются с помощью операторов в пространстве состояний, то очевидно, что эти последующие вершины могут строиться по отдельности н независимо друг от друга.
Кроме того, существуют случаи, когда применение всех применимых операторов было бы очень расточительно в смысле вычислительных затрат. Как указывалось выше, более информированный оператор Г ЗЛЗ. Критерии качества работы методов перебора зо выделял бы несколько наиболее перспективных операторов и строил бы только те последующие вершины, которые возникают в результате их применения. Более гибкий подход состоит в том, чтобы сначала допускать применение самого перспективного оператора (что приведет к одной последующей вершине), оставляя в дальнейшем возможность в процессе перебора построить и другие вершины, непосредственно следующие за данной.
Для того чтобы воспользоваться этой идеей вместе с оценочными функциями для упорядочения вершин, в алгоритм упорядоченного перебора следует внести соответствующие изменения. злз. КРитеРии КАчестВА РАБОты метОдОВ пеРеБОРА Эвристическая сила того нли иного метода перебора в значительной степени зависит от специфических черт, характерных для данной задачи, и определение этой силы — скорее вопрос опыта,, чем вычислений. Тем не менее существуют некоторые критерии работы, которые могут быть вычислены, и хотя эти критерии не дают исчерпывающей оценки эвристической силы, они оказываются полезными при сравнении различных методов перебора.
Один из таких критериев называется целенаправленностью. Целенаправленность Р перебора позволяет узнать, в какой мере перебор идет в направлении цели, а не ведется по нежелательным направлениям. Она просто определяется как Р= —, г где й — длина найденного пути до цели, а Т вЂ” общее число вершин, построенных в течение перебора (включая целевую вершину, но исключая начальную вершину).
Например, если оператор Г, с помощью которого строятся последующие вершины, настолько точен, что строятся только вершины, лежащие на пути к цели, то для него величина Р достигает своего максимума, равного 1. Перебор в слепую характеризуется малыми величинами Р. Таким образом, целенаправленность показывает, .насколько дерево, построенное при переборе, вытянуто, а не кустисто.
Значения величин целенаправленности для некоторых примеров перебора, использованных в настоящей главе, приведены в табл. 3.1. Величина целенаправленности перебора зависит как от трудности задачи, для которой производится этот перебор, так и от эффективности метода перебора.
Для данного метода перебора целенаправленность может быть велика при коротком оптимальном решающем пути и мала, если этот путь оказывается Гл. 8. Метода поиска о пространстве состояний 86 длинным. (Как правило, увеличение длины пути решения Ь приводит к тому, что Т увеличивается е(це быстрее.) Таблица 8.1 Целенаправленность н фактор эффеитнвного ветвление Лла раэлнчнмк прммеров Игре в восемь ! попона перебор Игре в восемь ! 1=9+ в'(и! Игре в восемь 2 4+Р (о!+аз (о( 0,385 Целенаправленность Р Фактор эффективного ветвления В 0,108 0,419 1В6 1,34 1,08 Другой критерий — фактор эффективного ветвления  — гораздо меньше зависит от длины оптимального решающего пути. Его определение основано на представлении, о дереве, имеющем глубину, равную длине этого пути, и общее число вершин, равное числу вершин, построенных в процессе перебора, причем у каждой вершины этого дерева имеется в точности В дочерних вершин.
Таким образом, В связано с длиной пути Ь и общим числом построенных вершин Т соотношениями В+В'+ ... +Вс=Т н — (Ве — 1) = Т.   — 1 Величина В не может быть выписана как явная функция от Л и Т, но на рис. 3.10 представлена диаграмма, показывающая зависимость В от Т при различных значениях !.. Величина В, близкая к единице, соответствует перебору, который весьма точно направлен прямо к цели и очень мало ответвляется на другие направления.
С другой стороны, кустообразный граф перебора характеризуется высоким значением В, Значения В для наших примеров перебора были вычислены с помощью диаграммы, изображенной на рис. 3.10, и приведены вместе со значениями целенаправленности в табл. 3.1. Целенаправленность связана с В и длиной пути формулой Р = = Е( — 1)/В(В' — 1). На рис. 3.11 показано изменение целенаправленности с длиной пути при 'различных значениях В. В той мере, в какой В мало зависит от длины пути, эта величина может быть использована для предсказания того, сколько вершин было бы'построено при переборе той или иной длины. Например, из табл.
ЗЛ видно, что при ! = В+ Р+35 для игры в восемь получается величина В, равная 1,08. Попытаемся м з у 3 О с И о ж о х Ф Ф ОЭ С5 а сэ ы О Гя. 8. Методы поиска в пространстве состояний теперь узнать, как много вершин пришлось,бы построить прн использовании той же самой функции !', решая более трудну1о задачу в игре в восемь, требуюшую, скажем, 30 шагов. Из Ао о,т о,г о,/ о г 4 о о со 1г 14 и 1о го Р И С.
3.1!. ЗааНСННОСта Р От Ь АЛя раЗЛИЧНЫХ ЗиаЧЕННА Рч рис. 3.10 мы видим, что тридцатишаговая задача, прн условии что фактор ветвления остается неизменным, потребовала бы построения около !20 вершин. (Эта оценка, между прочим,- не противоречит экспериментальным результатам Дорана и Мичн (1966), охватывающим больше примеров задач такого типа.) З.14. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ Алгоритмы поиска кратчайшего пути Алгоритмы поиска кратчайшего пути (или пути наименьшей стоимости) между двумя вершинами графа представляют большой интерес для широкого круга дисциплин.
Процедуру, названную нами методом равных цен, впервые описал Дийкстра (!959). Подобный метод полного перебора предлагался также 8.И. Библиографические и исторические замечания ао Муром (1959). Алгоритмы динамического программирования Беллмана по существу также явлнютсн методами полного перебора.
Подробное изложение динамического программирования содержится в книге Беллмана и Дрейфуса (!962). Процедура перебора на заданную глубину часто называется программироианием с обратным слежением (Ьасй-(гаси ргодгатттй); она описана Голомбом и Бомертом (1965). Стюарт Дрейфус (1969) дает подробный обзор этих и других методов поиска на графах.
Эвристические приемы поиска Вопрос использования эвристической информации для увеличения эффективности перебора рассматривался как в области искусственного интеллекта, так и в исследовании операций Вероятно, самым известным применением эвристических оценочных функций были игровые программы, в особенности программа Сэмюэля (!959, 1967) для игры в шашки. Привлечение оценочных функций для придания направленности перебору на графе было предложено Дораном и Мичи (1966) и в дальнейшем исследовалось Дораном (1968) и Мичи и Россом (1970). Наши примеры игры в восемь основаны на примерах Дарана и Мичи. Общая теория использования оценочных функций для ведения перебора была дана в статье Харта, Нильсона и Рафаэля (1968); приведенное нами описание алгоритма упорядоченного поиска и его свойств базируется на этой статье.
В методах ветвей и границ из области исследования операций мы также находим привлечение оценочных функций для направления перебора к цели. Их описание можно найти в обзорной статье Лолера и Вуда (1966). Метод ветвей и границ, предложенный Шапиро (1966) для задачи о коммивояжере, может быть также интерпретирован как прямое применение алгоритма А*.
Наш анализ, подтверждающий важность включения функции 8 (точно так же, как и функции тс) в оценочную функцию, взят нз диссертации Поля (1969). (См. также Поль, 1970.) Поль (1969) рассмотрел также проблему построения перебора как нэ начальной, так и из целевой вершины. В особенности здесь интересно его подробное рассмотрение более сложных критериев остановки, необходимых при двунаправленном переборе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
