我在同一个问题上苦苦挣扎。这是我经过深思熟虑后得出的结论。

使用深度优先搜索，您可以回溯到一个节点，该节点是您父级的非扩展子级（或者当您的父级没有更多未扩展的子级时，父级的父级（依此类推））。所以空间复杂度受到你的祖先和这些祖先的孩子的限制。转换为 m*b 其中 m 是最大路径长度（即最大祖先数），b 是分支因子（每个祖先的子代数）。

通过回溯时的贪婪搜索，您可以跳转到任何已评估但未扩展的节点，您可以在较早的路径上传递下去。因此，当回溯时，该算法可以在整个树中进行相当随机的跳跃，留下许多未扩展的兄弟节点。但是，您必须记住所有这些未扩展节点的评估函数的值，因为当回溯发生时，它们可能是下一个节点。因此，在理论上最坏的情况下，这可能意味着几乎整棵树都需要被记住。因此 O(b^m)。

我知道推理中仍然存在差距，但直觉上这让我最好地理解它。

在花了一些时间解决这个问题后，我得出结论，这是因为我们需要在遍历期间存储所有节点的启发式函数评估。因此，有人可能会声称整个节点的空间复杂度很简单$\mathcal{O}(b^m)$. 我希望这是正确的。

也是空间复杂度为$\mathcal{O}(bm)$称为递归最佳优先搜索，它与我在问题中描述的 DFS 实现最相似。