Лекция: Алгоритм поиска в глубину.
Опишем алгоритм поиска в глубину — упрощенный алгоритм поиска с возвратами, уже представленный в подразделе 10.2.1. В этом алгоритме состояния-потомки добавляются и удаляются с левого конца списка ореn, Т.е. список ореn реализован как стек магазинного типа или структура LIFO — «last-iп-first-out' (»последним пришел — первым обслужен"). При организации списка ореn в виде стека предпочтение отдается самым «молодым» (недавно сгенерированным состояниям), Т.е. осуществляется принцип поиска в глубину.
Ниже показан процесс реализации алгоритма depth_first_search для графа из рис. 10.10., при этом U — это желаемое целевое состояние.
| После итерации | Список open | Списокclosed |
| [А] | [ ] | |
| [В СD ] | [А] | |
| [Е F С D ] | [В А] | |
| [K L F С D ] | [Е В А] | |
| [S L F С D] | [K Е В А] | |
| [L F С D] | [S K Е В А ] | |
| [T F С D] | [L S K Е В А ] | |
| [F С D ] | [T L S K Е В А ] | |
| [M С D] | [F T L S K Е В А ] | |
| [С D] | [M F T L S K Е В А] | |
| [G Н D] | [С M F T L S K Е В А] | |
| [N Н D ] | [G M F T L S K Е В А] | |
| [Н D] | [N G M F T L S K Е В А] | |
| [O P D] | [Н N G M F T L S K Е В А] | |
| [P D] | [O Н N G M F T L S K Е В А ] | |
| [UD] | [P O Н N G M F T L S K Е В А] | |
| [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
ЦЕЛЬ
Рисунок 10.11. Поиск в глубину для игры в «пятнашки» с 8 фишками, ограниченный 5 уровнями
На рис. 10.11. рассмотрен поиск в глубину на примере ГОЛОВОЛОМКИ с 8 фишками. Как отмечалось ранее, пустая клетка передвигается согласно одному из четырех возможных правил (вверх, вниз, влево и вправо). Числа рядом с состояниями указывают порядок, в котором они были рассмотрены и удалены из списка ореn. Не показаны состояния, находящиеся в ореn, когда цель уже найдена. Глубина поиска в данном случае была ограничена пятью уровнями, чтобы не «затеряться в глубинах» пространства состояний.
После выбора стратегии поиска (на основе данных или от цели), оценки графа и выбора метода поиска (в глубину или в ширину) дальнейший ход решения будет зависеть от конкретной задачи. Влиять на выбор стратегии поиска может необходимость обнаружения именно кротчайшего пути к цели, коэффициент ветвления пространства, доступное время вычислений и возможности пространства, средняя длина пути к целевой вершине графа, а также необходимость получения всех решений или только первого. При выборе метода поиска несложно убедиться, что у любого подхода всегда имеются определенные преимущества и недостатки.
Типичной проблемой, связанной с поиском, является комбинаторная сложность. При наличии нетривиальных проблемных областей количество вариантов, подлежащих рассмотрению, становится столь значительным, что наибольшее значение приобретает существенное увеличение затрат ресурсов на исследование данных вариантов. Можно легко проанализировать причины того, почему это происходит. Для упрощения такого анализа предположим, что пространство состояний представляет собой дерево с единообразным ветвлением b. Это означает, что каждый узел в дереве, за исключением листьев, имеет точно b преемников. Предположим, что кратчайший путь решения имеет длину d, и в дереве на глубине d или меньшей отсутствуют листья. Количество альтернативных путей длины d от начального узла равно bd. При поиске в ширину количество рассматриваемых путей пропорционально bd. Это обозначается как О (bd). Итак, количество возможных путей очень быстро возрастает при увеличении их длины, что приводит к так называемому «ком6инаторному взрыву ».
Поиск в ширину.Поскольку при таком подходе до перехода к уровню п+1 всегда исследуются все узлы на уровне п, поиск в ширину всегда находит самый короткий путь к целевой вершине. Если в задаче существует простое решение, это решение будет найдено. К сожалению, при большом коэффициенте ветвления, если состояния имеют высокое среднее число потомков, комбинаторный взрыв может помешать алгоритму найти решения. Это происходит потому, что все перспективные и неперспективные вершины
для каждого уровня поиска находятся в списке open для глубокого поиска (когда цель расположена глубоко) или для пространства состояний С высоким коэффициентом ветвления этот поиск может быть весьма громоздким.
Степень использования пространства при поиске в ширину измеряется в терминах числа состояний в списке open и является экспоненциальной функцией длины пути в любой момент времени. Если каждое состояние порождает в среднем В дочерних состояний, то общее число состояний на данном уровне определяется умножением В на число состояний предыдущего уровня. Значит, на уровне п число состояний составляет Вn. При исследовании уровня п методом поиска в ширину все состояния помещаются в
open, что может быть нежелательно, если путь к решению достаточно длинный.
Поиск в глубину быстро проникает в глубины пространства. Если известно, что путь решения будет длинным, то поиск в глубину не будет тратить время на поиск большого количества «поверхностных» состояний на графе. С другой стороны, поиск в глубину может «затеряться в глубинах» графа, пропуская более короткие пути к цели, или даже «застрять» на не ведущем к цели бесконечно длинном пути.
Поиск в глубину эффективен для областей поиска с высокой степенью связности, потому что ему не нужно помнить все узлы данного уровня в списке open. Степень использования пространства состояний в случае поиска в глубину — это линейная функция длины пути. На каждом уровне в open сохраняются только дочерние вершины единственного состояния. Если у каждой вершины графа имеется в среднем В дочерних вершин, и если поиск продвигается на п уровней вглубь пространства, то уровень использования пространства составляет Вхп.
Так что же лучше: поиск в глубину или поиск в ширину? На этот вопрос можно ответить так. Необходимо исследовать пространство состояний и проконсультироваться с экспертами в данной области. В шахматах, например, поиск в ширину просто невозможен. В более простых играх поиск в ширину не только возможен, но даже может оказаться единственным способом избежать проигрышей или потерь в игре.