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

В ходе поиска раскрыто 7 и построено 12 вершин, но, как нетрудноубедиться, сравнивая последние два рисунка, в целом это не те же самые 12 первых вершин,построенных алгоритмом поиска вширь.Видно, что в алгоритме поиска в глубину сначала идет поиск вдоль одного пути, пока небудет достигнута установленная граничная глубина, затем рассматриваются альтернативные путитой же или меньшей глубины, которые отличаются от первого пути лишь последней (концевой)вершиной, после чего рассматриваются пути, отличающиеся последними двумя вершинами, и т.д.02 8 31 6 47 g52 8 31g47 6 582 8 37 1 4g6 512952 8 31 6 47 5g72 8g g 8 31 6 3 2 1 47 5 4 7 6 5Рис.61 2 8 31 6 4g7 5610 2 8 3g 1 47 6 542 8 31g67 5 4112 8 31 6g7 5 43g8 32 6 41 7 52 2 8 3g6 41 7 52 8 36 g41 7 5Анализ слепых алгоритмов.

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

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

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

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

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

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

Эта функцияопределяется на множестве вершин пространства состояний и принимает числовые значения.Значение эвристической оценочной функции 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, стоящих не на «своем» месте (фишка стоит не на «своем»месте, если ее позиция отлична от позиции в целевом состоянии).На рис.7 показано дерево, построенное алгоритмом эвристического перебора с указаннойоценочной функцией.