Поиск в ширину - Breadth-first search

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

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

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

Поиск в ширину (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 (ш)

Подробнее

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

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

Если грамм это дерево, замена очереди этого алгоритма поиска в ширину стеком даст алгоритм поиска в глубину. Для общих графов замена стека реализации итеративного поиска в глубину очередью также создала бы алгоритм поиска в ширину, хотя и несколько нестандартный.^[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<i\leq n}$, ${\displaystyle v_{i}}$ это вершина ${\displaystyle w\in V\setminus \{v_{1},\dots ,v_{i-1}\}}$ такой, что ${\displaystyle \nu _{(v_{1},\dots ,v_{i-1})}(w)}$ минимально. Эквивалентно ${\displaystyle \sigma }$ является порядком BFS, если для всех ${\displaystyle 1\leq i<j<k\leq n}$ с ${\displaystyle v_{i}\in N(v_{k})\setminus N(v_{j})}$, существует сосед ${\displaystyle v_{m}}$ из ${\displaystyle v_{j}}$ такой, что ${\displaystyle m<i}$.

Приложения

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

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

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

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

Рекомендации

1. «Спецификация теста Graph500 (оценка производительности суперкомпьютера)». Graph500.org, 2010. Архивировано с оригинал на 2015-03-26. Получено 2015-03-15.
2. Cormen Thomas H .; и другие. (2009). «22,3». Введение в алгоритмы. MIT Press.
3. Зузе, Конрад (1972), Der Plankalkül (на немецком языке), Интернет-архив Конрада Цузе. См. Стр. 96–105 связанного файла pdf (внутренняя нумерация 2,47–2,56).
4. Мур, Эдвард Ф. (1959). «Кратчайший путь через лабиринт». Материалы Международного симпозиума по теории переключения.. Издательство Гарвардского университета. С. 285–292. Цитируется Корменом, Лейзерсоном, Ривестом и Штайном.
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.
9. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. «22.2 Поиск в ширину». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 531–539. ISBN  0-262-03293-7.
10. Рассел, Стюарт; Норвиг, Питер (2003) [1995]. Искусственный интеллект: современный подход (2-е изд.). Прентис Холл. ISBN  978-0137903955.
11. Коппин, Б. (2004). Искусственный интеллект с подсветкой. Джонс и Бартлетт Обучение. С. 79–80.
12. Азиз, Аднан; Пракаш, Амит (2010). «4. Алгоритмы на графах». Алгоритмы собеседований. п. 144. ISBN  978-1453792995.

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

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

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