如何解决 DFS 在最大分支因子、最优解深度和最大树深度方面的 space 复杂度？
How can I solve the space complexity of DFS in terms of maximum branching factor, depth of the optimal solution and maximum tree depth?
DFS 在最大分支因子、深度方面的 space 复杂度是多少
最优解和最大树深？显示必要的计算并写出
合乎逻辑的解释。
深度优先搜索需要先将节点一直扩展到最大树深度，因此需要为每一级扩展添加一个指向堆栈的指针。
这表明 space 复杂度在树的最大深度上是线性的并且与分支因子无关。
但这取决于您如何扩展每个节点。如果您需要保持节点扩展以便指针不足以检索您在特定分支的位置，您将需要保留有关每个级别的分支选项的信息。您不需要保留此信息来扩展您已经排除的分支。这将导致 space 复杂度在深度上是线性的，在分支因子上是线性的。总数 space 需要是常数乘以两者的乘积。
DFS 在最大分支因子、深度方面的 space 复杂度是多少 最优解和最大树深？显示必要的计算并写出 合乎逻辑的解释。
深度优先搜索需要先将节点一直扩展到最大树深度，因此需要为每一级扩展添加一个指向堆栈的指针。 这表明 space 复杂度在树的最大深度上是线性的并且与分支因子无关。
但这取决于您如何扩展每个节点。如果您需要保持节点扩展以便指针不足以检索您在特定分支的位置，您将需要保留有关每个级别的分支选项的信息。您不需要保留此信息来扩展您已经排除的分支。这将导致 space 复杂度在深度上是线性的，在分支因子上是线性的。总数 space 需要是常数乘以两者的乘积。