поиск в ширину или в глубину

Question

Я знаю, как работает этот алгоритм, но не могу решить, когда использовать какой алгоритм?

Существуют ли какие-либо руководящие принципы, в которых одно лучше, чем другие, или какие-либо соображения?

Большое спасибо.

Answer 1

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

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

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

IDDFS сочетает в себе эффективность поиска по глубине и ширину поиска по ширине (когда коэффициент ветвления конечен).

Answer 2

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

Answer 3

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

Если вы хотите найти кратчайший путь, BFS - естественный выбор.

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

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

Answer 4

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

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

Если в вашей задаче есть причина выбора одного узла из другого, вы можете рассмотреть возможность использования очереди с приоритетами вместо стека (для глубины в первую очередь) или FIFO (для ширины в первую очередь). Очередь приоритетов займет O (log K) времени (где K - текущее число различных приоритетов), чтобы найти лучший узел на каждом шаге, но оптимизация может стоить этого.