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

редактировать

Алгоритм поиска узлов графа в порядке их количества переходов от начального узла

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

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

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

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

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

Содержание

1 Псевдокод
- 1.1 Подробнее
- 1.2 Пример
2 Анализ
- 2.1 Сложность по времени и пространству
- 2.2 Полнота
3 Порядок BFS
4 Приложения
5 См. Также
6 Ссылки
7 Внешние ссылки

Псевдокод

Вход : Граф G и начальная вершина корня G

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

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

Подробнее

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

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

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

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

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

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

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

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

Пример

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

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

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

Анализ

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

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

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

При работе с графами, которые слишком велики для явного хранения (или бесконечны), более практично описывать сложность поиска в ширину другими терминами: найти узлы, которые находятся на расстоянии d от начальный узел (измеряется числом обходов ребер), BFS занимает O (b) времени и памяти, где b - «коэффициент ветвления » графа (средний исходящий градус).

Полнота

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

Упорядочивание BFS

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

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

Пусть $σ = (v 1,…, vn) {\ displaystyle \ sigma = (v_ {1}, \ dots, v_ {n})}$ ${\ displaystyle \ сигма = (v_ {1}, \ точки, v_ {n})}$ будет перечислением вершин $V {\ displaystyle V}$ $V$ . Перечисление $σ {\ displaystyle \ sigma}$ $\ sigma$ называется упорядочением BFS (с источником $v 1 {\ displaystyle v_ {1}}$ $v_ {1}$ ), если, для всех $1 < i ≤ n {\displaystyle 1$ ${\ displaystyle 1 <i \ leq n}$ , $vi {\ displaystyle v_ {i}}$ $v_ {i}$ - это вершина $w ∈ V ∖ {v 1,…, vi - 1} {\ displaystyle w \ in V \ setminus \ {v_ {1}, \ dots, v_ {i-1} \}}$ ${\ displaystyle w \ in V \ setminus \ {v_ {1}, \ точки, v_ {i-1} \}}$ такие, что $ν (v 1,…, vi - 1) (w) {\ displaystyle \ nu _ { (v_ {1}, \ dots, v_ {i-1})} (w)}$ ${\ displaystyle \ nu _ {(v_ {1}, \ dots, v_ {i-1})} (ш) }$ минимально. Эквивалентно, $σ {\ displaystyle \ sigma}$ $\ sigma$ является порядком BFS, если для всех $1 ≤ i < j < k ≤ n {\displaystyle 1\leq i$ ${\ displaystyle 1 \ leq i <j <k \ leq n}$ с $vi ∈ N (vk) ∖ N (vj) {\ displaystyle v_ {i} \ in N (v_ {k}) \ setminus N (v_ {j})}$ ${\ displaystyle v_ {i} \ in N (v_ {k}) \ setminus N (v_ {j})}$ , существует сосед $vm {\ displaystyle v_ {m }}$ $v_ {m}$ из $vj {\ displaystyle v_ {j}}$ $v_ {j}$ так, что $m < i {\displaystyle m$ ${\ displaystyle m <i}$ .

Applications

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

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

См. также

Ссылки

Внешние ссылки

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