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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Поиск источников: «Поиск в глубину» - новости · газеты · книги · ученый · JSTOR ( июль 2010 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Поиск в глубину
Порядок посещения узлов
Учебный класс	Алгоритм поиска
Структура данных	График
Пессимистический производительность	$O(\|V\|+\|E\|)$ для явных графов, пройденных без повторения, для неявных графов с фактором ветвления b, поиск которых ведется до глубины d $O(b^{d})$
Сложность пространства в наихудшем случае	$O(\|V\|)$ если весь граф пройден без повторения, O (самая длинная длина искомого пути) = для неявных графов без исключения повторяющихся узлов $O(bd)$

Алгоритмы поиска по графам и деревьям
α – β А * B * Возврат Луч Беллман – Форд Лучший первый Двунаправленный Борувка Филиал и граница BFS британский музей D * DFS Dijkstra Эдмондс Флойд – Уоршалл Поиск бахромы скалолазание ИДА* Итеративное углубление Джонсон Точка прыжка Крускал Лексикографическая BFS LPA * Prim SMA *
Списки
Алгоритмы графа Алгоритмы поиска Список алгоритмов графа
похожие темы
Динамическое программирование Обход графа Обход дерева Искать игры
v т е

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

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

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

Время и пространство анализа ДФС различается в зависимости от его области применения. В теоретической информатике, ДФС , как правило , используется для обхода всего графа, и занимает много времени , ^[4] линейный по размеру графа. В этих приложениях он также использует пространство в худшем случае для хранения стека вершин на текущем пути поиска, а также набора уже посещенных вершин. Таким образом, в этой настройке временные и пространственные границы такие же, как для поиска в ширину, и выбор того, какой из этих двух алгоритмов использовать, зависит в меньшей степени от их сложности и в большей степени от различных свойств порядка вершин, создаваемых двумя алгоритмами. . $O(|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.

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

Вывод поиска в глубину [ править ]

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

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

Заказ DFS [ править ]

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

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

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

Порядок вершин [ править ]

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

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

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

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

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

if ( A ), то { B} еще { C}D

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

Вход : граф G и вершина v графа G.

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

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

Процедура ДФС ( G , v ) является этикетка v как обнаружил для всех ориентированных ребер от V до W, которые  в  G .adjacentEdges ( v ) делать ,  если вершина ж не помечен как обнаружил затем рекурсивно называть ДФС ( G , ш )

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

Нерекурсивная реализация DFS с наихудшей пространственной сложностью , с возможностью дублирования вершин в стеке: ^[6] $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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

^ Шарль Пьер Тремо (1859–1882) Политехническая школа Парижа (X: 1876 г.), французский инженер телеграфа
на публичной конференции, 2 декабря 2010 г. - профессором Жаном Пеллетье-Тибер в Академии де Макон (Бургундия - Франция) - ( Резюме опубликовано в Академии Анналов, март 2011 - ISSN 0980-6032 )
^ Even, Shimon (2011), Graph Algorithms (2-е изд.), Cambridge University Press, стр. 46–48, ISBN 978-0-521-73653-4.
^ Седжвик, Роберт (2002), Алгоритмы в C ++: Graph Algorithms (3-е изд.), Pearson Education, ISBN 978-0-201-36118-6.
^ Кормен, Томас Х., Чарльз Э. Лейзерсон и Рональд Л. Ривест. стр.606
^ Гудрич и Тамассия; Кормен, Лейзерсон, Ривест и Штайн
^ Страница 93, Разработка алгоритмов, Клейнберг и Тардос
^ "Стековый обход графа St поиск в глубину" . 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 .
^ de Fraysseix, H .; Оссона де Мендес, П .; Розенштиль, П. (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерных наук , 17 (5): 1017–1030, arXiv : math / 0610935 , doi : 10.1142 / S0129054106004248.
^ Рейф, Джон Х. (1985). «Поиск в глубину по своей сути является последовательным». Письма об обработке информации . 20 (5). DOI : 10.1016 / 0020-0190 (85) 90024-9 .
^ Mehlhorn, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: The Basic Toolbox (PDF) . Springer.
^ Aggarwal, A .; Андерсон, RJ (1988), "Случайный NC алгоритм глубины первого поиска", Combinatorica , 8 (1): 1-12, DOI : 10.1007 / BF02122548 , МР 0951989 .
^ Каргер, Дэвид Р .; Мотвани, Райеи (1997), "Об ЧПУ алгоритм минимальных сокращений", SIAM журнал по вычислениям , 26 (1): 255-272, CiteSeerX 10.1.1.33.1701 , DOI : 10,1137 / S0097539794273083 , МР 1431256 .

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

Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. 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

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

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

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

[1] Шарль Пьер Тремо (1859–1882) Политехническая школа Парижа (X: 1876 г.), французский инженер телеграфа
на публичной конференции, 2 декабря 2010 г. - профессором Жаном Пеллетье-Тибер в Академии де Макон (Бургундия - Франция) - ( Резюме опубликовано в Академии Анналов, март 2011 - ISSN 0980-6032 )

[2] Even, Shimon (2011), Graph Algorithms (2-е изд.), Cambridge University Press, стр. 46–48, ISBN 978-0-521-73653-4.

[3] Седжвик, Роберт (2002), Алгоритмы в C ++: Graph Algorithms (3-е изд.), Pearson Education, ISBN 978-0-201-36118-6.

[4] Кормен, Томас Х., Чарльз Э. Лейзерсон и Рональд Л. Ривест. стр.606

[5] Гудрич и Тамассия; Кормен, Лейзерсон, Ривест и Штайн

[6] Страница 93, Разработка алгоритмов, Клейнберг и Тардос

[7] "Стековый обход графа St поиск в глубину" . 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 .

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

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

[mehlhorn-12] Mehlhorn, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: The Basic Toolbox (PDF) . Springer.

[13] Aggarwal, A .; Андерсон, RJ (1988), "Случайный NC алгоритм глубины первого поиска", Combinatorica , 8 (1): 1-12, DOI : 10.1007 / BF02122548 , МР 0951989 .

[14] Каргер, Дэвид Р .; Мотвани, Райеи (1997), "Об ЧПУ алгоритм минимальных сокращений", SIAM журнал по вычислениям , 26 (1): 255-272, CiteSeerX 10.1.1.33.1701 , DOI : 10,1137 / S0097539794273083 , МР 1431256 .

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