over tree ：您无需检查您之前是否曾访问过状态，并且只能存储当前跟踪（在堆栈中），最大深度为$ d $ . 对于跟踪上的每个状态，您需要存储已经遍历的传出转换，这最大化为每个状态的最大分支因子$ b $ . 因此，您需要$ O（d * b）$空间 .
over graph ：您需要另外通过存储已访问过的所有州来检查您是否曾访问过某个州，例如：在哈希表中 . 因此，您需要$ O（d * b | V |）$空间，其中V是顶点集 . 在interwebs上，你通常会读到空间复杂度是$ O（| V |）$;通常状态的数量是主要因素，但如果您的状态空间有大的$ b $，请不要忽略这部分空间要求！
1 回答
这取决于您执行深度优先搜索（DFS）的结构类型：
over tree ：您无需检查您之前是否曾访问过状态，并且只能存储当前跟踪（在堆栈中），最大深度为$ d $ . 对于跟踪上的每个状态，您需要存储已经遍历的传出转换，这最大化为每个状态的最大分支因子$ b $ . 因此，您需要$ O（d * b）$空间 .
over graph ：您需要另外通过存储已访问过的所有州来检查您是否曾访问过某个州，例如：在哈希表中 . 因此，您需要$ O（d * b | V |）$空间，其中V是顶点集 . 在interwebs上，你通常会读到空间复杂度是$ O（| V |）$;通常状态的数量是主要因素，但如果您的状态空间有大的$ b $，请不要忽略这部分空间要求！