PDF-лекции (1156613), страница 14
Текст из файла (страница 14)
Алгоритм поиска вглубь демонстрирует также способ решения поисковыхзадач, называемый бэктрекингом (backtracking), или режимом возвратов. Этот способ предлагаетопределенную организацию перебора всех возможных вариантов решения задачи, число которых можетбыть велико.Суть бэктрекинга состоит в том, чтобы в каждой точке процесса решения, где существуетнесколько равноправных (априори) альтернативных путей дальнейшего продолжения, выбрать один изних и следовать ему, предварительно запомнив другие альтернативные пути – для того, чтобы в случаенеуспешности выбранного пути решения вернуться в указанную точку и выбрать для продолженияпоиска следующий альтернативный вариант-путь.
В общем случае в процессе решения возможновозникновение многих подобных точек выбора (называемых развилками) со своими вариантамипродолжения решения, и к каждой из точек необходимо совершать возвраты и пробовать другиеварианты.В базовом алгоритме поиска вглубь по существу проводится бэктрекинг: действительно,запоминание всех альтернатив продолжения поиска (нераскрытых вершин) осуществляется в спискеOpen, на шаге 3 производится выбор варианта-альтернативы, а возврат к этому шагу для выбораследующей альтернативы осуществляется на шагах 4 и 5.45Некоторые языки для задач искусственного интеллекта, как, например, Пролог и Плэнер имеютспециальный встроенный механизм для реализации бэктрекинга.
Это означает, что запоминаниеразвилок – самих альтернатив и связанной с ними информации, а также реализация возвратов к нужнымточкам (с восстановлением всей операционной обстановки этой точки) возложены на интерпретаторязыка, т.е. делается автоматически. От программиста требуется лишь определение развилок с нужнымиальтернативами и инициация в необходимый момент процесса возврата (заметим попутно, что языкПлэнер, в отличие от Пролога предлагает более гибкие средства управления бэктрекингом).В целом алгоритмы слепого перебора являются неэффективными методами поиска решения, и вслучае нетривиальных задач их невозможно использовать из-за большого числа порождаемых вершин.Действительно, если L – длина решающего пути, а B – средне количество ветвей (дочерних вершин) укаждой вершины, то для нахождения решения надо исследовать BL путей, ведущих из начальнойвершины.
Величина эта растет экспоненциально с ростом длины решающего пути, что приводит кситуации, называемой комбинаторным взрывом.Таким образом, для повышения эффективности поиска необходимо использовать информацию,отражающую специфику решаемой задачи и позволяющую более целенаправленно двигаться к цели.Такая информация обычно называется эвристической, а соответствующие алгоритмы и методы –эвристическими.День 10. Эвристические методы поискаИдея, лежащая в основе большинства эвристических алгоритмов, состоит в том, чтобыоценивать с помощью эвристической информации перспективность нераскрытых вершин пространствасостояний (с точки зрения достижения цели), и выбирать для продолжения поиска наиболееперспективную вершину. Самый обычный способ использования эвристической информации – введениетак называемой эвристической оценочной функции.
Эта функция определяется на множестве вершинпространства состояний и принимает числовые значения. Значение эвристической оценочной функцииEst(V) может интерпретироваться как перспективность раскрытия вершины (иногда – как вероятность еерасположения на решающем пути). Обычно считают, что меньшее значение Est(V) соответствует болееперспективной вершине, и вершины раскрываются в порядке увеличения (точнее, неубывания) значенияоценочной функции.Алгоритм эвристического перебораПоследовательность шагов формулируемого ниже базового алгоритма эвристического(упорядоченного) перебора похожа на последовательность шагов алгоритмов слепого перебора,отличие заключается в использовании эвристической оценочной функции. После порождения новогосостояния-вершины производится его оценивание (т.е.
вычисление значения этой функции), и спискиоткрытых и закрытых вершин должны содержать кроме самих вершин их оценки, которые ииспользуются для упорядочения поиска.Для раскрытия каждый раз в цикле выбирается наиболее перспективная концевая вершинадерева перебора. Также как и в случае алгоритмов слепого поиска множество порождаемых алгоритмомвершин и указателей образует дерево, в листьях которого находятся нераскрытые вершины.Предполагаем, что исследуемое алгоритмом пространство состояний представляет собой дерево.Тогда основные шаги алгоритма эвристического перебора (best_first_search) таковы:Шаг 1.
Поместить начальную вершину в список нераскрытых вершин Open и вычислить ее оценку.Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, впротивном случае перейти к шагу 3.Шаг 3. Выбрать из списка Open вершину с минимальной оценкой (среди вершин с одинаковойминимальной оценкой выбирается любая); перенести эту вершину (назовем ее Current) в списокClosed.46Шаг 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, стоящих не на «своем» месте (фишка стоит не на «своем»месте, если ее позиция отлична от позиции в целевом состоянии).На рис.1 показано дерево, построенное алгоритмом эвристического перебора с указаннойоценочной функцией.
Оценка каждой вершины приведена рядом с ней внутри кружка. Отдельностоящие цифры, как и раньше, показывают порядок, в котором строились вершины. Двойной рамкойобведена найденная целевая вершина, она построена двенадцатой.Видно, что поскольку каждый раз выбор вершины с минимальной оценкой производится внутривсего построенного к текущему моменту дерева перебора, то раскрываемые друг за другом вершинымогут располагаться в отдаленных друг от друга частях дерева.
Применяемая оценочная функциятакова, что при прочих равных преимущество имеет менее глубокая вершина.Решение задачи длиною в пять ходов найдено в результате раскрытия 6 и построения 13 вершин– это существенно меньше, чем при использовании слепого перебора (соответствующие числа были: 26и 46, 18 и 35). Таким образом, использование эвристической информации приводит к существенномусокращению перебора.Существует несколько критериев оценки качества работы алгоритмов перебора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
