Поиск в ширину - Википедия - Breadth-first search

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

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

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

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

BFS и его применение в поиске связанные компоненты графиков были изобретены в 1945 г. Конрад Зузе, в его (отклоненной) кандидатской диссертации. диссертация по Plankalkül язык программирования, но он не был опубликован до 1972 года.^[3] Он был изобретен заново в 1959 году Эдвард Ф. Мур, который использовал его, чтобы найти кратчайший путь из лабиринта,^[4]^[5] а затем был разработан К. Й. Ли в проводка алгоритм (опубликован в 1961 г.).^[6]

Псевдокод

Вход: График $грамм$ и начальная вершина $корень$ из $грамм$

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

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

Подробнее

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

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

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

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

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

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

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

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

Пример

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

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

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

Анализ

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

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

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

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

Полнота

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

Заказ BFS

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

Позволять ${ Displaystyle G = (V, E)}$ быть графом с ${ displaystyle n}$ вершины. Напомним, что ${ Displaystyle N (v)}$ это множество соседей ${ displaystyle v}$ .За ${ 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 infty}$ иначе.

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

Приложения

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

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

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

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

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

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

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

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

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

[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] Коппин, Б. (2004). Искусственный интеллект с подсветкой. Джонс и Бартлетт Обучение. С. 79–80.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

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