Поиск в ширину

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

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

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

Анимированный пример поиска в ширину

Поиск в ширину ( BFS ) - это алгоритм для обхода или поиска структур данных в виде дерева или графа . Он начинается с корня дерева (или некоторого произвольного узла графа, иногда называемого «ключом поиска» ^[1] ), и исследует все соседние узлы на текущей глубине, прежде чем перейти к узлам на следующей уровень глубины.

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

BFS и его приложение для нахождения компонент связности графов были изобретены в 1945 году Конрадом Цузе , в его (отвергнутой) докторской степени. докторскую диссертацию по языку программирования Планкалкюль , но она не была опубликована до 1972 года. ^[3] Он был заново изобретен в 1959 году Эдвардом Ф. Муром , который использовал его для поиска кратчайшего пути из лабиринта ^[4]^[5] и позже разработан CY Lee в алгоритм маршрутизации проводов (опубликован в 1961 г.). ^[6]

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

Входные данные : Граф $G$ и начинает вершина $корня$ из $G$

Выход : состояние цели. В родительских ссылках проследить кратчайший путь назад к $корню$ ^[7]

1 процедура BFS ( G , root ) равна 2, пусть Q - очередь 3 метка корень как обнаруженный 4 Q .enqueue ( корень ) 5, пока  Q не пусто do 6 v  : = Q .dequeue () 7, если  v - цель, то 8 вернуть  v 9 для всех ребер от v до w  в  G. AdjacentEdges ( v ) сделать
10, если  w не помечено как обнаруженное, тогда
11 пометить w как обнаруженное12 Q .enqueue ( ж )

Подробнее [ править ]

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

он использует очередь (First In First Out) вместо стека и
он проверяет, была ли обнаружена вершина перед постановкой вершины в очередь, а не откладывает эту проверку до тех пор, пока вершина не будет исключена из очереди.

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

Q очередь содержит границу , по которой алгоритм в настоящее время на поиск.

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

Обратите внимание, что слово « узел» обычно взаимозаменяемо со словом « вершина» .

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

Поиск в ширину дает так называемое дерево в ширину . Вы можете увидеть, как выглядит дерево в ширину, в следующем примере.

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

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

Пример карты Южной Германии с некоторыми связями между городами

Дерево в ширину, полученное при запуске BFS на данной карте и запуске во Франкфурте.

Анализ [ править ]

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

Трудоемкость может быть выражено как , так как каждая вершина и каждое ребро будет изучаться в худшем случае. - количество вершин и - количество ребер в графе. Обратите внимание, что это значение может варьироваться от и , в зависимости от разреженности входного графика. ^[9] ${\ Displaystyle O (| V | + | E |)}$ ${\ displaystyle | V |}$ ${\ displaystyle | E |}$ ${\ Displaystyle O (| E |)}$ $O(1)$ $O(|V|^{2})$

Когда количество вершин в графе известно заранее и используются дополнительные структуры данных, чтобы определить, какие вершины уже были добавлены в очередь, сложность пространства может быть выражена как , где - количество вершин. Это в дополнение к пространству, необходимому для самого графа, которое может варьироваться в зависимости от представления графа, используемого реализацией алгоритма. $O(|V|)$ $|V|$

При работе с графами, которые слишком велики для явного хранения (или бесконечны), более практично описывать сложность поиска в ширину другими терминами: найти узлы, которые находятся на расстоянии $d$ от начального узла (измеряется числом обходов ребер), BFS занимает $O (b d + 1)$ времени и памяти, где $b$ - « коэффициент ветвления » графа (средняя степень выхода). ^[10]^{: 81}

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

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

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

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

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

Позвольте быть перечисление вершин . Перечисление называется упорядочение BFS (с источником ) , если для всех , является вершиной таким образом, что является минимальным. Эквивалентное является упорядочение BFS , если для всех с , существует сосед из таких , что . $\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)$ $\sigma$ $1\leq i<j<k\leq n$ $v_{i}\in N(v_{k})\setminus N(v_{j})$ $v_{m}$ $v_{j}$ $m<i$

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

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

Копирование сборки мусора , алгоритм Чейни
Нахождение кратчайшего пути между двумя узлами u и v с длиной пути, измеряемой числом ребер (преимущество перед поиском в глубину ) ^[12]
(Обратный) нумерация сеток Катхилла – Макки
Метод Форда – Фулкерсона для вычисления максимального потока в потоковой сети
Сериализация / десериализация двоичного дерева по сравнению с сериализацией в отсортированном порядке позволяет эффективно реконструировать дерево.
Построение функции отказа от Ахо-Corasick картины согласовани.
Проверка двудольности графа .

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

Поиск в глубину
Итеративный поиск в глубину с углублением
Структура уровней
Лексикографический поиск в ширину
Параллельный поиск в ширину

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

^ «Спецификация теста Graph500 (оценка производительности суперкомпьютера)» . Graph500.org, 2010. Архивировано из оригинала на 2015-03-26 . Проверено 15 марта 2015 .
^ Cormen Thomas H .; и другие. (2009). «22,3». Введение в алгоритмы . MIT Press.
^ Цузе, Конрад (1972), Der Plankalkül (на немецком языке), Интернет-архив Конрада Цузе. См. Стр. 96–105 связанного файла pdf (внутренняя нумерация 2,47–2,56).
^ Мур, Эдвард Ф. (1959). «Кратчайший путь через лабиринт». Материалы Международного симпозиума по теории переключения . Издательство Гарвардского университета. С. 285–292. Цитируется Корменом, Лейзерсоном, Ривестом и Штайном.
^ Skiena, Стивен (2008). «Сортировка и поиск». Руководство по разработке алгоритмов . Springer. п. 480. Bibcode : 2008adm..book ..... S . DOI : 10.1007 / 978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.
^ Ли, CY (1961). «Алгоритм соединения путей и его приложения». Операции IRE на электронных компьютерах . DOI : 10.1109 / TEC.1961.5219222 .
^ Кормен, Томас Х. "Поиск в ширину 22.2". Введение в алгоритмы . ISBN 978-81-203-4007-7. OCLC 1006880283 .
^ «Обход графа на основе стека ≠ поиск в глубину» . 11011110.github.io . Проверено 10 июня 2020 .
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «22.2 Поиск в ширину». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 531–539. ISBN 0-262-03293-7.
^ Рассел, Стюарт ; Норвиг, Питер (2003) [1995]. Искусственный интеллект: современный подход (2-е изд.). Прентис Холл. ISBN 978-0137903955.
^ Coppin, B. (2004). Искусственный интеллект с подсветкой. Джонс и Бартлетт Обучение. С. 79–80.
^ Азиз, Аднан; Пракаш, Амит (2010). «4. Алгоритмы на графах». Алгоритмы собеседований . п. 144. ISBN 978-1453792995.

Кнут, Дональд Э. (1997), Искусство компьютерного программирования Том 1. 3-е изд. , Бостон: Аддисон-Уэсли, ISBN 978-0-201-89683-1

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

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

Структуры открытых данных - Раздел 12.3.1 - Поиск в ширину , Пат Морин
Упрощенный поиск в ширину

[1] «Спецификация теста Graph500 (оценка производительности суперкомпьютера)» . Graph500.org, 2010. Архивировано из оригинала на 2015-03-26 . Проверено 15 марта 2015 .

[2] Cormen Thomas H .; и другие. (2009). «22,3». Введение в алгоритмы . MIT Press.

[:0-3] Цузе, Конрад (1972), Der Plankalkül (на немецком языке), Интернет-архив Конрада Цузе. См. Стр. 96–105 связанного файла pdf (внутренняя нумерация 2,47–2,56).

[4] Мур, Эдвард Ф. (1959). «Кратчайший путь через лабиринт». Материалы Международного симпозиума по теории переключения . Издательство Гарвардского университета. С. 285–292. Цитируется Корменом, Лейзерсоном, Ривестом и Штайном.

[skiena-5] Skiena, Стивен (2008). «Сортировка и поиск». Руководство по разработке алгоритмов . Springer. п. 480. Bibcode : 2008adm..book ..... S . DOI : 10.1007 / 978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.

[6] Ли, CY (1961). «Алгоритм соединения путей и его приложения». Операции IRE на электронных компьютерах . DOI : 10.1109 / TEC.1961.5219222 .

[7] Кормен, Томас Х. "Поиск в ширину 22.2". Введение в алгоритмы . ISBN 978-81-203-4007-7. OCLC 1006880283 .

[8] «Обход графа на основе стека ≠ поиск в глубину» . 11011110.github.io . Проверено 10 июня 2020 .

[clrs-9] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «22.2 Поиск в ширину». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 531–539. ISBN 0-262-03293-7.

[10] Рассел, Стюарт ; Норвиг, Питер (2003) [1995]. Искусственный интеллект: современный подход (2-е изд.). Прентис Холл. ISBN 978-0137903955.

[coppin-11] Coppin, B. (2004). Искусственный интеллект с подсветкой. Джонс и Бартлетт Обучение. С. 79–80.

[12] Азиз, Аднан; Пракаш, Амит (2010). «4. Алгоритмы на графах». Алгоритмы собеседований . п. 144. ISBN 978-1453792995.

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