Для чего нужен поиск в ширину?

Question

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

Когда имеет смысл использовать поиск в ширину?

ОБНОВЛЕНИЕ : Полагаю, мой ответ здесь показывает ситуацию, когда я использовал BFS (потому что я думал, что это DFS). Мне все еще интересно узнать, почему это было полезно в этом случае.

Answer 1

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

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

Answer 2

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

Также вы можете увидеть более сложные алгоритмы, такие как A *, которые являются особым подтипом поиска в ширину.

В целом, bfs является оптимальным и полным (с конечным коэффициентом ветвления), а dfs - нет.

Answer 3

Никто еще не упомянул ключевой фактор в тех случаях, когда поиск в ширину полезен: посещение узла одним способом может устранить необходимость посещения узла другим способом. В некоторых случаях в конечном итоге выполняется одна и та же работа, независимо от порядка посещения узлов, но BFS будет выполнять гораздо меньше ожидающих действий одновременно, чем DFS. В других случаях посещение узлов в одной последовательности может потребовать больше работы, чем в других; в качестве примера приводятся различные алгоритмы кратчайшего пути. Если посещение узла требует посещения его соседей, если не известно, что узел доступен для пути, который короче текущего, то посещение узлов в первом порядке обычно приводит к тому, что узлам назначается кратчайший путь - или что-то близкое к нему - -при их первом посещении. В отличие от этого, поиск в глубину может привести к тому, что многие узлы будут посещаться с очень длинными путями в первый раз, затем с более короткими путями, затем с чуть более короткими путями и т. Д., Что потребует поистине чудовищного общего объема работы.

Кстати, одна хорошая графическая иллюстрация различия между алгоритмами глубины и ширины - это заливка области, где белый узел заливается заливкой его черным цветом и заливкой соседей. Если кто-то пытается заполнить область квадрата NxN, начиная с корндерса, операция глубины сначала заполняет квадрат в спиральной или зигзагообразной последовательности, при этом операции NxN-1 остаются в стеке. Заполнение в ширину будет «выливаться» из начальной точки и будет иметь не более O (N) незавершенных операций независимо от формы, которую нужно заполнить. Кстати, заливка в IBM BASICA работала таким образом (я не уверен насчет QBASIC).

Answer 4

Может использоваться для решения задачи поиска с минимальным количеством шагов. Сначала углубление может привести (если не ограничено каким-либо образом) к бесконечной глубине.

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

Answer 5

Когда имеет смысл использовать поиск в ширину?

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

Answer 6

Одним из примеров является обход файловой системы (с ограниченной рекурсивной глубиной).

Согласно википедии , это также полезно для некоторых алгоритмов графов (двухсторонности, связанных компонентов).

Answer 7

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

1. Веб-сайты социальных сетей могут использовать его для поиска людей в указанное расстояние.
2. Это может быть полезно в торрент / одноранговой сети для поиска соседние компьютеры.
3. Системы навигации GPS могут использовать его для поиска ближайших мест.

Answer 8

BFS иногда действительно полезен. Предположим, у вас есть дерево, которое представляет, скажем, WBS. Возможно, вы захотите представить своему пользователю только 1 его уровень.

Answer 9

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

Answer 10

Когда вам нужно получить кратчайший путь к вершине из графа без веса ребра.