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

Поиск в глубину
	Order in which the nodes get expandedПорядок посещения узлов
Сорт	Алгоритм поиска
Структура данных	График
Худшая производительность	для явных графов, проходимых без повторений, для неявных графов с коэффициентом ветвления b, поиском на глубину d
Наихудшая пространственная сложность	если весь граф пройден без повторений, O (самая длинная длина искомого пути) = для неявных графов без исключения повторяющихся узлов
Оптимальный	нет (обычно не находит кратчайшие пути)

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

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

Свойства [ править ]

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

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

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

if (A) then {
    B
} else {
    C
}
D

Псевдокод [ править ]

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

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

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

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do 
                S.push(w)

Неориентированный граф с ребрами AB, BD, BF, FE, AC, CG, AE. — The example graph, copied from above

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

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

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

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

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

procedure DFS_iterative(G, v) is
    let S be a stack
    label v as discovered
    S.push(iterator of G.adjacentEdges(v))
    while S is not empty do
        if S.peek().hasNext() then
            w = S.peek().next()
            if w is not labeled as discovered then
                label w as discovered
                S.push(iterator of G.adjacentEdges(w))
        else
            S.pop()

Приложения [ править ]

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

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

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

Сложность [ править ]

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

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

См. также [ править ]

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

Примечания [ править ]

^ Шарль Пьер Тремо (1859–1882) Парижская политехническая школа (X: 1876), французский инженер телеграфа
на публичной конференции, 2 декабря 2010 г. – профессор Жан Пеллетье-Тиберт в Академии Макона (Бургундия, Франция) – (Тезисы опубликованы в журнале Annals Academic, март 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 . Проверено 10 июня 2020 г.
^ Седжвик, Роберт (2010). Алгоритмы на Java . Аддисон-Уэсли. ISBN 978-0-201-36121-6 . OCLC 837386973 .
^ Хопкрофт, Джон ; Тарьян, Роберт Э. (1974), «Эффективное тестирование планарности» (PDF) , Журнал Ассоциации вычислительной техники , 21 (4): 549–568, doi : 10.1145/321850.321852 , hdl : 1813/6011 , S2CID 6279825 .
^ де Фрейссе, Х.; Оссона де Мендес, П. ; Розенштиль, П. (2006), «Деревья Тремо и плоскостность», Международный журнал основ компьютерных наук , 17 (5): 1017–1030, arXiv : math/0610935 , Bibcode : 2006math.....10935D , doi : 10.1142/S0129054106004248 , S2CID 40107560 .
^ Бачелли, Франсуа; Гаджи-Мирсадеги, Мир-Омид; Хезели, Али (2018), «Вечные генеалогические деревья и динамика на унимодулярных случайных графах», Собечки, Флориан (ред.), Унимодулярность в случайно сгенерированных графах: специальная сессия AMS, 8–9 октября 2016 г., Денвер, Колорадо , Contemporary Математика, вып. 719, Провиденс, Род-Айленд: Американское математическое общество, стр. 85–127, arXiv : 1608.05940 , doi : 10.1090/conm/719/14471 , MR 3880014 , S2CID 119173820 ; см. пример 3.7, с. 93
^ Рейф, Джон Х. (1985). «Поиск в глубину по своей сути последователен». Письма об обработке информации . 20 (5): 229–234. дои : 10.1016/0020-0190(85)90024-9 .
^ Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Спрингер. Архивировано (PDF) из оригинала 8 сентября 2015 г.
^ Аггарвал, А.; Андерсон, Р.Дж. (1988), «Случайный алгоритм ЧПУ для поиска в глубину», Combinatorica , 8 (1): 1–12, doi : 10.1007/BF02122548 , MR 0951989 , S2CID 29440871 .
^ Каргер, Дэвид Р .; Мотвани, Раджив 1997), « Алгоритм минимальных разрезов», Journal on Computing 26 ( : CiteSeerX ( , 255–272 SIAM ЧПУ для , ) 1

Ссылки [ править ]

Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. 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-е изд. , Бостон: Аддисон-Уэсли, ISBN 0-201-89683-4 , OCLC 155842391 , заархивировано из оригинала 4 сентября 2008 г. , получено 12 февраля 2008 г.

Внешние ссылки [ править ]

[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 . Проверено 10 июня 2020 г.

[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] Бачелли, Франсуа; Гаджи-Мирсадеги, Мир-Омид; Хезели, Али (2018), «Вечные генеалогические деревья и динамика на унимодулярных случайных графах», Собечки, Флориан (ред.), Унимодулярность в случайно сгенерированных графах: специальная сессия AMS, 8–9 октября 2016 г., Денвер, Колорадо , Contemporary Математика, вып. 719, Провиденс, Род-Айленд: Американское математическое общество, стр. 85–127, arXiv : 1608.05940 , doi : 10.1090/conm/719/14471 , MR 3880014 , S2CID 119173820 ; см. пример 3.7, с. 93

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

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

[14] Аггарвал, А.; Андерсон, Р.Дж. (1988), «Случайный алгоритм ЧПУ для поиска в глубину», Combinatorica , 8 (1): 1–12, doi : 10.1007/BF02122548 , MR 0951989 , S2CID 29440871 .

[15] Каргер, Дэвид Р .; Мотвани, Раджив 1997), « Алгоритм минимальных разрезов», Journal on Computing 26 ( : CiteSeerX ( , 255–272 SIAM ЧПУ для , ) 1

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

v т и графов и деревьев Алгоритмы обхода
Поиск	обрезка a–b А* ИДА* МПА* СМА* Поиск по принципу «лучшее в первую очередь» Поиск луча Двунаправленный поиск Поиск в ширину Лексикографический Параллельно Б* Поиск в глубину Итеративное углубление Д* Граничный поиск Поиск точки прыжка Поиск по дереву Монте-Карло ССС*
Кратчайший путь	Беллман-Форд Дейкстры Флойд-Уоршалл Джонсонс Кратчайший путь быстрее Йен
Минимальное связующее дерево	Черника Крускала Прим Обратное удаление
Список алгоритмов поиска по графу