深度优先搜索

3.4.3 深度优先搜索

深度优先搜索总是扩展搜索树的当前边缘中最深的节点。搜索过程如图3.12所示。搜索直接推进到搜索树的最深层，那里的节点没有后继节点。当那些节点扩展完之后，它们被从边缘中去掉，然后搜索算法“向上回到”下一个还有未扩展后继节点的稍浅的节点。

这个搜索策略可以由函数 TREE-SEARCH 通过一个后进先出（LIFO）队（也可以称为栈）来实现。作为一个可选择的TREE-SEARCH实现方案，通常使用一个调用自己的递归函数来实现深度优先搜索算法，可以依次对当前节点的子节点调用该函数。（一个结合深度限制的递归深度优先算法如图3.13所示。）

深度优先搜索对内存的需求很少。它只需要存储一条从根节点到叶节点的路径，以及该路径上每个节点的所有未被扩展的兄弟节点即可。一旦一个节点被扩展，当它的所有后代都被完全探索过后这个节点就可以从内存中删除。（参见图3.12。）对一个分支因子为b，最大深度为m的状态空间，深度优先搜索只需要存储bm+1个节点。使用与图3.11相同的假设，并且假设与目标节点在同一深度的节点没有后继节点，我们发现在深度d = 12的时候深度优先搜索只需要118K字节而不是10P字节（1K约为103，1P = 1MG 约为1015——译者注），节省了大约百亿倍的空间。

深度优先搜索的另外一种变形称为回溯搜索，所用的内存空间更少。在回溯搜索中，每次只产生一个后继节点而不是所有的后继节点；每个被部分扩展的节点要记住下一个要生成的节点是哪个。用这种方法，只需要O(m)的内存而不是O(bm)。回溯搜索还推动了另一个节省内存（和节省时间）的技巧：通过直接修改当前的状态描述而不是先对它进行复制来生成后继节点的思想。这把内存需求减少到只有一个状态描述以及O(m)个行动。为了让这个算法工作，当我们回溯扩展下一个后继节点的时候，我们必须能够撤销每次修改。对于状态描述很复杂的问题，例如机器人装配问题，这些技术是成功的关键。

图3.12 二叉树上的深度优先搜索。已经被扩展并且在边缘中没有后代的节点可以从内存中删除；这些节点用黑色表示。假设第三层的节点没有后继节点并且M是唯一的目标节点

深度优先算法的缺点是它有可能错误地选择一条分支并且沿着一条很长的（甚至是无限的）路径一直走下去，而如果做出不同的选择则可能引导对树根节点附近的解进行搜索。例如，在图3.12中，尽管C是目标节点，深度优先搜索还是要先探索整个左侧子树。如果节点J也是一个目标节点，那么深度优先搜索将把它作为解返回；因此，深度优先搜索不是最优的。如果左子树没有深度限制又不包含目标节点，那么深度优先搜索将永远不会终止；因此，它不是完备的。在最坏情况下，深度优先搜索将生成搜索树中的所有O(bm)个节点，其中m是任何节点的最大深度。注意m可以比d（深度最浅的解的深度）大很多，并且如果搜索树是无边界的，则m也是无限的。