Недостатки BFS и DFS

Question

BFS потребляет много памяти, особенно когда фактор ветвления дерева огромен. DFS, с другой стороны, может занять много времени, чтобы посетить другие соседние узлы, если глубина дерева огромна, но она имеет большую сложность пространства. Например, в BFS, если у меня есть коэффициент ветвления 10 и глубина 12, используя формулу O(b^d), это означает, что у меня будет около 10 ^ 12 узлов. Если каждый узел имеет размер 10 байт, ему потребуется около 10 ТБ.

Однако, что здесь считается «огромным»? Считается ли космическая сложность 10 ТБ огромной (хотя я уверен, что это так)? Как определить, когда мне следует покинуть DFS и BFS и искать другие алгоритмы? Они даже по-прежнему используются в современных приложениях или вместо них применяются другие, более совершенные алгоритмы (например, IDDFS)?

Answer 1

Рассмотрите этот источник: Когда целесообразно использовать поиск в глубину (DFS) против поиска в ширину (BFS)?

Я думаю, что есть эксперимент для ваших собственных данных, Ресурсы.Если результат теста не удовлетворяет вас, попробуйте другой алгоритм.Binary-Tree Search, KDTree - это несколько вариантов.

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