Когда это практично для использования Поиска в глубину (DFS) по сравнению с Поиском в ширину (BFS)?
Я понимаю различия между DFS и BFS, но мне интересно знать, когда это более практично для использования один по другому?
Кто-либо мог дать какие-либо примеры того, как DFS превзошел бы BFS и наоборот?
4 ответа
Это сильно зависит от структуры дерева поиска и количества и расположения решений (они же искомые элементы).
- Если вы знаете, что решение находится недалеко от корня дерева, лучше использовать поиск по ширине (BFS) может быть лучше.
Если дерево очень глубокое и решения встречаются редко, то поиск по глубине. (DFS) может занять очень много времени, но BFS может быть быстрее.
Если дерево очень широкое, BFS может потребоваться слишком много памяти, так что он может оказаться совершенно непрактичным.
Если решения встречаются часто, но расположены глубоко в дереве, BFS может быть непрактичным.
- Если дерево поиска очень глубокое, вам придется ограничить глубину поиска. глубину для поиска по глубине (DFS), в любом случае (например, с помощью итеративного углубления).
Но это всего лишь эмпирические правила; вероятно, вам придется поэкспериментировать.
DFS более эффективно использует пространство, чем BFS, но может пойти на излишнюю глубину.
Их названия показывают: если есть большая ширина (т.е. большой фактор ветвления), но очень ограниченная глубина (например, ограниченное количество «ходов»), то DFS может быть более предпочтительным, чем BFS.
О IDDFS
Следует упомянуть, что существует менее известный вариант, который сочетает в себе пространственную эффективность DFS, но (в совокупности) посещение BFS на уровне уровня, это итеративный поиск с углублением в глубину. . Этот алгоритм пересматривает некоторые узлы, но вносит только постоянный фактор асимптотической разницы.
Работа некоторых алгоритмов зависит от определенных свойств DFS (или BFS). Например, алгоритм Хопкрофта и Тарьяна для поиска 2-связанных компонентов использует тот факт, что каждый уже посещенный узел, обнаруженный DFS, находится на пути от корня к текущему исследуемому узлу.
Поиск в ширину обычно является лучшим подходом, когда глубина дерева может варьироваться, и вам нужно искать решение только в части дерева. Например, поиск кратчайшего пути от начального значения до конечного значения - хорошее место для использования BFS.
Поиск в глубину обычно используется, когда необходимо выполнить поиск по всему дереву. Его проще реализовать (с использованием рекурсии), чем BFS, и требуется меньше состояния: в то время как BFS требует, чтобы вы сохраняли всю «границу», DFS требует, чтобы вы сохранили только список родительских узлов текущего элемента.