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