Ids算法的空间复杂度(Space Complexity of Ids Algorithm)

Ids算法的空间复杂度(Space Complexity of Ids Algorithm)

您好我尝试计算IDS（迭代深化深度优先搜索）算法的空间复杂度，但我无法弄清楚如何做到这一点。 我无法真正理解算法如何访问树的节点，以便我可以计算它所需的空间。 你可以帮我吗？

Hello I try to calculate the space complexity of IDS (Iterative deepening depth-first search) algorithm but I cannot figure out how to do that. I can't really understand how the algorithm visits the nodes of a tree, so that I could calculate how space it needs. Can you help me?

最满意答案

据我所知，IDS的工作方式如下：从限制为0开始，意味着图形（或起点）中根节点的深度，它执行深度优先搜索，直到它耗尽它找到的节点为止由限制定义的子图。 然后通过将限制增加1并从相同的起点执行深度优先搜索继续进行，但是在由较大限制定义的现在更大的子图上。 通过这种方式，IDS设法将DFS的优势与BFS（广度优先搜索）的优势结合起来。 我希望这可以解决一些问题。

As far as i have understood, IDS works like this: starting with a limit of 0, meaning the depth of the root node in a graph(or your starting point), it performs a Depth First Search until it exhausts the nodes it finds within the sub-graph defined by the limit. It then proceeds by increasing the limit by one, and performing a Depth First Search from the same starting point, but on the now bigger sub-graph defined by the larger limit. This way, IDS manages to combine benefits of DFS with those of BFS(breadth first search). I hope this clears up a few things.