Шпора (Шпоры к первому коллоквиуму), страница 12

Основные шаги базового алгоритма ограниченного перебора вглубь (с граничной глубиной D) таковы:

Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open. Установить ее глубину (0). Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список раскрытых вершин Closed.

Шаг 4. Если глубина вершины Current равна граничной глубине D, то перейти к шагу 2, в ином случае перейти к следующему шагу.

Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в произвольном порядке; с указанием их глубины) в начало списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.

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

Конец алгоритма.

Приведенное только что описание очень похоже на описание алгоритма поиска вглубь, разница заключается только в ограничении глубины (шаг 4) и в месте списка Open, куда помещаются построенные дочерние вершины (шаг 5).

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

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

На рис. 6 показано дерево перебора, построенное алгоритмом поиска вглубь; граничная глубина установлена равной 4. В качестве начального состояния взята та же самая, что и в примере на рис. 5, конфигурация игры в восемь. Вершины занумерованы в том порядке, в котором они были построены. В ходе поиска раскрыто 7 и построено 12 вершин, но, как нетрудно убедиться, сравнивая последние два рисунка, в целом это не те же самые 12 первых вершин, построенных алгоритмом поиска вширь.

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

Анализ слепых алгоритмов. Бэктрекинг

Если продолжить выполнение алгоритмов перебора вширь и вглубь для рассмотренного начального состояния игры в восемь (для задачи, указанной на рис.1(б)), то на глубине 5 будет найдена целевая конфигурация. При этом алгоритмом поиска вширь будет раскрыто 26 и построено 46 вершин, а алгоритмом поиска вглубь – соответственно 18 и 35 вершин.

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

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

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

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

Внесенные изменения дают гарантию, что алгоритм поиска вширь всегда завершит работу в случае существования решения, а алгоритм поиска вглубь закончится в любом случае, независимо от существования решения.

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

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

В базовом алгоритме поиска вглубь по существу проводится бэктрекинг: действительно, запоминание всех альтернатив продолжения поиска (нераскрытых вершин) осуществляется в списке Open, на шаге 3 производится выбор варианта-альтернативы, а возврат к этому шагу для выбора следующей альтернативы осуществляется на шагах 4 и 5.

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

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

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

Эвристические методы поиска

Идея, лежащая в основе большинства эвристических алгоритмов, состоит в том, чтобы оценивать с помощью эвристической информации перспективность нераскрытых вершин пространства состояний (с точки зрения достижения цели), и выбирать для продолжения поиска наиболее перспективную вершину. Самый обычный способ использования эвристической информации – введение так называемой эвристической оценочной функции. Эта функция определяется на множестве вершин пространства состояний и принимает числовые значения. Значение эвристической оценочной функции Est(V) может интерпретироваться как перспективность раскрытия вершины (иногда – как вероятность ее расположения на решающем пути). Обычно считают, что меньшее значение Est(V) соответствует более перспективной вершине, и вершины раскрываются в порядке увеличения (точнее, неубывания) значения оценочной функции.

Алгоритм эвристического перебора

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

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

Предполагаем, что исследуемое алгоритмом пространство состояний представляет собой дерево. Тогда основные шаги алгоритма эвристического перебора (best_first_search) таковы:

Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open и вычислить ее оценку.

Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к шагу 3.

Шаг 3. Выбрать из списка Open вершину с минимальной оценкой (среди вершин с одинаковой минимальной оценкой выбирается любая); перенести эту вершину (назовем ее Current) в список Closed.

Шаг 4. Если Current – целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей от нее к начальной вершине, в противном случае перейти к следующему шагу.

Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины. Если таких вершин нет, то перейти к шагу 2, в ином случае – к шагу 6.

Шаг 6. Для каждой дочерней вершины вычислить оценку (значение оценочной функции), поместить все дочерние вершины в список Open, и построить указатели, ведущие от этих вершин к родительской вершине Current. Перейти к шагу 2.

Конец алгоритма.

Заметим, что поиск в глубину можно рассматривать как частный случай упорядоченного поиска с оценочной функцией Est(V) = d(V) , а поиск в ширину – с функцией Est(V) = 1/d(V) , где d(V) – глубина вершины V.

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

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

Впрочем, если оценочная функция учитывает только внутренние характеристики вершин-состояний, то для предотвращения зацикливания требуется более простая модификация алгоритма –

надо просто исключить дублирование состояний в списках Open и Closed, оставляя в них лишь по одному состоянию.

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

Est1(V) = d(V) + k(V) , где

d(V) – глубина вершины V, или число ребер дерева на пути от этой вершины к начальной вершине;

k(V) – число фишек позиции-вершины V, стоящих не на «своем» месте (фишка стоит не на «своем» месте, если ее позиция отлична от позиции в целевом состоянии).