Введение

Алгоритм поиска узлов графа

Поиск в ширину (BFS) — это алгоритм поиска в древовидной структуре данных узла, удовлетворяющего заданному условию. Он начинается с корня дерева и исследует все узлы на текущем уровне глубины, прежде чем переходить к узлам следующего уровня. Для отслеживания дочерних узлов, которые были обнаружены, но еще не исследованы, требуется дополнительная память, обычно очередь. Например, в шахматной эндшпиле шахматный движок может построить дерево игры из текущей позиции, применяя все возможные ходы, и использовать поиск в ширину для нахождения выигрышной позиции для белых. Неявные деревья (такие как деревья игры или другие деревья решения задач) могут быть бесконечного размера; поиск в ширину гарантированно найдет узел решения, если он существует. В отличие от этого, (обычный) поиск в глубину (DFS), который исследует ветвь узла как можно глубже, прежде чем возвращаться и расширять другие узлы, может застрять в бесконечной ветви и никогда не достичь узла решения. Итеративное углубление поиска в глубину позволяет избежать этого недостатка ценой повторного исследования верхних частей дерева. С другой стороны, оба алгоритма поиска в глубину обычно требуют значительно меньше дополнительной памяти, чем поиск в ширину. Поиск в ширину может быть обобщен как для неориентированных, так и для ориентированных графов с заданным начальным узлом (иногда называемым «ключом поиска»). В поиске пространства состояний в искусственном интеллекте часто допускаются повторные посещения вершин, в то время как в теоретическом анализе алгоритмов, основанных на поиске в ширину, обычно принимаются меры предосторожности для предотвращения повторений. Алгоритм BFS и его применение для поиска связных компонент графов были изобретены в 1945 году Конрадом Цузе в его (отклоненной) докторской диссертации по языку программирования Plankalkül, но она не была опубликована до 1972 года. Он был повторно изобретен в 1959 году Эдвардом Ф. Муром, который использовал его для поиска кратчайшего пути из лабиринта, а позже разработан Си Й. Ли в алгоритм трассировки соединений (опубликован в 1961 году).

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

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

Полная информация

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

Заказ BFS

Перечисление вершин графа называется BFS-порядком, если оно может быть получено в результате применения алгоритма BFS к этому графу. Пусть G – граф с n вершинами. Напомним, что N(v) – множество соседей вершины v. Пусть L – список различных элементов из V, и для каждого i, пусть f(i) – наименьший элемент из V, такой что f(i) является соседом L[i], если такой элемент существует, и иначе – бесконечность. Пусть L – перечисление вершин графа G. Перечисление L называется BFS-порядком (с источником) если для всех i, L[i] – вершина, для которой f(i) минимально. Эквивалентно, L является BFS-порядком, если для всех i > 0 существует сосед v вершины L[i], такой что v = L[j] для некоторого j < i.