Когда целесообразно использовать поиск в глубину (DFS) по сравнению с поиском в ширину (BFS)?

Question

Я понимаю разницу между DFS и BFS, но мне интересно знать, когда практичнее использовать один поверх другого?

Может ли кто-нибудь привести примеры того, как DFS превзойдет BFS и наоборот?

Answer 1

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

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

• Если дерево очень глубокое и решения редки, сначала ищите глубину (DFS) может занять очень много времени, но BFS может быть быстрее.

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

• Если решения часты, но расположены глубоко в дереве, BFS может быть непрактично.

• Если дерево поиска очень глубокое, вам нужно ограничить поиск глубина для поиска в глубину (DFS), в любом случае (например, с итерационное углубление).

Но это всего лишь эмпирические правила; вам, вероятно, нужно будет поэкспериментировать.

Answer 2

Поиск в глубину

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

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

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

---

Поиск в ширину

Поиск в ширину обладает интересным свойством: сначала он находит все вершины, которые находятся на расстоянии одного ребра от начальной точки, затем все вершины, которые находятся на расстоянии двух ребер, и так далее. Это полезно, если вы пытаетесь найти кратчайший путь от начальной вершины до данной вершины. Вы запускаете BFS, и когда вы находите указанную вершину, вы знаете, что путь, который вы до сих пор отслеживали, является кратчайшим путем к узлу. Если бы был более короткий путь, BFS уже нашла бы его.

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

Answer 3

Хорошее объяснение от http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

Пример BFS

Вот пример того, как будет выглядеть BFS. Это что-то вроде обхода дерева порядка уровней, когда мы будем использовать QUEUE с подходом ITERATIVE (в основном, RECURSION будет заканчиваться DFS). Числа представляют порядок, в котором к узлам обращаются в BFS:

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

Пример DFS

Вот пример того, как будет выглядеть DFS. Я думаю, что обратный порядок в двоичном дереве сначала начнет работать с уровня Leaf. Числа представляют порядок, в котором к узлам обращаются в DFS:

Различия между DFS и BFS

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

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

Еще один пример - Facebook; Предложение о друзьях друзей. Нам нужны непосредственные друзья для предложения, где мы можем использовать BFS. Может быть, найти кратчайший путь или определить цикл (используя рекурсию), мы можем использовать DFS.

Answer 4

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

Поиск в глубину обычно используется, когда вам нужно выполнить поиск по всему дереву.Его проще реализовать (используя рекурсию), чем BFS, и требует меньшего количества состояний: в то время как BFS требует сохранения всей «границы», DFS требует только сохранения списка родительских узлов текущего элемента.

Answer 5

DFS более компактен, чем BFS, но может пойти на ненужную глубину.

Их имена показательны: если есть большая ширина (то есть большой фактор ветвления), но очень ограниченная глубина (например, ограниченное количество «ходов»), то DFS может быть более предпочтительным, чем BFS.

---

В IDDFS

Следует отметить, что существует менее известный вариант, который объединяет эффективность использования пространства DFS, но (совокупно) посещение BFS в порядке уровней - это итеративное углубление поиска в глубину . Этот алгоритм пересматривает некоторые узлы, но он вносит только постоянный коэффициент асимптотической разности.

Answer 6

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

Answer 7

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

Вот поиск в глубину для неориентированного графа, если вы храните «уже посещенную» информацию в узлах:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

При хранении «уже посещенной» информации в отдельной структуре данных:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(origin, set())

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

Answer 8

Для BFS мы можем рассмотреть пример Facebook.Мы получаем предложение добавить друзей из профиля FB из профиля других друзей.Предположим, A-> B, в то время как B-> E и B-> F, поэтому A получит предложение для E And F. Они должны использовать BFS для чтения до второго уровня.DFS больше основывается на сценариях, в которых мы хотим прогнозировать что-то на основе данных, которые мы имеем от источника до места назначения.Как уже упоминалось о шахматах или судоку.Как только у меня все по-другому, я считаю, что DFS следует использовать для кратчайшего пути, потому что DFS сначала будет покрывать весь путь, а затем мы сможем выбрать лучший.Но так как BFS будет использовать подход жадности, может показаться, что это самый короткий путь, но конечный результат может отличаться.Дайте мне знать, неверно ли мое понимание.

Answer 9

Некоторые алгоритмы зависят от конкретных свойств DFS (или BFS) для работы. Например, алгоритм Хопкрофта и Тарьяна для поиска 2-соединенных компонентов использует тот факт, что каждый уже посещенный узел, с которым столкнулась DFS, находится на пути от корневого до текущего исследуемого узла.

Answer 10

По свойствам DFS и BFS. Например, когда мы хотим найти кратчайший путь. мы обычно используем BFS, это может гарантировать «самый короткий». но только dfs может гарантировать, что мы можем прийти из этой точки, можем достичь этой точки, не можем гарантировать «самый короткий».