Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
В рубрике LeetCode на прошлых выходных мы подробно описали поиск в глубину и поиск с возвратом, поэтому сегодня мы продолжим эту тему и поговорим с вами о другой ветви алгоритма поиска, поиске в ширину.
Английский поиск в ширину — это поиск в ширину, сокращенно bfs. В отличие от поиска в глубину, английский язык, естественно, является поиском в глубину, сокращенно dfs. Поэтому, если вы читаете мой код или чей-то еще код и сталкиваетесь с функцией под названием bfs или dfs, если вы можете вспомнить эти сокращения, вы поймете, что они означают.
бфс и дфс
Прежде чем объяснять концепцию bfs, давайте рассмотрим концепцию dfs для сравнения.
Из предыдущих статей мы уже знаем, что реализация dfs часто требует использования рекурсии. Нам нужно обойти все текущие решения в рекурсии, а затем рекурсивно выполнить эти решения. Если эти решения повлияют на будущие решения, то нам также необходимо использовать возврат для отмены текущей операции после завершения обхода решения.
Итак, у нас есть код шаблона для dfs:
def dfs(n):
if n > depth:
return
for i in decisions:
do_decision(i)
dfs(n+1)
rollback(i)
Если у нас есть дерево, нам нужно обойти дерево. Очевидно, что поскольку дерево представляет собой древовидную структуру, состоящую из узлов, а не структуру списка, мы не можем пройти его напрямую с помощью цикла. Чтобы избежать повторения, нам нужно пройти по дереву в определенном порядке. Чаще всего используется dfs и bfs, давайте посмотрим, как dfs решает эту проблему.
Применяя приведенный выше шаблон, мы можем легко написать:
def dfs(node):
if node is None:
return
for child in node.childs:
print(child)
dfs(child)
Поскольку нам нужно пройти только по узлам, процесс обхода не повлияет на последующий обход, поэтому нам не нужно откатывать этот шаг. И дерево имеет естественную структуру, порядок нашей рекурсии точно такой же, как порядок самого дерева, проходя от родительского узла к дочернему узлу. Поэтому никакой другой обработки не требуется.
Предположим, у нас есть такое дерево:
Используйте dfs, чтобы обойти его, каков будет порядок?
Немного в логику вышеперечисленного обхода нужно уметь понимать, его порядок таков: A->B->C->D->E->F->G->H.
Вы видели узор? Фактически, dfs заключается в том, чтобы сначала пройти до конца одной дороги, а затем вернуться, чтобы пересечь другие дороги. То есть, когда мы сталкиваемся с несколькими решениями, мы отдаем предпочтение движению в направлении большей глубины.
Поиск в ширину как раз противоположен его логике. Мы должны уметь угадывать буквальное значение. При поиске bfs стремится сначала принять все текущие решения, то есть пойдет в направлении большей широты. предстоящий.
Для очень простого примера предположим, что мы играем в игру с несколькими концовками. Поиск в глубину означает, что независимо от того, что такое тройка, семерка и двадцать одна, сначала играйте до растаможки, а потом меняйте выбор, чтобы получить другие концовки. Поиск в ширину заключается в том, чтобы сохранять архивы, когда игра стоит перед выбором, перебирать все возможности, а затем читать архивы один за другим и повторять эту операцию.
Итак, вернемся к проблеме обхода дерева выше, если это bfs, порядок его обхода, очевидно, A->B->D->E->C->F->G->H.
Выполнение
Тщательный анализ покажет, что dfs обходит дерево поиска вертикально, а bfs — горизонтально. При реализации dfs мы фактически позаимствовали системный стек для хранения ранее пройденного состояния. И теперь, когда нам нужно пройти по горизонтали, очевидно, что рекурсия не применяется, но нам также нужна структура данных для хранения состояния обхода, точно так же, как сохранение игры.
Снова взглянув на дерево, узел A имеет в общей сложности 3 ветви B, D и E. Мы можем получить эти три узла через узел A. После этого нам нужно пройти по очереди эти три узла и получить все их ответвления. Другими словами, порядок, в котором мы проходим через три узла BDE, является порядком, в котором мы сталкиваемся с ним.Мы считаем, что состояние хранения записывается в контейнер, а при чтении считается, что оно выбрасывается из контейнера. контейнер, поэтому контейнер должен быть первым пришел, первым вышел.
Стек первым пришел, последним вышел, поэтому он не выполняется, а очередь первым пришел, первым ушел, что нам и нужно. Итак, bfs реализован на основе очередей.
Когда у нас есть очередь, мы можем передать ей работу по поддержанию состояния, нам нужно только сосредоточиться на логике обхода одного узла. Потому что очередь будет натягивать нам эти узлы, когда в очереди нет элементов, значит, мы закончили обход.
Записываем код шаблона:
queue = Queue()
while not queue.empty():
state = queue.front()
queue.pop()
print(state)
for new_state in state.new_states():
queue.put(new_state)
Это очень просто, не так ли?После использования очереди код для обхода также состоит из нескольких строк. Что касается очередей, то существует множество способов их реализации. Пока принцип освоен, реализация одинакова, можно использовать как список, так и связанный список. Python реализует для нас очередь, в версии Python3 это очередь, а в Python2 это Queue, тут нужно обратить внимание. Я использую Python3, так что это очередь, и использование очень простое:
from queue import Queue
que = Queue()
while not queue.empty():
state = queue.get()
print(state)
for new_state in state.new_states():
queue.put(new_state)
Если вы понаблюдаете за этим, вы обнаружите, что, согласно моему пониманию, получение элемента в голове очереди и извлечение элемента из головы на самом деле являются двумя операциями. Но в библиотеке очередей они объединены в одну. То есть, когда мы используем метод get для получения элемента head, он выталкивается из очереди, что требует внимания. В большинстве случаев это не проблема, но иногда мы можем захотеть сначала получить ее, а потом уже судить, удалять из очереди или нет. up deque, или Сделай сам со списком.
вот и дело
Если все в духе критики и познания в процессе обучения, обязательно возникнет вопрос, а зачем мы придумываем два метода обхода? Какая польза от изучения bfs?Разве не хорошо, что рекурсивная реализация dfs не должна поддерживать структуру данных сама по себе?
Очень важно подумать об этом моменте.Если мы не понимаем этого момента, как мы узнаем, какой алгоритм использовать, когда мы сталкиваемся с проблемами на практике? Но, к сожалению, большинство учебников не освещают этот момент, а оставляют читателям возможность подумать самостоятельно, и я должен сказать, что это довольно сложно.
На самом деле разница только одна, то есть когда мы находим ответ, не заканчивая поиск, bfs может закончиться раньше, а dfs часто нет.
На самом деле есть два момента, чтобы решить эту проблему раньше: давайте сначала рассмотрим более простой: реализации bfs обычно реализуются с помощью циклов while вместо рекурсии. Затем, когда мы нашли ответ, мы можем просто выйти из цикла и завершить обход досрочно. Но dfs относительно сложно. Некоторые студенты могут сказать, что мы также можем возвращать значения в рекурсивных функциях, не так ли?
На самом деле это действительно не то же самое, мы можем выйти из текущего выполнения только тогда, когда выполним return в рекурсии, после возврата мы вернемся в то место, где был сделан вызов верхнего уровня, и весь процесс поиска не над. Например:
def dfs(n):
if n > 20:
return
print(n)
for i in range(n+1, 50):
dfs(i)
При n равном 21 сработает условие n > 20, и будет выполнен возврат, но после возврата он вернется на позицию предыдущего цикла, и тогда i=21, 22... 50 все равно будут казнены. То есть, хотя он и возвращается, весь рекурсивный процесс не заканчивается, а заканчивается только текущий узел. И если это bfs, поскольку мы проходим в цикле, мы можем напрямую прервать цикл, чтобы завершить весь процесс bfs.
думать глубоко
Если мы просто хотим найти ответ или просто хотим получить ответ, то dfs и bfs похожи. Хотя у dfs есть проблема, связанная с невозможностью выхода напрямую, ее нельзя полностью решить.Вводя такие методы, как глобальные переменные, мы также можем замаскировать ранний выход, хотя это немного более проблематично.
Но если мы хотим найти оптимальный ответ, часто поиск в глубину не применяется.
Давайте рассмотрим классический пример, который также является классическим сценарием использования bfs, то есть задачу лабиринта.
###########
# S #
# #
# # # #
# #E# #
###########
На картинке выше показан очень простой лабиринт, s — начальная точка, а E — конечная точка. # Указывает на забор, то есть позицию, по которой нельзя пройти. Если мы просто спросим, есть ли допустимое решение для этого лабиринта, то и dfs, и bfs будут одинаковыми. И из-за привычек кодирования мы можем быть более склонны использовать dfs для поиска с возвратом.
Но если мы хотим узнать кратчайший путь от начальной до конечной точки, то в этой задаче можно в основном использовать только bfs.
Причина проста, потому что когда мы находим конечную точку через dfs, мы не знаем, является ли это кратчайшим путем. Для того, чтобы найти кратчайший путь, мы можем только записать все пути до конечной точки, а затем вернуть кратчайший путем сравнения. Это явно ненаучно, потому что мы дополнительно проходим множество ненужных состояний, которых в задаче поиска может быть очень много. Так как bfs — это горизонтальный обход, то при нахождении конечной точки это должно быть оптимальное решение, поэтому достаточно сразу вернуться к циклу прерывания, избегая множества ненужных обходов.
То есть способность найти ответ с первого раза и самый быстрый путь к ответу — самая большая особенность bfs. Это также важная причина, по которой мы используем bfs в задаче.
Новички часто больше склоняются к использованию dfs, так как не знакомы с очередями, и не понимают сути этих двух поисковых алгоритмов, что помимо принципов самих алгоритмов тоже очень важно.
Наконец, мы прикрепляем код для обхода лабиринта bfs:
from queue import Queue
from collections import defaultdict
que = Queue()
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visited = defaultdict(bool)
def bfs(S, E, maze):
# S is start, E is end
# maze 地图
# visited 记录走过的位置
n, m = len(maze), len(maze[0])
que.push((S, []))
visited[S] = True
while not que.empty():
position, states = que.get()
if position == E:
states.append(E)
return states
for xi, xj in directions:
# 拷贝，Python中list是引用传递，不使用copy会引起出错
cur = states.copy()
x, y = position[0] + xi, position[i] + xj
if 0 < x < n and 0 < y < m and maze[x][y] != '#' and not visited[(x, y)]:
visited[(x, y)] = True
cur.append((x, y))
que.put(((x, y), cur))
return []
На этом знакомство с алгоритмом bfs подошло к концу. Заинтересованные студенты могут рассчитывать на это.
Если вы чувствуете, что что-то добились, пожалуйста, нажмите на это или перешлите.Ваши усилия очень важны для меня.