Поиск в глубину

Алгоритм поиска

Поиск в глубину ( DFS ) — это алгоритм обхода или поиска по древовидным или графовым структурам данных. Алгоритм начинается с корневого узла (выбирая произвольный узел в качестве корневого узла в случае графа) и исследует как можно дальше каждую ветвь перед возвратом. Дополнительная память, обычно стек , необходима для отслеживания узлов, обнаруженных до сих пор вдоль указанной ветви, что помогает в возврате графа.

Вариант поиска в глубину был исследован в 19 веке французским математиком Шарлем Пьером Тремо ^[1] как стратегия решения лабиринтов . ^{[2] [3]}

Характеристики

Анализ времени и пространства DFS различается в зависимости от области его применения. В теоретической информатике DFS обычно используется для обхода всего графа и занимает время , ^[4] где — число вершин и число ребер . Это линейно по размеру графа. В этих приложениях он также использует пространство в худшем случае для хранения стека вершин на текущем пути поиска, а также набора уже посещенных вершин. Таким образом, в этой настройке временные и пространственные ограничения такие же, как и для поиска в ширину , и выбор того, какой из этих двух алгоритмов использовать, зависит не столько от их сложности, сколько от различных свойств упорядочения вершин, которые производят два алгоритма. ${\displaystyle O(|V|+|E|)}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$ ${\displaystyle O(|V|)}$

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

DFS также может использоваться для сбора выборки узлов графа. Однако неполный DFS, подобно неполному BFS , смещен в сторону узлов высокой степени .

Пример

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

Для следующего графика:

поиск в глубину, начинающийся с узла A, предполагая, что левые ребра в показанном графе выбираются раньше правых ребер, и предполагая, что поиск запоминает ранее посещенные узлы и не будет их повторять (так как это небольшой граф), посетит узлы в следующем порядке: A, B, D, F, E, C, G. Ребра, пройденные в этом поиске, образуют дерево Тремо , структуру, имеющую важные приложения в теории графов . Выполнение того же поиска без запоминания ранее посещенных узлов приводит к посещению узлов в порядке A, B, D, F, E, A, B, D, F, E и т. д. навсегда, попадая в цикл A, B, D, F, E и никогда не достигая C или G.

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

Результат поиска в глубину

Четыре типа ребер, определяемых остовным деревом

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

Упорядочение вершин

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

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

Для бинарных деревьев дополнительно существует упорядочение по входу и обратное упорядочение по входу .

Например, при поиске по направленному графу ниже, начиная с узла A, последовательность обходов — это либо ABDBACA, либо ACDCABA (выбор первого посещения B или C из A зависит от алгоритма). Обратите внимание, что повторные посещения в форме возврата к узлу для проверки того, есть ли у него еще непосещенные соседи, включены сюда (даже если обнаружено, что их нет). Таким образом, возможными предварительными порядками являются ABDC и ACDB, тогда как возможными поздними порядками являются DBCA и DCBA, а возможными обратными поздними порядками являются ACBD и ABC D.

Обратный постпорядок производит топологическую сортировку любого направленного ациклического графа . Этот порядок также полезен в анализе потока управления , поскольку он часто представляет собой естественную линеаризацию потоков управления. Граф выше может представлять поток управления в фрагменте кода ниже, и естественно рассматривать этот код в порядке ABCD или ACBD, но неестественно использовать порядок ABDC или ACD B.

если ( А ) то { Б} еще { С}Д

Псевдокод

Рекурсивная реализация DFS: ^[5]

процедура DFS( G , v ) помечает v как обнаруженную для всех направленных ребер от v до w, которые находятся  в  G . adjacentEdges( v ) делает,  если вершина w не помечена как обнаруженная, то рекурсивно вызывает DFS( G , w )

Нерекурсивная реализация DFS с наихудшей сложностью пространства , с возможностью дублирования вершин в стеке: ^[6] ${\displaystyle O(|E|)}$

процедура DFS_iterative( G , v ) — пусть S будет стеком S .push( v ) пока  S не пусто do  v = S .pop() если  v не помечен как обнаруженный, то пометить v как обнаруженный для всех ребер от v до w  в  G .adjacentEdges( v ) do  S .push( w )

Пример графика, скопированный сверху

Эти две вариации DFS посещают соседей каждой вершины в порядке, противоположном друг другу: первый сосед v , посещенный рекурсивной вариацией, является первым в списке смежных ребер, тогда как в итеративной вариации первый посещенный сосед является последним в списке смежных ребер. Рекурсивная реализация посетит узлы из примера графа в следующем порядке: A, B, D, F, E, C, G. Нерекурсивная реализация посетит узлы как: A, E, F, B, D, C, G.

Нерекурсивная реализация похожа на поиск в ширину, но отличается от него двумя способами:

1. он использует стек вместо очереди, и
2. он откладывает проверку того, была ли обнаружена вершина, до тех пор, пока вершина не будет извлечена из стека, вместо того, чтобы выполнять эту проверку перед добавлением вершины.

Если G — дерево , замена очереди алгоритма поиска в ширину на стек даст алгоритм поиска в глубину. Для общих графов замена стека итеративной реализации поиска в глубину на очередь также даст алгоритм поиска в ширину, хотя и несколько нестандартный. ^[7]

Другая возможная реализация итеративного поиска в глубину использует стек итераторов списка соседей узла вместо стека узлов. Это дает тот же обход, что и рекурсивный DFS. ^[8]

процедура DFS_iterative( G , v ) — пусть S будет стеком пометить v как обнаруженный S .push(итератор G .adjacentEdges( v )) пока  S не пусто do  if  S .peek().hasNext() then  w = S .peek().next() если  w не помечен как обнаруженный , то пометить w как обнаруженный S .push(итератор G .adjacentEdges( w )) else  S .pop()

Приложения

Рандомизированный алгоритм, аналогичный поиску в глубину, используемый при создании лабиринта.

Алгоритмы, использующие поиск в глубину в качестве строительного блока, включают:

• Нахождение связанных компонентов .
• Топологическая сортировка .
• Нахождение 2-связных (ребро или вершина) компонентов.
• Нахождение 3-связных (ребро или вершина) компонентов.
• Нахождение мостов графа.
• Генерация слов для построения предельного множества группы .
• Нахождение сильно связанных компонентов .
• Определение того, находится ли вид ближе к тому или иному виду на филогенетическом дереве.
• Тестирование планарности . ^{[9] [10]}
• Решение головоломок, имеющих только одно решение, например, лабиринтов . (DFS можно адаптировать для поиска всех решений лабиринта, включив только узлы на текущем пути в посещаемый набор.)
• Генерация лабиринта может использовать рандомизированный DFS.
• Нахождение двусвязности в графах .
• Наследование престола разделено между королевствами Содружества . ^[11]

Сложность

Вычислительная сложность DFS была исследована Джоном Рейфом . Точнее, если задан граф , пусть будет порядком, вычисленным стандартным рекурсивным алгоритмом DFS. Этот порядок называется лексикографическим порядком поиска в глубину. Джон Рейф рассмотрел сложность вычисления лексикографического порядка поиска в глубину, заданного графом и источником. Решающая версия задачи (проверка того, встречается ли некоторая вершина u перед некоторой вершиной v в этом порядке) является P -полной , ^[12] что означает, что это «кошмар для параллельной обработки ». ^{[13] : 189} ${\displaystyle G}$ ${\displaystyle O=(v_{1},\dots ,v_{n})}$

Поиск в глубину (не обязательно лексикографический) может быть вычислен рандомизированным параллельным алгоритмом в классе сложности RNC . ^[14] По состоянию на 1997 год оставалось неизвестным, можно ли построить обход в глубину с помощью детерминированного параллельного алгоритма в классе сложности NC . ^[15]

Смотрите также

• Обход дерева (подробнее о прямом, прямом и обратном обходе в глубину)
• Поиск в ширину
• Итеративное углубление поиска в глубину
• Поиск игры

Примечания

1. Шарль Пьер Тремо (1859–1882) Политехническая школа Парижа (X:1876), французский инженер телеграфа
   , Публичная конференция, 2 декабря 2010 г. – профессор Жан Пеллетье-Тибер в Академии Макона (Бургундия – Франция) – (Реферат опубликован в Annals academic, март 2011 г. – ISSN  0980-6032)
2. Эвен, Шимон (2011), Графовые алгоритмы (2-е изд.), Cambridge University Press, стр. 46–48, ISBN 978-0-521-73653-4.
3. Седжвик, Роберт (2002), Алгоритмы в C++: Графовые алгоритмы (3-е изд.), Pearson Education, ISBN 978-0-201-36118-6.
4. Кормен, Томас Х., Чарльз Э. Лейзерсон и Рональд Л. Ривест. стр.606
5. Гудрич и Тамассия; Кормен, Лейзерсон, Ривест и Штейн
6. Страница 93, Разработка алгоритма, Клейнберг и Тардос
7. "Обход графа на основе стека ≠ поиск в глубину". 11011110.github.io . Получено 2020-06-10 .
8. Седжвик, Роберт (2010). Алгоритмы в Java. Эддисон-Уэсли. ISBN 978-0-201-36121-6. OCLC  837386973.
9. Хопкрофт, Джон ; Тарьян, Роберт Э. (1974), «Эффективное тестирование планарности» (PDF) , Журнал Ассоциации вычислительной техники , 21 (4): 549–568, doi : 10.1145/321850.321852, hdl : 1813/6011 , S2CID  6279825.
10. де Фрейссе, Х.; Оссона де Мендес, П .; Розенштиль, П. (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерной науки , 17 (5): 1017–1030, arXiv : math/0610935 , Bibcode : 2006math.....10935D, doi : 10.1142/S0129054106004248, S2CID  40107560.
11. Baccelli, Francois; Haji-Mirsadeghi, Mir-Omid; Khezeli, Ali (2018), «Вечные генеалогические деревья и динамика на унимодулярных случайных графах», в Sobieczky, Florian (ред.), Unimodularity in Randomly Generated Graphs: AMS Special Session, October 8–9, 2016, Denver, Colorado , Contemporary Mathematics, т. 719, Providence, Rhode Island: American Mathematical Society, стр. 85–127, arXiv : 1608.05940 , doi : 10.1090/conm/719/14471, MR  3880014, S2CID  119173820; см. пример 3.7, стр. 93
12. Рейф, Джон Х. (1985). «Поиск в глубину по своей сути последователен». Information Processing Letters . 20 (5): 229–234. doi :10.1016/0020-0190(85)90024-9.
13. Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Springer. Архивировано (PDF) из оригинала 2015-09-08.
14. Аггарвал, А.; Андерсон, Р.Дж. (1988), «Случайный алгоритм NC для поиска в глубину», Combinatorica , 8 (1): 1–12, doi :10.1007/BF02122548, MR  0951989, S2CID  29440871.
15. Каргер, Дэвид Р .; Мотвани, Раджив (1997), « Алгоритм ЧПУ для минимальных разрезов», SIAM Journal on Computing , 26 (1): 255–272, CiteSeerX 10.1.1.33.1701 , doi : 10.1137/S0097539794273083, MR  1431256 .

Ссылки

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest и Clifford Stein . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 22.3: Поиск в глубину, стр. 540–549. 
• Гудрич, Майкл Т.; Тамассиа , Роберто (2001), Разработка алгоритмов: основы, анализ и примеры из Интернета , Wiley, ISBN 0-471-38365-1
• Кляйнберг, Джон ; Тардос, Ева (2006), Разработка алгоритмов , Аддисон Уэсли, стр. 92–94.
• Кнут, Дональд Э. (1997), Искусство программирования, том 1. 3-е изд., Бостон: Addison-Wesley, ISBN 0-201-89683-4, OCLC  155842391, заархивировано из оригинала 2008-09-04 , извлечено 2008-02-12

Внешние ссылки

• Открытые структуры данных - Раздел 12.3.2 - Поиск в глубину, Пэт Морин
• Библиотека C++ Boost Graph: поиск в глубину
• Анимация поиска в глубину (для направленного графа)
• Поиск в глубину и в ширину: объяснение и код
• Иллюстрированное объяснение алгоритма поиска в глубину (реализации на Java и C++)
• YAGSBPL – библиотека C++ на основе шаблонов для поиска и планирования графов