Сложность глубины/пространства глубины Первый поиск

Question

Я посмотрел на другой ответ на stackoverflow, и все они отличаются от того, что мой лектор написал на своих слайдах.

Глубина первый поиск имеет временную сложность O (Ь^м), где Ь является максимальным коэффициентом ветвления из дерева поиска и м максимальной глубины пространства состояний. Ужасно, если m много больше, чем d, но если поиск дерева «густой», может быть намного быстрее, чем ширина в первую очередь.

Он продолжает говорить ..

Пространство сложность O (Ьт), то есть пространство линейно по длине действия последовательности! Нужно хранить только один путь от корня до листа , а также оставшиеся неиспользуемые узлы для каждого узла по пути .

Другой ответ на StackOverflow состояний, что это O (п + т) Time complexity of depth-first graph algorithm

Answer 1

Сложность времени: Если вы можете получить доступ к каждому узлу в O (1) раз, то с коэффициентом ветвления b и максимальной глубиной m общее число узлов в этом дереве будет = b * b * b ... m times = b ^m, в результате чего общее время посещения каждого узла пропорционально b ^m. Следовательно, сложность = O (b ^m).

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

Другие ответы SO, которые вы связали в своем вопросе, аналогичным образом используют разные термины. Идея такая же повсюду. В некоторых ответах также добавлен счетчик краев, чтобы сделать ответ более точным, но в целом количество узлов достаточно для описания сложности.

---

Пространство Сложность: Длина самого длинного пути = т. Для каждого узла вы должны хранить своих братьев и сестер, чтобы после того, как вы закончите посещение всех детей, и вы вернетесь к родительскому узлу, вы можете узнать, какой родной брат будет исследовать дальше. Для m узлов по пути вам нужно будет хранить b узлов дополнительно для каждого из m узлов. Вот как вы получаете сложность пространства O (bm).

Answer 2

Сложность O(n + m) где n является количество узлов в дереве и m это число ребер.

Причина, по которой ваш учитель представляет сложность, как O(b^m), вероятно, потому, что он хочет подчеркнуть разницу между поиском глубины и первым поиском по ширине.

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

Когда дерево очень глубокое, а не листья могут предоставлять информацию о более глубоких узлах, BFS может обнаруживать способы обрезки дерева поиска, чтобы уменьшить количество узлов, необходимых для поиска вашей цели. Ясно, что чем выше дерево вы обнаружите, вы можете обрезать поддерево, тем больше узлов вы можете пропустить. Это сложнее, если вы используете DFS, потому что вы уделяете приоритетное внимание достижению листа над исследуемыми узлами, которые ближе к корню.

Answer 3

Я полагаю, что эта сложность времени и пространства DFS преподается на классе AI, но не на классе алгоритмов.

Поиск DFS дерево поиска здесь имеет немного другой смысл:

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

Цитируется по книге «Искусственный интеллект - современный подход»

Таким образом, время/пространство сложности здесь сосредоточена на вас посетить узлы и проверить, является ли состояние цели. @displayName уже дает очень четкое объяснение.

Хотя O (m + n) находится в классе алгоритмов, фокус - это сам алгоритм, когда мы храним график как список смежности и как мы обнаруживаем узлы.