Когда целесообразно использовать поиск по глубине (Depth-First Search, DFS) и поиск по ширине (Breadth-First Search, BFS)?

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

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

River
Редактировал вопрос 11-го марта 2018 в 7:18
Программирование
graph-theory algorithm graph-algorithm depth-first-search breadth-first-search
26-го июля 2010 в 7:24
67 просмотров
Комментарии к вопросу (5)
Решение

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

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

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

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

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

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

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

nobalG
Редактировал ответ 9-го октября 2017 в 5:46
Комментарии (4)

Глубину поиска

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

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

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

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

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

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

Yogesh Umesh Vaity
Редактировал ответ 3-го июля 2017 в 2:09
Комментарии (0)

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

пример БФС

Вот пример того, что БФС будет выглядеть. Это что-то вроде порядка обхода дерева, где мы используем очереди с итеративный подход (в основном рекурсии в конечном итоге с ДПП). Цифры означают порядок, в котором узлы доступны в БФС:

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

пример ДПП

Вот пример того, что ДПП будет выглядеть. Я думаю, что после порядок обхода в двоичном дереве будет начать работу с конечного уровня первой. Цифры означают порядок, в котором узлы доступны в ДФС:

различия между ДПП и ВПХ

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

Например, учитывая семейное древо, если кто-то искал кого-то на дереве, кто еще жив, тогда можно было бы с уверенностью предположить, что человек будет на нижней части дерева. Это означает, что БФС займет очень много времени, чтобы достичь этого последнего уровня. В ДФС, однако, найти цели быстрее. Но, если мы ищем члена семьи, который умер очень давно, то этот человек будет ближе к вершине дерева. Затем, БФС обычно будет быстрее, чем ДПП. Таким образом, преимущества либо различаться в зависимости от данных, и то, что вы ищете.

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

Kanagavelu Sugumar
Редактировал ответ 12-го апреля 2016 в 10:41
Комментарии (6)

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

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

Комментарии (0)

DFS занимает больше места, чем BFS, но может заходить на ненужную глубину.

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

О IDDFS

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

Комментарии (1)

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

Здесь'с поиском в глубину для неориентированный граф, если вы'вэ хранение “уже посетили” информации в узлах:

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())

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

Комментарии (0)

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

Community
Редактировал ответ 13-го апреля 2017 в 12:48
Комментарии (0)

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

Комментарии (1)

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

Комментарии (0)

Следующих исчерпывающий ответ на то, что вы просите.

В простых терминах:

Широта первого поиска (БФС) алгоритм, с его именем "вширь" и, обнаруживает, что все соседи узла через края узла, затем он обнаруживает непосещенных соседей из вышеупомянутых соседей через их края и так далее, пока все узлы достижимы из оригинал источник посещают (мы можем продолжить и сделать еще один оригинальный источник, Если остались непосещенные узлы и так далее). Что's, почему он может быть использован для поиска кратчайшего пути (если есть) из узла (оригинальный источник) на другой узел в случае, если веса ребер одинаковы.

Поиском в глубину (DFS алгоритм), с его именем "Глубина", которая, обнаруживает непосещенных соседей недавно обнаружен узел X через его края. Если нет непосещенных соседей из узла X, то алгоритм возвращается, чтобы обнаружить непосещенных соседей узла (по его краям), из которого узел X был обнаружен, и так далее, пока все узлы достижимы из оригинал источник посещают (мы можем продолжить и сделать еще один оригинальный источник, Если остались непосещенные узлы и так далее).

Как BFS и DFS могут быть неполными. Например, если ветвление фактора узел бесконечной или очень большой для ресурсов (памяти) для обслуживания (например, при хранении узлы, к которым будет обнаружен рядом), потом БФС неполная, хотя искали ключ может находиться на расстоянии нескольких краях от первоначально источника. Этот бесконечный коэффициент ветвления может быть из-за бесконечного выбора (соседние узлы) от данного узла, чтобы обнаружить. Если глубина бесконечна, или очень больших ресурсов (памяти) для обслуживания (например, при хранении узлы, к которым будет обнаружен рядом), то DFS не полный, хотя искали ключ может быть третий сосед на оригинальный источник. Эту бесконечную глубину может быть из-за ситуации там, где есть, для каждого узла алгоритм обнаруживает, по крайней мере, новый выбор (соседних узла), непосещаемая раньше.

Таким образом, можно сделать вывод, когда следует использовать БФС и ДФС. Предположим, что мы имеем дело с управляемым коэффициентом ветвления общества и управляемого общества глубиной. Если искомый узел-мелкий, т. е. до границы с оригинальный источник, то лучше использовать поиск в ширину. С другой стороны, если искомый узел глубокий, т. е. занимает много края от первоначально источника, то лучше использовать DFS.

Например, в социальной сети, если мы хотим искать людей, которые имеют схожие интересы конкретного человека, мы можем применить БФС от этого человека, как и оригинальный источник, т. к. в основном эти люди будут его прямых друзей или друзей друзей, то есть один или два края далеко. С другой стороны, если мы хотим искать людей, которые имеют совершенно разные интересы конкретного человека, мы можем применять ДФС от этого человека, как и оригинальный источник, т. к. в основном эти люди будут очень далеки от него, т. е. друг друг друга.... т. е. слишком много краев далеко.

Применение BFS и DFS могут изменяться также из-за механизма поиска в каждой из них. Например, мы можем использовать либо БФС (при условии, что ветвление фактор является управляемым) или ДПП (при условии, что глубина управляемо), когда мы просто хотим проверить доступность из одного узла на другой, не имея никакой информации, где что узел может быть. Также они оба могут решить те же задачи, как и топологическую сортировку графа (если он есть). БФС может быть использовано для определения кратчайшего пути, блок с краями вес, из узла (оригинальный источник) к другому. Принимая во внимание, что DFS может быть использован, чтобы исчерпать все варианты, из-за своего характера идти в глубину, как обнаружили самый длинный путь между двумя вершинами в ациклическом графе. Также ДФС, можно использовать для обнаружения циклов в графе.

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

Mosab Shaheen
Редактировал ответ 10-го мая 2019 в 9:23
Комментарии (0)

По свойствам ДПП и ВПХ. Например,когда мы хотим найти кратчайший путь. мы обычно используем БФС,он может гарантировать что 'короткие'. но DFS может только гарантировать, что мы можем прийти с этой точки может достигнуть этой точки ,не может гарантировать 'короткие'.

Комментарии (0)

Я думаю, что это зависит от того, какие проблемы вы столкнулись.

  1. кратчайший путь на простой график -> БФС
  2. все возможные результаты -> ДПП
  3. поиск на графе(дереве лечить, martix в тоже график) -> ДПП ....
MedicineMan
Редактировал ответ 27-го мая 2019 в 6:33
Комментарии (1)

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

Комментарии (0)

Когда ширина дерева очень большие и глубина низких ДХ используют, как рекурсия стек не переполнится.Использовать БФС, когда ширина невелика и глубина очень большая, чтобы пересечь дерево.

Комментарии (0)

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

Комментарии (0)

Это хороший пример, чтобы продемонстрировать, что BFS лучше, чем ДФС в конкретном случае. https://leetcode.com/problems/01-matrix/

При правильной реализации, оба решения должны посетить клеток, которые имеют большее расстояние, чем текущая ячейка +1. Но ДФС является неэффективным и неоднократно бывал в той же ячейке в результате о(n*n) сложность.

Например,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,
Комментарии (0)