Что такое поиск по ширине?

Question

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

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

UPDATE: Я полагаю, что мой ответ here показывает ситуацию, когда я использовал BFS (потому что я думал, что это DFS). Мне все еще интересно узнать, почему это было полезно в этом случае.

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

Answer 8

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

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

Answer 9

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

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

Answer 10

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

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