Лекция 28.

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

Опишем алгоритм поиска в глубину - упрощенный алгоритм поиска с возвратами, уже представленный в подразделе 10.2.1. В этом алгоритме состояния-потомки добавляются и уда­ляются с левого конца списка ореn, Т.е. список ореn реализован как стек магазинного типа или структура LIFO - "last-iп-first-out' ("последним пришел - первым обслужен"). При ор­ганизации списка ореn в виде стека предпочтение отдается самым "молодым" (недавно сге­нерированным состояниям), Т.е. осуществляется принцип поиска в глубину.

Ниже показан процесс реализации алгоритма depth_first_search для графа из рис. 10.10., при этом U - это желаемое целевое состояние.

После итерации	Список open	Список closed
0	[А]	[ ]
1	[ В С D ]	[А]
2	[Е F С D ]	[В А]
3	[K L F С D ]	[ Е В А]
4	[ S L F С D]	[ K Е В А]
5	[L F С D]	[ S K Е В А ]
6	[ T F С D]	[L S K Е В А ]
7	[F С D ]	[T L S K Е В А ]
8	[ M С D]	[F T L S K Е В А ]
9	[С D]	[M F T L S K Е В А]
10	[G Н D]	[С M F T L S K Е В А]
11	[ N Н D ]	[G M F T L S K Е В А]
12	[Н D]	[N G M F T L S K Е В А]
13	[O P D]	[Н N G M F T L S K Е В А]
14	[P D]	[ O Н N G M F T L S K Е В А ]
15	[UD]	[ P O Н N G M F T L S K Е В А]
16	[D ]	[UP O Н N G M F T L S K Е В А ]

Таблица 10.3. Состояние списков после каждой итерации алгоритма поиска в глубину для графа на рис. 10.10.

0 итерация - Инициализируем списки. Список open =[A]; Список closed =[ ];

1 итерация – Выбираем первую вершину из списка open и определяем её как текущее состояние Х=А. Применяем процедуру определения потомков к Х=А, потомки есть, ими являются вершины В, С, D. Записываем слева направо эти вершины в список open, удаляя слева из этого списка вершину А и записывая эту вершину в список closed слева направо. Далее алгоритм переходит к следующей итерации.

2 итерация – Выбираем первую вершину из списка open и определяем её как текущее состояние Х=В. Применяем процедуру определения потомков к Х= В, потомки есть, ими являются вершины Е, F. Записываем слева направо эти вершины в список open, удаляя слева из этого списка вершину В и записывая эту вершину в список closed слева направо. Далее алгоритм переходит к следующей итерации. Эти итерации продолжаются до тех пор пока текущее состояние Х не будет равно целевому состоянию U, либо список open окажется пустым.

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

сохранения лучшей версии. 1