Поиск в глубину - Depth-first search

Поиск в глубину
	Порядок посещения узлов
Учебный класс	Алгоритм поиска
Структура данных	График
Худший случай спектакль	для явных графов, пройденных без повторения, для неявных графов с фактором ветвления б искал до глубины d
Худший случай космическая сложность	если весь граф пройден без повторения, O (самая длинная длина искомого пути) = для неявных графов без исключения повторяющихся узлов

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

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

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

В время и Космос Анализ DFS различается в зависимости от области его применения. В теоретической информатике DFS обычно используется для обхода всего графа и требует времени. ${ Displaystyle O (| V | + | E |)}$ ,^[4] линейный по размеру графика. В этих приложениях также используется пространство ${ 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.

Итеративное углубление - это один из способов избежать этого бесконечного цикла и охватить все узлы.

Вывод поиска в глубину

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

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

Заказ DFS

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

Позволять ${ Displaystyle G = (V, E)}$ быть графом с ${ displaystyle n}$ вершины. За ${ displaystyle sigma = (v_ {1}, dots, v_ {m})}$ быть списком отдельных элементов ${ displaystyle V}$ , за ${ displaystyle v in V setminus {v_ {1}, dots, v_ {m} }}$ , позволять ${ displaystyle nu _ { sigma} (v)}$ быть величайшим ${ displaystyle i}$ такой, что ${ displaystyle v_ {i}}$ является соседом ${ displaystyle v}$ , если такой ${ displaystyle i}$ существует, и быть ${ displaystyle 0}$ иначе.

Позволять ${ displaystyle sigma = (v_ {1}, dots, v_ {n})}$ - перечисление вершин ${ displaystyle V}$ .Перечисление ${ displaystyle sigma}$ называется порядком DFS (с источником ${ displaystyle v_ {1}}$ ) если для всех ${ Displaystyle 1 <я Leq п}$ , ${ displaystyle v_ {i}}$ это вершина ${ displaystyle w in V setminus {v_ {1}, dots, v_ {i-1} }}$ такой, что ${ Displaystyle ню _ {(v_ {1}, точки, v_ {я-1})} (ш)}$ является максимальным. Напомним, что ${ Displaystyle N (v)}$ это множество соседей ${ displaystyle v}$ . Эквивалентно, ${ displaystyle sigma}$ это порядок DFS, если для всех ${ Displaystyle 1 Leq я$ с ${ displaystyle v_ {i} in N (v_ {k}) setminus N (v_ {j})}$ , существует сосед ${ displaystyle v_ {m}}$ из ${ displaystyle v_ {j}}$ такой, что ${ Displaystyle я <м$ .

Порядок вершин

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

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

Для бинарных деревьев есть дополнительно в порядке и обратный порядок.

Например, при поиске в ориентированном графе ниже, начиная с узла A, последовательность обходов будет либо A B D B A C A, либо A C D C A B A (выбор первого посещения B или C из A зависит от алгоритма). Обратите внимание, что здесь включаются повторные посещения в форме возврата к узлу, чтобы проверить, есть ли у него еще не посещенные соседи (даже если обнаружено, что их нет). Таким образом, возможные предварительные заказы - это A B D C и A C D B, в то время как возможные последующие заказы - это D B C A и D C B A, а возможные обратные последующие заказы - это A C B D и A B C D.

Ориентированный граф с ребрами AB, BD, AC, CD

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

если (А) тогда { B} еще { C}D

Псевдокод

Вход: График грамм и вершина v из G

Выход: Все вершины достижимы из v помечено как обнаруженное

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

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

Порядок, в котором вершины обнаруживаются этим алгоритмом, называется порядком. лексикографический порядок.^{[нужна цитата ]}

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

процедура DFS_iterative (грамм, v) является    позволять S быть стеком S.толкать(v)    пока S не пусто делать        v = S.pop () если v не помечено как обнаруженное тогда            метка v как обнаружено для всех края от v к ш в грамм.adjacentEdges (v) делать                 S.толкать(ш)

Неориентированный граф с ребрами AB, BD, BF, FE, AC, CG, AE

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

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

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

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

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

процедура DFS_iterative (грамм, v) является    позволять S быть стеком S.push (итератор грамм.adjacentEdges (v))    пока S не пусто делать        если S.peek (). hasNext () тогда            ш = S.peek (). следующий () если ш не помечен как обнаруженный тогда                метка ш как обнаружено S.push (итератор грамм.adjacentEdges (ш))        еще            S.pop ()

Приложения

Воспроизвести медиа

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

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

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

Сложность

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

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

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

Обход дерева (для получения подробной информации о предварительном, последовательном и последующем обходе в глубину)
Поиск в ширину
Итеративный поиск в глубину с углублением
Искать игры

Примечания

^ Шарль Пьер Тремо (1859–1882) Политехническая школа Парижа (X: 1876), французский инженер телеграфа
in Public Conference, 2 декабря 2010 г. - проф. Жан Пеллетье-Тибер в Académie de Macon (Бургундия, Франция) - (Резюме опубликовано в Академической Академии Анналов, март 2011 г. - ISSN 0980-6032 )
^ Эвен, Шимон (2011), Графические алгоритмы (2-е изд.), Cambridge University Press, стр. 46–48, ISBN 978-0-521-73653-4.
^ Седжвик, Роберт (2002), Алгоритмы в C ++: алгоритмы графов (3-е изд.), Pearson Education, ISBN 978-0-201-36118-6.
^ Кормен, Томас Х., Чарльз Э. Лейзерсон и Рональд Л. Ривест. стр.606
^ Гудрич и Тамассия; Кормен, Лейзерсон, Ривест и Штайн
^ Стр. 93, Разработка алгоритмов, Клейнберг и Тардос
^ «Стековый обход графа ≠ поиск в глубину». 11011110.github.io. Получено 2020-06-10.
^ Седжвик, Роберт (2010). Алгоритмы на Java. Эддисон-Уэсли. ISBN 978-0-201-36121-6. OCLC 837386973.
^ Хопкрофт, Джон; Тарджан, Роберт Э. (1974), «Эффективное тестирование планарности» (PDF), Журнал Ассоциации вычислительной техники, 21 (4): 549–568, Дои:10.1145/321850.321852.
^ de Fraysseix, H .; Оссона де Мендес, П.; Розенштиль, П. (2006), «Деревья Тремо и планарность», Международный журнал основ информатики, 17 (5): 1017–1030, arXiv:математика / 0610935, Дои:10.1142 / S0129054106004248.
^ Рейф, Джон Х. (1985). «Поиск в глубину по своей сути является последовательным». Письма об обработке информации. 20 (5). Дои:10.1016/0020-0190(85)90024-9.
^ Мельхорн, Курт; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF). Springer.
^ Aggarwal, A .; Андерсон, Р. Дж. (1988), «Случайный NC алгоритм поиска в глубину », Комбинаторика, 8 (1): 1–12, Дои:10.1007 / BF02122548, МИСТЕР 0951989.
^ Каргер, Дэвид Р.; Мотвани, Раджив (1997), "An NC алгоритм минимальных разрезов », SIAM Журнал по вычислениям, 26 (1): 255–272, CiteSeerX 10.1.1.33.1701, Дои:10.1137 / S0097539794273083, МИСТЕР 1431256.

внешняя ссылка

[1] Шарль Пьер Тремо (1859–1882) Политехническая школа Парижа (X: 1876), французский инженер телеграфа
in Public Conference, 2 декабря 2010 г. - проф. Жан Пеллетье-Тибер в Académie de Macon (Бургундия, Франция) - (Резюме опубликовано в Академической Академии Анналов, март 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, Дои:10.1145/321850.321852.

[10] Fraysseix, H .; Оссона де Мендес, П.; Розенштиль, П. (2006), «Деревья Тремо и планарность», Международный журнал основ информатики, 17 (5): 1017–1030, arXiv:математика / 0610935, Дои:10.1142 / S0129054106004248.

[11] Рейф, Джон Х. (1985). «Поиск в глубину по своей сути является последовательным». Письма об обработке информации. 20 (5). Дои:10.1016/0020-0190(85)90024-9.

[mehlhorn-12] Мельхорн, Курт; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF). Springer.

[13] Aggarwal, A .; Андерсон, Р. Дж. (1988), «Случайный NC алгоритм поиска в глубину », Комбинаторика, 8 (1): 1–12, Дои:10.1007 / BF02122548, МИСТЕР 0951989.

[14] Каргер, Дэвид Р.; Мотвани, Раджив (1997), "An NC алгоритм минимальных разрезов », SIAM Журнал по вычислениям, 26 (1): 255–272, CiteSeerX 10.1.1.33.1701, Дои:10.1137 / S0097539794273083, МИСТЕР 1431256.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Структуры данных и алгоритмы
Структуры данных	Множество Ассоциативный массив Дерево двоичного поиска Фенвик Дерево График Хеш-таблица Куча Связанный список Очередь Сегментное дерево Куча Нить Дерево Trie
Алгоритмы	Возврат Бинарный поиск Поиск в ширину Поиск в глубину Разделяй и властвуй Динамическое программирование Складывать Жадный Минимакс Рекурсия Сортировка Потоковое Линия развертки Топологическая сортировка