6.3. Направленный поиск

Как было показано в предыдущем разделе, все стратегии слепого поиска обладают экспоненциальными оценками сложности по времени поиска, а некоторые и по памяти, и, вследствие этого, пригодны для решения сравнительно небольших задач. В стратегиях слепого поиска знания, используемые при выборе очередной вершины, определяют только общий порядок выбора и никак не учитывают качество выбора, например, по сложности поиска целевой вершины. В стратегиях направленного поиска знания, используемые для выбора очередной вершины, более глубокие и используют специальные функции, называемые критериями. Если для каждой вершины участвующей в поиске, критерий может быть вычислен, а множество всех вершин упорядочивается по этому критерию, то выбор очередной вершины производится в соответствии со значением этого критерия. Чем лучше значение критерия (например, выше или ниже), тем предпочтительнее выбор. Иными словами, из множества альтернативных вершин выбирается та, для которой критерий имеет наилучшее значение. Поэтому стратегии выбора подобного типа называются стратегиями выбора по наилучшему критерию. Критерии обычно выбираются таким образом, чтобы оптимизировать сложность поиска, найти оптимальное решение или достичь того и другого. В настоящем разделе рассмотрим некоторые стратегии направленного поиска, при котором используются дополнительные, знания о среде, позволяющие понизить сложность поиска. Рассмотрим, как осуществляется направленный поиск при решении оптимизационных задач.

6.3.1. Поиск по критерию близости к цели

Критерием близости к цели обычно является числовая функция вычисляемая для вершины и характеризующая близость этой вершины к целевой. При использовании критерия близости к цели, начиная с корневой вершины, просматриваются все соседние ей вершины, выбирается та, для которой минимальна, и все повторяется вновь для выбранной вершины. И так до тех пор, пока не будет достигнута целевая вершина, для которой т.е. выбирается та вершина, которая ближе всего находится к цели. Вид критерия близости к цели зависит от среды (является проблемно зависимым).

Чтобы получить достаточно полное представление об этом критерии, вернемся к задаче поиска маршрута из Иванова в Москву. Критерием выбора в этом случае будет минимальное расстояние по прямой (кратчайшее расстояние) от вершины (населенного пункта) до Москвы. Естественно, чтобы значение критерия могло быть вычислено, необходимо иметь карту или какой-либо другой источник информации, содержащий сведения о кратчайших расстояниях от населенных пунктов до Москвы. На рис. 6.5 показана последовательность поиска по критерию близости к цели для примера с поиском маршрута из Иванова в Москву, использованного при рассмотрении монотонного поиска в ширину.

Рис. 6.5. (см. скан) Поиск по критерию близости к цели

На первом шаге вычисляется кратчайшее расстояние от корневой вершины (Иваново) до Москвы На втором шаге просматриваются все вершины (города), в которые ведет дорога из Иванова и вычисляется кратчайшее расстояние И от этих городов до Москвы. По этому критерию ближайшим по прямой до цели (Москвы) оказывается Юрьев-Польский На третьем шаге просматриваются все вершины, в которые ведет дорога из Юрьева-Польского.

Для них снова вычисляется кратчайшее расстояние до Москвы. Кратчайшим оказывается расстояние от Киржача Наконец, на последнем шаге вновь просматриваются все вершины, в которые ведет дорога из Киржача, а также вычисляется кратчайшее расстояние до этих городов. Среди этих городов оказывается город с кратчайшим расстоянием т.е. целевая вершина (Москва). На этом поиск по критерию близости к цели завершается.

Поиск по критерию близости к цели является поиском в глубину, но с выбором на каждом шаге единственной вершины, от которой начинается следующий шаг. Недостатки этой стратегии те же, что и для слепого поиска в глубину, а именно, она неоптимальная и неполная, поскольку может случиться, что поиск пойдет по бесконечному пути и никогда не вернется назад. Оценка сложности по времени этой стратегии поиска равна где d - максимальная глубина пространства поиска. При поиске по критерию близости к цели приходится хранить все вершины, рассматриваемые при поиске. Поэтому оценка сложности по памяти для этой стратегии та же, что и оценка сложности по времени. Если критерий близости к цели выбран достаточно удачно, то сложность поиска может быть существенно уменьшена.

6.3.2. Поиск по критерию цены пути (А - поиск)

Обозначим — критерий цены пути из корневой вершины в вершину — уже рассмотренный критерий близости к цели. Пусть оба критерия имеют одну и ту же размерность. Функцию можно считать критерием пути из корневой вершины в целевую. С помощью этого критерия можно находить пути с минимальной ценой. Рассмотрим стратегию поиска на основе этого критерия и покажем, что она будет полна и оптимальна, если ввести небольшие ограничения на критерий Идея этого ограничения состоит в том, чтобы выбирать критерий таким образом, чтобы не переоценивать близость к цели, т.е. не выбирать значение меньше, чем оно есть на самом деле. Критерий выбираемый таким образом, называется допустимым. Стратегия поиска, использующая критерий и допустимый критерий известна как А - поиск. Критерий близости цели использованный в примере с поиском маршрута из Иванова в Москву, является типичным примером допустимого критерия, поскольку не может быть пути из одного населенного пункта в другой короче, чем кратчайший путь. На рис. 6. 6 показаны первые четыре шага поиска пути из Иванова в Москву с использованием критерия в А - поиске. Заметим, что в результате этого поиска, в отличие от поиска только по критерию близости к цели, рассмотренного в предыдущем разделе, выбран путь к Москве не через Юрьев-Польский, а через Владимир, хотя Юрьев-Польский ближе к Москве, чем Владимир. Такой выбор объясняется тем, что цена пути от Иванова до Юрьева-Польского выше, чем до Владимира вследствие очень плохой дороги. Дальнейший выбор маршрута можно проследить по рисунку, где на любом пути от корневой вершины значение критерия нигде не уменьшается при переходе к рассмотрению очередной вершины. Это не случайность и справедливо

Рис. 6.6. Поиск по критерию цены пути (А - поиск)

почти для всех допустимых критериев близости к цели. Критерии для которых имеет место подобное свойство, называются монотонными. Если монотонность нарушается, то путем незначительной коррекции это нарушение может быть устранено. Рассмотрим, например, пару вершин где предшественник, последователь. Предположим, что Тогда т.е. цена пути через вершину самое меньшее равна 7. Предположим также, что т.е. Ясно, что в этом случае критерий не является монотонным. К счастью, благодаря тому, что любой путь через является также путем через цена пути

6 является бессмысленной. Поэтому каждый раз, как рассматривается какая-либо вершина и оказывается, что ее цена пути мы полагаем, что т.е.

Таким способом немонотонность может быть всегда устранена, и критерий никогда не будет уменьшаться вдоль одного и того же пути при условии, что допустимое. Если же никогда не уменьшается вдоль одного и того же пути, начинающегося от корневой вершины, то на пространство состояний можно наложить контуры, каждый из которых охватывает множество вершин для которых значение критерия меньше определенной величины с. Процесс поиска можно представить как переход

от просмотра еще не просмотренных вершин какого-либо внутреннего контура, для всех вершин А, которого имеет место к просмотру вершин некоторого внешнего контура, для всех вершин которого имеет место Это продолжается до тех пор, пока внутри очередного контура не окажется целевая вершина с При удачном выборе критерия контуры как бы растягиваются в сторону целевой вершины, фокусируясь вокруг оптимального пути. Обозначим с цену оптимального пути. Тогда можно утверждать следующее:

А-поиск просматривает вершины с

А-поиск осуществляет направленный просмотр вершин, стремясь к просмотру вершин контура, для которых имеет место

Решение, получаемое с помощью А-поиска, является оптимальным, поскольку находится вершина с максимальным значением а следовательно, и максимальным так как А-поиск является также полным, поскольку увеличивая постепенно значение критерия мы должны, в конце концов, найти путь к целевой вершине. Заметим также, что для данного критерия не существует никакой другой процедуры поиска, которая давала бы более оптимальные решения, чем А- поиск. Все эти утверждения требуют более строгих доказательств, которые мы здесь не приводим. Оценки сложности по времени и памяти для А- поиска аналогичны оценкам для поиска по критерию близости цели.

На идее А-поиска построено много других методов поиска, учитывающих особенности конкретной среды, которые влияют на выбор критериев, и различные ограничения, например по доступным ресурсам (времени выполнения и доступной памяти).

6.3.3. Оптимизирующий итеративный поиск

Во многих задачах поиск целевого состояния (состояний) в пространстве состояний ставится как задача нахождения такого состояния (состояний), которое в определенном смысле наилучшее (оптимальное). При этом не имеет особого значения цена пути нахождения цели, если эта цель может быть достигнута за приемлемые затраты времени и памяти. Идея оптимизирующего итеративного поиска станет понятной, если полагать, что состояния — это точки на поверхности некоторого горного ландшафта. Чем выше точка находится над уровнем моря, тем лучше (оптимальнее) состояние, которое она представляет. Точки, соответствующие пикам, являются оптимальными точками. Задачей оптимизирующего итеративного поиска является такой порядок просмотра точек, или иначе такое движение по поверхности ландшафта, при котором в конце концов достигаются (находятся) оптимальные точки. Имеется большое разнообразие процедур оптимизирующего итеративного поиска. Одной из таких процедур является градиентный поиск. Рассмотрим суть этой процедуры.

Идея градиентного поиска чрезвычайно проста — двигаться в направлении подъема вверх, начиная с некоторого начального состояния. Дерево поиска не хранится, а сохраняется только последнее найденное состояние и оценка

его качества Если попадаются несколько состояний с одинаковой оценкой качества, то, как правило, выбирается одно из них. Градиентный поиск в чистом виде обладает тремя известными недостатками.

Если вершин несколько, то поднявшись на одну из них, процесс поиска остановится, полагая, что цель достигнута, хотя достигнутая вершина является всего лишь локальным оптимумом и далека от наилучшей.

Если ландшафт имеет плато, то процесс поиска по нему становится случайным.

Если ландшафт имеет гребни (хребты) со слабым наклоном, то легко достигнув гребня, процесс поиска может очень долго идти по гребню, пока не достигнет оптимальной вершины.

После остановки процесса градиентного поиска начинается следующая итерация с другого начального состояния. Найденное оптимальное состояние сохраняется до тех пор, пока не будет найдено лучшее. Этот итеративный процесс поиска осуществляется конечное число раз или пока не будет найдено устраивающее решение.

Ясно, что если провести достаточное число подобных итераций, то оптимальное решение, в конце концов, будет найдено. Успех градиентною поиска сильно зависит от вида пространства состояний. Если число локальных минимумов невелико, то оптимальное решение будет найдено сравнительно быстро. Процедуры градиентного поиска могут отличаться способом выбора очередной вершины в процессе подъема на вершину, выбором очередной вершины для новой итерации и т.д.

Вопросы и упражнения

(см. скан)

(см. скан)