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

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

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

Например, в шахматном эндшпиле шахматный движок может построить дерево игры из текущей позиции, применяя все возможные ходы, и использовать поиск в ширину, чтобы найти выигрышную позицию для белых. Неявные деревья (такие как игровые деревья или другие деревья решения проблем) могут быть бесконечного размера; поиск в ширину гарантированно найдет узел решения ^[1], если он существует.

Напротив, (обычный) поиск в глубину (DFS), который исследует ветвь узла как можно дальше, прежде чем возвращаться и расширять другие узлы, ^[2] может потеряться в бесконечной ветви и никогда не добраться до узла решения. Итеративный поиск в глубину с углублением избегает последнего недостатка ценой повторного исследования верхних частей дерева. С другой стороны, оба алгоритма поиска в глубину обычно требуют гораздо меньше дополнительной памяти, чем поиск в ширину. ^[3]

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

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

Входные данные : граф G и начальная вершина- корень графа G.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Перечисление вершин графа называется упорядочением 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 я}$${\displaystyle v_{i}}$${\displaystyle v}$${\displaystyle я}$${\displaystyle \infty}$

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

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

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

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

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