Алгоритм поиска в глубину

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

Рис. 38.

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

ABCDEFGHK - в ширину,ABEKSLT – в глубину;

В сравнении с поиском в глубину последовательность просматриваемых вершин будет представлять собой совокупность путей;

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

Алгоритм поиска в ширину.

Для организации поиска потребуется два списка:

OPEN – список сгенерированных, но не просмотренных вершин. Он эквивалентен списку NSL;

CLOSED – список просмотренных вершин. Он является объединением SL DL;

Для организации поиска OPEN, следует рассматривать структуру данных FIFO. Это значит, что состояния в OPEN будут добавляться справа, а извлекаться для просмотра – слева. В сравнение с алгоритмом обхода в глубину список NSL, представляет структуру LIFO (LAST IN FIRST OUT). Это значит, что новые состояния добавляются справа и извлекаются для просмотра тоже справа.

CS	OPEN	CLOSED
	A	[ ]
A	A	[ ]
-	BCD	A
B	CDEF	BA
-
C	DEFGM	CBA
D	EFGM	DCBA
-
E	FGMKL	EDCBA
F	GMKLM	FEDCBA
G	MKLMN	GFEDCBA
M	KLMNOP	MGFEDCDA
K	LMNOPS	KMGFEDCBA
L	NNOPST	LKMGFEDCBA

При поиске в ширину для формирования пути к найденной цели необходимо, чтобы каждый элемент списка был двухсоставным

P

R

Первая часть элемента P – сгенерированный потомок, вторая часть R – содержит имя родителя. Такая конструкция позволит, просматривая списки OPEN CLOSED, восстановить путь. Например, для вершины A сгенерируются потомки в списке OPEN

(B,A), (C,A), (D,A)

При обходе в ширину размерность списка OPEN растет по экспоненте, когда как для обхода в глубину размерность списка NSL (NEW STATE LIST) будет расти по линейной функции, следовательно, кроме среднего коэффициента ветвления дополнительно вводится переменная размерности для списка раскрытых (сгенерированных) вершин.

Эта переменная характеризует не производство, а алгоритм поиска. Если имеется средний коэффициент ветвления – В и количество уровней- n, то суммарное количество просматриваемых состояний определяется следующей аналитической зависимостью:

Различия между алгоритмами поиска в глубину и в ширину проявляются в том, для некоторого уровня L, где L=1,n, при поиске в ширину исследуются вершин, а при поиске в глубину исследуется B*L вершин.

Алгоритм поиска в глубину на n уровней.

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

Существует разновидность поиска в глубину с ограничением n, получившего название комбинированный поиск. Её предложил немецкий математик Корф.

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

Хорошим решением проблем поиска в глубину является использование предельного значения глубины поиска. Предельная глубина позволяет ограничить поиск только за­данным числом уровней. Это обеспечивает некоторое подобие "развертки" области по­иска в ширину при поиске в глубину.

Ограниченный поиск в глубину наиболее полезен, если известно, что решение находится в пределах искомой глубины, имеются ограничения во времени или пространство со­стоянии чрезвычайно велико (как в шахматах). В таких задачах число рассматриваемых со­стояний ограничивают предельной глубиной поиска. На рис. 3.17 показан поиск в глубину для 8-головоломки, для которого предельная глубина ограничена пятью уровнями. Поэто­му именно на этой глубине возникает поперечная развертка пространства.

Такая модификация позволяет исправить немало недостатков как поиска в глубину, так и поиска в ширину. Итерационным заглублением [Korf, 1987] называется поиск в глубину, первая итерация которого ограничена 1 уровнем. Если цель не найдена, выполняется еще один шаг с предельной глубиной 2. В процессе поиска предельная глубина увеличивается на 1. На каждой итерации. На каждой итерации алгоритм выполняет поиск в глубину с учетом текущего предельного числа уровней. При этом при переходе от од­ной итерации к другой информация о пространстве состояний не сохраняется.

Поскольку алгоритм исследует пространство "по уровням", он может гарантировать нахождение кратчайшего пути к цели. Поскольку на каждой итерации осуществляется только поиск в глубину, степень использования пространства на каждом уровне л со­ставляет В*п, где В – среднее число дочерних состояний вершины.

На первый взгляд кажется, что итерационное продвижение в глубину менее эффективно по времени, чем поиск глубину или в ширину. Однако временная сложность алго­ритма (время выполнения алгоритма в зависимости от размерности задачи) в действи­тельности имеет тот же самый порядок величины, что и каждый из этих алгоритмов – О(В"). Объяснение этого кажущегося парадокса приведено в [Korf, 1987].

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

ЛЕКЦИЯ 15