Ширина первого или глубины сначала поиска

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

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

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