Поиск в ширину ( BFS ) — это алгоритм поиска в древовидной структуре данных узла, удовлетворяющего заданному свойству. Он начинается с корня дерева и исследует все узлы на текущей глубине , прежде чем перейти к узлам на следующем уровне глубины. Дополнительная память, обычно очередь , необходима для отслеживания дочерних узлов, которые были обнаружены, но еще не исследованы.
Например, в шахматном эндшпиле шахматный движок может построить дерево игры из текущей позиции, применяя все возможные ходы и используя поиск в ширину, чтобы найти выигрышную позицию для белых. Неявные деревья (например, игровые деревья или другие деревья решения задач) могут иметь бесконечный размер; поиск в ширину гарантированно находит узел решения [1], если он существует.
Напротив, (простой) поиск в глубину (DFS), который исследует ветвь узла как можно дальше, прежде чем возвращаться и расширять другие узлы, [2] может заблудиться в бесконечной ветке и никогда не добраться до узла решения. Итеративный поиск в глубину с углублением позволяет избежать последнего недостатка ценой повторного исследования верхних частей дерева. С другой стороны, оба алгоритма поиска в глубину обычно требуют гораздо меньше дополнительной памяти, чем поиск в ширину. [3]
Поиск в ширину можно обобщить как на неориентированные графы , так и на ориентированные графы с заданным начальным узлом (иногда называемым «ключом поиска»). [4] При поиске в пространстве состояний в искусственном интеллекте часто допускаются повторные поиски вершин, тогда как при теоретическом анализе алгоритмов, основанных на поиске в ширину, обычно принимаются меры предосторожности для предотвращения повторений.
BFS и ее применение для поиска компонентов связности графов были изобретены в 1945 году Конрадом Цузе в его (отвергнутой) докторской диссертации. диссертация по языку программирования Plankalkül , но она не была опубликована до 1972 года. [5] Он был заново изобретен в 1959 году Эдвардом Ф. Муром , который использовал его для поиска кратчайшего пути из лабиринта, [6] [7] и позже разработан С.А. Ли в алгоритм маршрутизации проводов (опубликован в 1961 г.). [8]
Входные данные : граф G и начальный корень вершины G.
Выход : Целевое состояние. Родительские ссылки прослеживают кратчайший путь обратно к корню [ 9]
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 ) do 10 , если w не помечено как исследованное , то 11 пометить w как исследованное12 w .parent := v 13 Q .enqueue( w )
Эта нерекурсивная реализация аналогична нерекурсивной реализации поиска в глубину , но отличается от нее двумя способами:
Если G — дерево , замена очереди этого алгоритма поиска в ширину стеком даст алгоритм поиска в глубину. Для общих графов замена стека реализации итеративного поиска в глубину очередью также приведет к созданию алгоритма поиска в ширину, хотя и несколько нестандартного. [10]
Очередь Q содержит границу, вдоль которой алгоритм выполняет поиск.
Узлы можно пометить как исследованные, сохранив их в наборе или по атрибуту на каждом узле, в зависимости от реализации.
Обратите внимание, что слово node обычно взаимозаменяемо со словом vertex .
Родительский атрибут каждого узла полезен для доступа к узлам по кратчайшему пути, например, путем возврата от узла назначения до начального узла, после запуска BFS и установки узлов-предшественников.
Поиск в ширину создает так называемое дерево в ширину . Вы можете увидеть, как выглядит дерево в ширину, в следующем примере.
Ниже приведен пример дерева в ширину, полученного путем запуска BFS в немецких городах, начиная с Франкфурта :
Временную сложность можно выразить как , поскольку в худшем случае будет исследована каждая вершина и каждое ребро. — количество вершин и — количество ребер в графе. Обратите внимание, что значение может варьироваться от и , в зависимости от того, насколько разрежен входной граф. [11]
Когда количество вершин в графе известно заранее и для определения того, какие вершины уже добавлены в очередь, используются дополнительные структуры данных, сложность пространства может быть выражена как , где – количество вершин. Это в дополнение к пространству, необходимому для самого графа, которое может варьироваться в зависимости от представления графа , используемого реализацией алгоритма.
При работе с графами, которые слишком велики для явного хранения (или бесконечны), практичнее описывать сложность поиска в ширину разными терминами: найти узлы, находящиеся на расстоянии d от начального узла (измеряется числом обходов ребер), BFS требует O ( b d + 1 ) времени и памяти, где b — « коэффициент ветвления » графа (средняя исходящая степень). [12] : 81
При анализе алгоритмов входными данными для поиска в ширину считается конечный граф, представленный в виде списка смежности , матрицы смежности или аналогичного представления. Однако при применении методов обхода графа в искусственном интеллекте входные данные могут быть неявным представлением бесконечного графа. В этом контексте метод поиска описывается как полный, если он гарантированно находит целевое состояние, если оно существует. Поиск в ширину завершен, а поиск в глубину — нет. При применении к бесконечным графам, представленным неявно, поиск в ширину в конечном итоге найдет целевое состояние, но поиск в глубину может потеряться в частях графа, которые не имеют целевого состояния и никогда не возвращаются. [13]
Перечисление вершин графа называется BFS-упорядочением, если оно является возможным результатом применения BFS к этому графу.
Пусть — граф с вершинами. Напомним, что это множество соседей . Позвольте быть списком различных элементов , для , пусть будет наименьший такой, который является соседом , если такой существует, и быть в противном случае.
Пусть – перечисление вершин . Перечисление называется упорядочением BFS (с source ) , если для всех вершина минимальна . Эквивалентно, это упорядочение BFS, если для всех с существует сосед такого, что .
Поиск в ширину можно использовать для решения многих задач теории графов, например: