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

Поиск в ширину
Порядок расширения узлов
Порядок раскрытия узлов
Класс Алгоритм поиска
Структура данных График
Наихудшая производительность
Сложность пространства в наихудшем случае
Анимированный пример поиска в ширину. Черный: исследован, серый: в очереди на изучение позже
Верхняя часть дерева игры в крестики-нолики

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

Подробнее

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

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

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

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

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

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

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

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

Пример

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

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

Анализ

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

Трудоемкость может быть выражено как , так как каждая вершина и каждое ребро будет изучаться в худшем случае. - количество вершин и - количество ребер в графе. Обратите внимание, что это значение может варьироваться от и , в зависимости от разреженности входного графа.

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

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

Полнота

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

Заказ BFS

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

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

Позвольте быть перечисление вершин . Перечисление называется упорядочение BFS (с источником ) , если для всех , является вершиной таким образом, что является минимальным. Эквивалентное является упорядочение BFS , если для всех с , существует сосед из таких , что .

Приложения

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

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

использованная литература

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