#algorithm #search #depth-first-search
#алгоритм #Поиск #поиск в глубину
Вопрос:
Я борюсь с пространственной сложностью итеративного поиска глубины углубления. Мне кажется, что в худшем случае, когда целью является последний узел в графе, вам нужно будет создать весь граф, и поэтому ваше пространство равно O (bm), где b — коэффициент ветвления, а m — максимальная глубина. Однако говорят, что оно равно O (bm). Может кто-нибудь, пожалуйста, объясните мне, почему это так. Заранее спасибо!
Ответ №1:
В конечном итоге вы можете создать и просмотреть весь график в тот или иной момент времени, но вам никогда не нужно хранить все это в памяти одновременно. В любой момент времени все, что вам нужно сохранить в памяти, это путь вниз к текущему местоположению, который дает вам m в bm. Я предполагаю, что фактор b исходит из того, что дочерние элементы каждого узла в пути содержат или эквивалентную информацию. На самом деле запись в Википедии в https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search говорит
Временная сложность IDDFS равна O (bd) {displaystyle O(b ^ {d})} O (b ^ d), а ее пространственная сложность равна O (d) {displaystyle O (d)} O (d), где b {displaystyle b} b -коэффициент ветвления и d {displaystyle d} d — это глубина самой мелкой цели.[2]