Поиск в ширину - Breadth-first search
Порядок раскрытия узлов
| |
Класс | Алгоритм поиска |
---|---|
Структура данных | График |
Наихудшая производительность | |
Сложность пространства в наихудшем случае |
Алгоритмы поиска по графам и деревьям |
---|
Списки |
похожие темы |
![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/f9/Tic-tac-toe-game-tree.png/187px-Tic-tac-toe-game-tree.png)
Поиск в ширину ( BFS ) - это алгоритм поиска в древовидной структуре данных узла, который удовлетворяет заданному свойству. Он начинается с корня дерева и исследует все узлы на текущей глубине, прежде чем перейти к узлам на следующем уровне глубины. Дополнительная память, обычно очередь , необходима для отслеживания дочерних узлов, которые были обнаружены, но еще не исследованы.
Например, в эндшпиль шахматный движок может построить дерево игры из текущей позиции, применяя все возможные ходы, а также использование в ширину первого поиска , чтобы найти место для выигрыша белого цвета. Неявные деревья (такие как игровые деревья или другие деревья решения проблем) могут иметь бесконечный размер; Поиск в ширину гарантированно найдет узел решения, если он существует.
Напротив, (простой) поиск в глубину , который исследует ветвь узла как можно дальше, прежде чем выполнять обратное отслеживание и расширять другие узлы, может потеряться в бесконечной ветви и никогда не добраться до узла решения. Итеративный углубленный поиск в глубину позволяет избежать последнего недостатка за счет многократного изучения верхних частей дерева. С другой стороны, оба алгоритма в глубину обходятся без дополнительной памяти.
Поиск в ширину может быть обобщен на графы , если начальный узел (иногда называемый «ключ поиска») задан явно, и приняты меры предосторожности против повторения вершины дважды.
BFS и его приложение для нахождения компонент связности графов были изобретены в 1945 году Конрадом Цузе , в его (отвергнутой) докторской степени. докторскую диссертацию по языку программирования Планкалкюль , но она не была опубликована до 1972 года. Она была изобретена заново в 1959 году Эдвардом Ф. Муром , который использовал ее, чтобы найти кратчайший путь из лабиринта, а затем разработан Си Ю. Ли в алгоритм маршрутизации проводов. (опубликовано в 1961 г.).
Псевдокод
Входные данные : Граф G и начинает вершина корня из G
Выход : состояние цели. В родительских ссылках проследить кратчайший путь назад к корню
1 procedure BFS(G, root) is 2 let Q be a queue 3 label root as explored 4 Q.enqueue(root) 5 while Q is not empty do 6 v := Q.dequeue() 7 if v is the goal then 8 return v 9 for all edges from v to w in G.adjacentEdges(v) do 10 if w is not labeled as explored then 11 label w as explored 12 Q.enqueue(w)
Подробнее
Эта нерекурсивная реализация похожа на нерекурсивную реализацию поиска в глубину , но отличается от нее двумя способами:
- он использует очередь (First In First Out) вместо стека и
- он проверяет, была ли вершина исследована перед постановкой вершины в очередь, а не откладывает эту проверку до тех пор, пока вершина не будет исключена из очереди.
Если G - дерево , замена очереди этого алгоритма поиска в ширину на стек даст алгоритм поиска в глубину. Для общих графов замена стека реализации итеративного поиска в глубину очередью также создала бы алгоритм поиска в ширину, хотя и несколько нестандартный.
Q очередь содержит границу , по которой алгоритм в настоящее время на поиск.
Узлы можно пометить как исследованные, сохранив их в наборе или с помощью атрибута на каждом узле, в зависимости от реализации.
Обратите внимание, что слово « узел» обычно взаимозаменяемо со словом « вершина» .
Родительский атрибут каждого узла полезен для доступа к узлам в кратчайшем пути, например , путем отката от узла назначения до исходного узла после того , как BFS была запущена, и предшественники узлы были установлены.
Поиск в ширину дает так называемое дерево в ширину . Вы можете увидеть, как выглядит дерево в ширину, в следующем примере.
Пример
Ниже приведен пример дерева в ширину, полученного при запуске BFS в городах Германии, начиная с Франкфурта :
![](https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/MapGermanyGraph.svg/250px-MapGermanyGraph.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/6/63/GermanyBFS.svg/250px-GermanyBFS.svg.png)
Анализ
Сложность времени и пространства
Трудоемкость может быть выражено как , так как каждая вершина и каждое ребро будет изучаться в худшем случае. - количество вершин и - количество ребер в графе. Обратите внимание, что это значение может варьироваться от и , в зависимости от разреженности входного графа.
Когда количество вершин в графе известно заранее и используются дополнительные структуры данных, чтобы определить, какие вершины уже были добавлены в очередь, сложность пространства может быть выражена как , где - количество вершин. Это в дополнение к пространству, необходимому для самого графа, которое может варьироваться в зависимости от представления графа, используемого реализацией алгоритма.
При работе с графами, которые слишком велики для явного хранения (или бесконечны), более практично описывать сложность поиска в ширину в разных терминах: найти узлы, которые находятся на расстоянии d от начального узла (измеряется числом обходов ребер), BFS занимает O ( b d + 1 ) времени и памяти, где b - « коэффициент ветвления » графа (средняя степень выхода).
Полнота
При анализе алгоритмов, на входе поиска в ширину предполагается конечный граф, представленный в явном виде списка смежности , матрицу смежности , или аналогичное представление. Однако при применении методов обхода графа в искусственном интеллекте ввод может быть неявным представлением бесконечного графа. В этом контексте метод поиска описывается как завершенный, если гарантируется нахождение целевого состояния, если оно существует. Поиск в ширину завершен, а поиск в глубину - нет. При применении к бесконечным графам, представленным неявно, поиск в ширину в конечном итоге найдет целевое состояние, но поиск в глубину может потеряться в частях графа, которые не имеют целевого состояния, и никогда не вернуться.
Заказ BFS
Перечисление вершин графа называется упорядочением BFS, если это возможный результат применения BFS к этому графу.
Позвольте быть граф с вершинами. Напомним, это набор соседей . Позвольте быть списком различных элементов , для , позвольте быть наименьшим из таких, что является соседом , если такой существует, и быть в противном случае.
Позвольте быть перечисление вершин . Перечисление называется упорядочение BFS (с источником ) , если для всех , является вершиной таким образом, что является минимальным. Эквивалентное является упорядочение BFS , если для всех с , существует сосед из таких , что .
Приложения
Поиск в ширину можно использовать для решения многих задач теории графов, например:
- Копирование сборки мусора , алгоритм Чейни
- Нахождение кратчайшего пути между двумя узлами u и v с длиной пути, измеряемой количеством ребер (преимущество перед поиском в глубину )
- (Обратный) нумерация сеток Катхилла – Макки
- Метод Форда – Фулкерсона для вычисления максимального потока в потоковой сети
- Сериализация / десериализация двоичного дерева по сравнению с сериализацией в отсортированном порядке позволяет эффективно реконструировать дерево.
- Построение функции отказа от Ахо-Corasick картины согласовани.
- Проверка двудольности графа .
- Реализация параллельных алгоритмов вычисления транзитивного замыкания графа.
Смотрите также
- Поиск в глубину
- Итеративный поиск в глубину с углублением
- Структура уровней
- Лексикографический поиск в ширину
- Параллельный поиск в ширину
использованная литература
- Кнут, Дональд Э. (1997), Искусство компьютерного программирования Том 1. 3-е изд. , Бостон: Аддисон-Уэсли, ISBN 978-0-201-89683-1