您好，我尝试计算 IDS（迭代加深深度优先搜索）算法的空间复杂度，但我无法弄清楚如何做到这一点。我无法真正理解算法如何访问树的节点，以便我可以计算它需要多少空间。你能帮助我吗？
问问题
1228 次
2 回答
0
据我了解，IDS 的工作原理是这样的：从 0 的限制开始，这意味着图中根节点的深度（或您的起点），它执行深度优先搜索，直到耗尽它在其中找到的节点由限制定义的子图。然后它继续将限制增加一，并从相同的起点执行深度优先搜索，但在由更大限制定义的现在更大的子图上。通过这种方式，IDS 设法将 DFS 的优点与 BFS（广度优先搜索）的优点结合起来。我希望这能澄清一些事情。
于 2014-01-05T20:40:32.310 回答
0
来自维基百科：
IDDFS 的空间复杂度为 O(bd)，其中 b 是分支因子，d 是最浅目标的深度。由于迭代加深访问状态多次，可能看起来很浪费，但事实证明它并没有那么昂贵，因为在树中大多数节点都在底层，所以如果上层被多次访问也没关系次。[2]
于 2014-01-28T21:13:31.060 回答