Почему считается, что DFS имеет сложность ?

Согласно этим примечаниям считается , что DFS имеет сложность пространства , где - коэффициент ветвления дерева, а - максимальная длина любого пути в пространстве состояний. $O(bm)$ $b$ $m$

То же самое сказано в этой странице Wikibook на Неинформированном Поиске .

Теперь «инфобокс» статьи в Википедии о DFS представляет следующее для пространственной сложности алгоритма:

$O(|V|)$ , если весь граф обходится без повторения, ищется самая длинная длина пути для неявных графов без устранения дублирующих узлов $O($ $)$

что больше похоже на то, что я думал, была пространственная сложность DFS, то есть , где - максимальная длина, достигнутая алгоритмом. $O(m)$ $m$

Почему я думаю, что это так?

Ну, в общем, нам не нужно хранить какие-либо другие узлы, кроме узлов пути, на который мы в данный момент просматриваем, так что нет смысла умножать на в анализе, предоставленном как Wikibook, так и заметками, которые я вам рекомендовал. к. $b$

Кроме того, согласно этой статье на IDA * по Ричард Корф , пространство сложность DFS является , где считается «глубина среза». $O(d)$ $d$

Итак, какова правильная космическая сложность DFS?

Я думаю, что это может зависеть от реализации, поэтому я был бы признателен за объяснение сложности пространства для различных известных реализаций.

graphs algorithm-analysis graph-traversal space-analysis nbro
источник

DFS is considered to […] of the treeне каждый пройденный граф глубиной в первую очередь является деревом .

глиняный кувшин

Существует различие между словами «эта реализация DFS имеет стоимость X» и «DFS может быть реализована так, чтобы она стоила X». Так что, похоже, спорят о различных утверждениях второго рода, которые вообще не должны быть противоречивыми. (Обратите внимание, что нет никакого противоречия вообще, поскольку , если вообще что-либо значит.)

O (b m) \supset O (m)

$O(bm) \supset O(m)$

O (b m)

$O(bm)$

Рафаэль

@greybeard Можете ли вы привести пример, когда обход глубины в графе не приведет к дереву?

nbro

example where a depth-first traversal on a graph would not result in a treeне задумываясь об этом: разбор. (Подождите: что вы имеете в виду: result in a tree? Речь идет о поиске / обходе графа.)

глиняный кувшин

@greybeard Согласно всем определениям, которые я нашел до сих пор. Найдите мне определение, где он повторно посещает узлы, тогда мы можем обсудить это.

nbro

Ответы:

Это зависит от того, что именно вы называете DFS. Рассмотрим, например, алгоритм DFS-итеративный, описанный в Википедии , и предположим, что вы запускаете его на дереве, чтобы вам не приходилось отслеживать, какие узлы вы уже посетили. Предположим, что вы запустили его на полном -ом дереве глубины . Мы можем идентифицировать узлы в их дереве со словами длиной более не более . Алгоритм работает следующим образом: $b$ $m$ $[b]$ $m$

Начните с корня. Нажмите в стек (в обратном порядке). $1,2,\ldots,b$
Вставьте и вставьте в стек. $1$ $11,12,\ldots,1b$
Поп , и нажмите в стек. $11$ $111,112,\ldots,11b$
$\ldots$
Вставьте и вставьте в стек. $1^{m-1}$ $1^m,1^{m-1}2,\ldots,1^{m-1}b$

На этом этапе стек содержит

1^{m}, 1^{m - 1} 2, \dots, 1^{m - 1} b, \dots, 112, \dots, 11 b, 12, \dots, 1 b, 2, \dots, b,

$1^m,1^{m-1}2,\ldots,1^{m-1}b,\ldots,112,\ldots,11b,12,\ldots,1b,2,\ldots,b,$

в общей сложности узлов. Вы можете проверить, что это пинта во времени, в которой размер стека максимизируется. $(b-1)m + 1$

Юваль Фильмус
источник

Пинта вовремя держит доктора подальше.

глиняный кувшин

Здесь нужно сделать два замечания:

Если вы вводите в стек все потомки текущего узла, то, по сути, сложность пространства равна где - коэффициент ветвления, а - максимальная длина. Ответ Ювала Фильмуса действительно относится к этому делу. Тем не менее, обратите внимание, что в целом намного больше, чем . Более того, во многих областях, таких как головоломка со скользящей плиткой, ограничена сверху константой (в данном конкретном случае, 4), и, следовательно, мы можем с уверенностью сказать, что DFS имеет пространственную сложность, которая равна . $O(bd)$ $b$ $d$ $d$ $b$ $b$ $O(d)$
Правда, это не всегда так. Например, в головоломке Блина коэффициент ветвления растет с длиной оптимального решения, и они оба имеют одинаковые значения. Тем не менее, сложность пространства составляет . Чтобы увидеть это, просто настройте процедуру расширения любого узла: вместо вставки всех потомков текущего узла (как это было предложено Yuval Filmus) вставьте их по порядку. Сначала вы генерируете первого потомка, и сразу после того, как вы продолжаете в порядке глубины - на самом деле, вам не нужны все остальные потомки в этой точке $O(d)$ , Если вы когда-нибудь вернетесь к этому узлу, его потомок будет удален из стека. Затем, сгенерируйте второго потомка и продолжите в порядке глубины первого. Если вы вернетесь к этому узлу, сгенерируйте третий и так далее, пока не останется больше потомков. В таком случае в вашем стеке будет только узлов, независимо от коэффициента ветвления, . $d$ $b$

Подводя итог, я бы никогда не сказал, что DFS имеет пространственную сложность и вместо этого я утверждаю, что его космическая сложность . $O(bd)$ $O(d)$

Надеюсь это поможет,

Карлос Линарес Лопес
источник