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

Поиск в ширину
Порядок расширения узлов
Порядок, в котором узлы раскрываются
Учебный классАлгоритм поиска
Структура данныхГрафик
Худший случай спектакль
Худший случай космическая сложность
Анимированный пример поиска в ширину

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

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

BFS и его применение в поиске связанные компоненты графиков были изобретены в 1945 г. Конрад Зузе, в его (отклоненной) кандидатской диссертации. диссертация по Plankalkül язык программирования, но он не был опубликован до 1972 года.[3] Он был изобретен заново в 1959 году Эдвард Ф. Мур, который использовал его, чтобы найти кратчайший путь из лабиринта,[4][5] а затем был разработан К. Й. Ли в проводка алгоритм (опубликован в 1961 г.).[6]

Псевдокод

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

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

 1  процедура BFS (грамм, корень) является 2 лет Q быть лейблом очереди 3 корень как обнаружено 4 Q.enqueue (корень) 5      пока Q не пусто делать 6          v := Q.dequeue () 7 если v это цель тогда 8              возвращаться v 9          для всех края от v к ш в грамм.adjacentEdges (v) делать10              если ш не помечено как обнаруженное тогда11 этикетка ш как обнаружено12 Q.enqueue (ш)

Подробнее

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

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

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

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

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

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

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

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

Пример

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

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

Анализ

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

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

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

При работе с графами, которые слишком велики для явного хранения (или бесконечны), более практично описывать сложность поиска в ширину другими терминами: найти узлы, которые находятся на расстоянии d от начального узла (измеряется количеством обходов ребер), BFS берет О(бd + 1) время и память, где б это "фактор ветвления "графика (средняя степень выхода).[10]:81

Полнота

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

Заказ BFS

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

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

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

Приложения

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

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

Рекомендации

  1. ^ «Спецификация теста Graph500 (оценка производительности суперкомпьютера)». Graph500.org, 2010. Архивировано с оригинал на 2015-03-26. Получено 2015-03-15.
  2. ^ Cormen Thomas H .; и другие. (2009). «22,3». Введение в алгоритмы. MIT Press.
  3. ^ Зузе, Конрад (1972), Der Plankalkül (на немецком языке), Интернет-архив Конрада Цузе. См. Стр. 96–105 связанного файла pdf (внутренняя нумерация 2,47–2,56).
  4. ^ Мур, Эдвард Ф. (1959). «Кратчайший путь через лабиринт». Материалы Международного симпозиума по теории переключения.. Издательство Гарвардского университета. С. 285–292. Цитируется Корменом, Лейзерсоном, Ривестом и Штайном.
  5. ^ Скиена, Стивен (2008). «Сортировка и поиск». Руководство по разработке алгоритмов. Springer. п. 480. Bibcode:2008adm..book ..... S. Дои:10.1007/978-1-84800-070-4_4. ISBN  978-1-84800-069-8.
  6. ^ Ли, К. Ю. (1961). «Алгоритм соединения путей и его приложения». Операции IRE на электронных компьютерах. Дои:10.1109 / TEC.1961.5219222.
  7. ^ Кормен, Томас Х. "22.2 Поиск в ширину". Введение в алгоритмы. ISBN  978-81-203-4007-7. OCLC  1006880283.
  8. ^ «Обход графа на основе стека ≠ поиск в глубину». 11011110.github.io. Получено 2020-06-10.
  9. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. «22.2 Поиск в ширину». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 531–539. ISBN  0-262-03293-7.
  10. ^ Рассел, Стюарт; Норвиг, Питер (2003) [1995]. Искусственный интеллект: современный подход (2-е изд.). Прентис Холл. ISBN  978-0137903955.
  11. ^ Коппин, Б. (2004). Искусственный интеллект с подсветкой. Джонс и Бартлетт Обучение. С. 79–80.
  12. ^ Азиз, Аднан; Пракаш, Амит (2010). «4. Алгоритмы на графах». Алгоритмы собеседований. п. 144. ISBN  978-1453792995.

внешняя ссылка