Почему пространственная сложность итеративного углубленного поиска O (bm)?

Question

В учебнике Искусственный интеллект: современный подход заявлено, что IDS имеет пространственную сложность O(bm), где b = коэффициент ветвления и m = максимальная глубина дерева. Какие узлы IDS хранит во время своего обхода, что приводит к сложности пространства O(bm)?

Answer 1

В Википедии говорится, что сложность пространства - это просто глубина d цели, поскольку это, по сути, поиск в глубину; это то, что на самом деле говорится в моей копии AIAMA (стр. 88)

Я могу только представить, что O (bm) предполагает, что верхний уровень всех посещенных узлов хранится, который будет уровнем ветвления, умноженным на текущую глубину. Нет необходимости хранить узлы более высокого уровня, так как они уже были найдены.