поиск в ширину или поиск в глубину
Я знаю, как этот алгоритм работает, но наклон решает, когда использовать который алгоритм?
Есть ли некоторые инструкции, где один лучше работают, чем другой или какие-либо соображения?
Большое спасибо.
4 ответа
Если вы хотите найти решение с кратчайшим количеством шагов или если ваше дерево имеет бесконечную высоту (или очень большую), вы должны сначала использовать ширину.
Если у вас есть конечное дерево и вы хотите обойти все возможные решения, используя наименьший объем памяти, то вы должны сначала использовать глубину.
Если вы ищете лучший шахматный ход для игры, вы можете использовать итеративное углубление, которое представляет собой комбинацию обоих.
IDDFS сочетает в себе эффективность поиска сначала глубину и полноту поиска по ширине (когда коэффициент ветвления конечен).
BFS обычно полезен в тех случаях, когда граф имеет некоторое значимое «естественное расслоение» (например, более близкие узлы представляют «более близкие» результаты), и ваш целевой результат, вероятно, будет расположен ближе к начальной точке или начальные точки будут дешевле искать ».
Если вы хотите найти кратчайший путь, BFS - естественный выбор.
Если ваш граф бесконечен или генерируется программно, вы, вероятно, захотите поискать более близкие слои, прежде чем выходить на поле, поскольку стоимость исследования удаленных узлов перед тем, как добраться до ближайших узлов, непомерно высока.
Если доступ к большему количеству удаленных узлов будет более дорогим из-за проблем с памятью / диском / местоположением, BFS снова может быть лучше.
Какой метод использовать обычно зависит от приложения (т. е. причины, по которой вам нужно искать график) - например, топологическая сортировка требует глубины -первый поиск, тогда как алгоритм Форда-Фулкерсона для поиска максимального потока требует поиска в ширину.
Если вы обходите дерево, depth-first будет использовать память пропорционально его глубине. Если дерево достаточно сбалансировано (или имеет какое-то другое ограничение на глубину), может быть удобно использовать рекурсивный обход в глубину.
Однако не делайте этого при обходе общего графа: это может привести к переполнению стека. Для неограниченных деревьев или общих графов вам понадобится какое-то вспомогательное хранилище, которое может расширяться до размера, пропорционального количеству входных узлов. В этом случае простой и удобный метод обхода по ширине.
Если в вашей задаче есть причина выбрать один узел вместо другого, вы можете рассмотреть возможность использования приоритетной очереди, вместо стека (для обхода в глубину) или FIFO (для обхода в ширину). Очередь приоритетов займет O(log K) времени (где K - текущее количество различных приоритетов) для поиска лучшего узла на каждом шаге, но оптимизация может того стоить.