PART3 (Печатные лекции), страница 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эвристический (упорядоченный) поиск

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

Таким образом, основные шаги алгоритма эвристического перебора таковы:

Шаг 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.

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

Est(V) = D(V) + K(V) где

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

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

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

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

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

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

Лисп- и Плэнер-алгоритмы поиска в пространстве состояний

Реализация алгоритмов слепого поиска на языке программирования Лисп не представляет особых затруднений. Ниже приводятся тексты лисп-функций BREADTH_FIRST_SEARCH (поиска вширь) и LIMITED_DEPTH_SEARCH (ограниченного поиска вглубь) от начального состояния StartState. Обе функции вырабатывают в качестве своего значения либо решающий путь (в виде лисповского списка) – если таковой существует, и список () в противном случае.

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

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

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

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

Предикат IS_GOAL проверяет, является ли ее аргумент целевым состоянием. В случае положительного исхода проверки значением функции является само проверяемое состояние, в ином случае значение равно() .

В обоих алгоритмах поиска применяется также вспомогательная рекурсивная функция RETAIN_NEW, которая оставляет в списке дочерних состояний Dlist только те, которые не порождались ранее – тем самым исключается зацикливание при поиске в произвольном графе:

(defun RETAIN_NEW (Dlist)

(prog (D)

(cond( (null Dlist) (return()) )

(t (setq D (car Dlist))

(cond((or (member D Open)(member D Closed))

(return(RETAIN_NEW (cdr Dlist)) ))

(t (return(cons D

(RETAIN-NEW(cdr Dlist)))) )) )) ))

Другая вспомогательная рекурсивная функция CHECK_GOALS проверяет, есть ли среди дочерних состояний целевые. Значением этой функции является целевое состояние, если таковое найдено, и пустой список в ином случае:

(defun CHECK_GOALS (Dlist)

(cond((null Dlist) nil)

((IS_GOAL(car Dlist)) (car Dlist))

(t (CHECK_GOALS (cdr Dlist)) )) )

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

(defun BREADTH_FIRST_SEARCH(StartState)

(prog (Open Closed Current

Deslist ;список дочерних вершин;

Reflist ;список указателей;

Goal ;целевая вершина;)

;Шаг 1:; (setq Open (list (list 'S0 StartState)))

;Шаг 2:; ВS (cond( (null Open) (return() )))

;Шаг 3:; (setq Current (car Open))

(setq Open (cdr Open))

(setq Closed (cons Current Closed))

;Шаги 4,5:; (setq Deslist (OPENING Current))

(cond( (setq Goal(CHECK_GOALS Deslist))

(return (SOLUTION Goal Reflist)) ))

; Исключение повторных вершин-состояний:

(setq Deslist (RETAIN_NEW Deslist))

(cond( (null Deslist) (go BS) ))

(setq Open (append Open Deslist))

; Построение указателей и занесение их в общий список:

(setq Reflist(append(CONNECT Deslist Current)

Reflist))

(go ВS) ))

Граф-пространство состояний для головоломки-игры в восемь достаточно велик (в игре в пятнадцать фишек он на порядок больше), поэтому хотя в принципе применимы алгоритмы слепого поиска, предпочтителен все же эвристический поиск. Опишем нужные для HEURISTIC_SEARCH вспомогательные лисп-функции IS_GOAL, EST, OPENING, SOLUTION, CONNECT для игры в восемь. В соответствии с предположениями, сделанными в предыдущем разделе, состояние задачи (конфигурация игры) представляется списком из следующих элементов:

идентификатор состояния (используются атомы S1,S2,S3, ... генерируемые встроенной лисповской функцией gensym);

собственно описание состояния – список из номеров фишек, записанных последовательно по рядам квадрата;

число-глубина состояния-вершины в дереве перебора;

числовая эвристическая оценка состояния.