为什么迭代深化搜索的空间复杂度是O(bm)？

Question

在 人工智能。现代方法 教科书中指出，IDS的空间复杂度为 O(bm)，其中 b = 分支系数和 m =树的最大深度。IDS在其遍历过程中存储了哪些节点，导致它有一个 O(bm) 空间复杂度 ?

Answer 1

在 维基百科 它说空间复杂度是简单的深度 d 因为它本质上是一种深度优先的搜索；这就是我的《AIAMA》副本中的实际内容（第88页）。

我只能想象 O(bm) 假设存储了所有访问过的节点的最高级别，也就是分支级别乘以当前深度。没有必要存储更高级别的节点，因为它们已经被搜索过了。