Привет, я пытаюсь вычислить сложность пространства алгоритма IDS (Итеративный углубление глубины поиска), но я не могу понять, как это сделать. Я не могу понять, как алгоритм посещает узлы дерева, чтобы я мог рассчитать, как он нужен. Вы можете мне помочь?Космическая сложность алгоритмов идентификаторов
Насколько я понял, IDS работает следующим образом: начиная с предела 0, что означает глубину корневого узла в графе (или отправной точке), он выполняет поиск глубины первого, пока не исчерпает узлы, которые он находит в пределах субграфа, определенного пределом. Затем он переходит путем увеличения лимита на единицу и выполнения глубины первого поиска с той же начальной точки, но на более крупном подграфе, определяемом большим лимитом. Таким образом, IDS удается комбинировать преимущества DFS с преимуществами BFS (поиск по ширине в первом порядке). Надеюсь, это прояснит кое-что.
от Wikipedia:
Пространство сложность IDDFS представляет собой О (шд), где Ь коэффициент ветвления и d это глубина неглубокой цели. Поскольку итеративное углубление посещает состояния несколько раз, это может показаться расточительным, но оно оказывается не таким дорогостоящим, поскольку в дереве большинство узлов находятся на нижнем уровне, поэтому не имеет большого значения, если верхние уровни посещаются несколькими раз. [2]