Чем полезен поиск в ширину?

Question

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

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

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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

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