深度优先搜索算法解析

深度优先搜索首先向纵深方向进行搜索，由某个节点扩展出下一层节点后，选择其中一个节点，判读是否为目标状态节点，如果不是，并且该节点还有子节点，则继续扩展该节点的所有子节点并选择其中一个判断是否为目标状态节点，如果不是，检查该节点是否还有子节点。这样，一直搜索到某个节点没有子节点可以扩展，即无路径可走时，再返回到上一层，尝试上一层的其他子节点，依此类推，以深度优先的方式继续搜索其他子节点，直到对这一层的所有兄弟节点都没找到目标状态节点时，继续向上一层返回，具体流程也同图3.1所示是一致的。

同样，在搜索过程中，需要存储扩展出来的节点（OPEN表）以及访问过的节点（CLOSED表）。深度优先搜索中，扩展出了某个节点的所有子节点后，需要向纵深方向进行搜索，先扩展出来的节点需要压后再取出来进行扩展，所以OPEN表的存取过程和宽度优先搜索中的是完全不一样的，它的过程是先入后出（FILO，first input last output），所以用堆栈来实现深度优先搜索中的OPEN表。CLOSED表的作用同宽度优先搜索中的相似，同时还可以用来获取回退时的路径。

同样，用例子来说明。

例3.2　依然采用例3.1中的图3.5（a）所示状态空间作为欲搜索的状态空间，对它进行深度优先搜索，OPEN表中节点的取出扩展次序是怎样的？

解　从S出发进行深度优先搜索。首先将S存入OPEN表中，然后取出S放入CLOSED表中，S不是目标状态节点，有两条路径分别到达A和B，扩展出A，B节点，将A，B存入OPEN表中。注意，此时OPEN表采用堆栈来实现。

假设扩展S时，先将A存入OPEN表中，后将B存入OPEN表中，所以这时从OPEN表中取出的第一个节点应为后放入的B，将它放入CLOSED表中。它不是目标状态节点，其子节点为E，将E存入OPEN表中。这时，E为最后放入的节点，所以下一个从OPEN表中取出的待扩展节点为E。E也不是目标状态节点，并且没有子节点，于是回退到上一层B节点，B只有E这一个子节点且E已经被访问过了，所以继续沿着B返回到其上一层S节点。

S节点还有子节点在OPEN表中，继续从OPEN表中取出当前第一个节点A，A有3个子节点C，D和B，由于B已经在CLOSED表中了，因而只将C，D存入OPEN表中。

后放入的是D，它是当前OPEN表的第一个元素，取出后进行扩展，得到节点G和F并存入OPEN表中。类似地，取出F放入CLOSED表中，F的子节点G已经在OPEN表中了，F没有其他子节点，于是进行回溯，从OPEN表中取出G，并放入CLOSED表中，即得到目标状态节点。扩展示例如图3.6所示。

图3.6　深度优先搜索中OPEN表中节点扩展过程(www.xing528.com)

所以在深度优先搜索中，OPEN表的节点扩展次序依次为：S，B，E，A，D，F，G。同样，可以通过G回溯到S得到解的路径为S-A-D-G。

对于深度优先搜索来说，状态空间可能形成回路，导致出现无穷分支，因此，深度优先搜索只能说可能是完备的，即当状态空间中不存在回路且有限时才是完备的。由于深度优先搜索首先沿着某条路径深入下去，并不能保证找到的第一个解一定是距离初始状态节点最近、路径最短的解，因而说深度优先搜索不具备最优性。如图3.7所示，假设节点g1，g2，g3均为该问题的目标状态节点，则如果从最左边开始进行深度优先搜索，最先搜索到最左边的目标状态节点g1，此时获得的解路径显然没有获得目标状态节点g2的路径短。

图3.7　深度优先搜索示例

从算法的复杂度角度来考虑，假设整个状态空间从初始状态节点开始，每个节点有b个分支，最短的解在第s层，整个状态空间有m层（这也可以用图3.7来示意），那么进行深度优先搜索，最坏的情况为当目标状态节点为最右边支路的g3节点时，需要搜索的节点数为1+b1+b2+…+bm-1=bm-1，所以时间复杂度为O（bm）。对于空间复杂度，需要分别考虑OPEN表和CLOSED表。对于OPEN表，最多存储从初始状态节点开始的某个支路的所有节点。比如OPEN表中将会存储第2层的b个支路子节点，然后取出一个，继续扩展该节点，得到b个子节点，再取出一个，继续下去，直到搜索到第m层的b个子节点，OPEN表堆栈中最多会有（b-1）×（m-1）+1个节点，所以空间复杂度为O（bm）。对于CLOSED表，由于深度优先搜索具有回溯的过程，当搜索完某个支路所有的节点发现没有目标状态节点时，这些节点也不会形成解的回溯路径，所以可以不用保存在CLOSED表中，因此它的复杂度和OPEN表类似，最终得到深度优先搜索的空间复杂度为O（bm），比起宽度优先搜索中的指数级空间复杂度来说小得多。

不难发现，深度优先搜索能很快深入到路径深层，所以有时能很快地获得解，实现求解的高效率，但同时，如果解不在某分支上，而该分支又是无穷分支，则可能得不到解。所以，很多情况下在使用深度优先搜索时，需要对它进行改进，比如采用有界的深度优先搜索。有界的深度优先搜索的基本思想是对深度优先搜索设置一个搜索深度的界限dm，当到达了搜索深度的界限还未发现目标状态节点时，就可以回溯换一个分支进行搜索了，直到该界限内的所有分支都搜索完毕，此时可以考虑放弃搜索或再继续深入。

在有界的深度优先搜索中，如果问题有解，且路径长度dx≤dm，则一定能搜索到目标状态节点，所以界限深度dm的选择非常重要。

关于dm的处理，Richard E.Korf在1985年发表的论文Depth-First Iterative-Deepening：An Optimal Admissible Tree Search提出了一种方案，称为迭代加深的深度优先搜索（DFID，depth-first iterative-deepening）。其过程为：首先进行深度界限为1的深度优先搜索，如果没有找到目标状态节点，那么进行深度界限为2的深度优先搜索，如果又没找到目标状态节点，接着进行深度界限为3的深度优先搜索，这样继续下去，每次迭代把深度界限加1。每一次迭代运算中，状态空间信息并不共享。

虽然这种算法看起来有非常多的冗余，效率比宽度优先搜索和深度优先搜索都低，但是很多情况下，目标状态节点都在比较浅的层中，所以这种算法也不算太“坏”。由于该算法是逐层加深的，因此可以找到最优解。

在这里再来求解传教士与野人过河问题，采用深度优先搜索，搜索过程为：从初始状态节点（3，3，1）开始，对它按照［（1，0），（0，1），（1，1），（2，0），（0，2）］进行扩展，得到下一步状态节点（2，3，0）、（3，2，0）、（2，2，0）、（1，3，0）、（3，1，0），剔除不合法节点，将（3，2，0）、（2，2，0）、（3，1，0）存入OPEN表中；在深度优先搜索中OPEN表采用堆栈来实现，所以取最后存入的（3，1，0）节点进行扩展，得到下一步状态节点（4，1，1）、（3，2，1）、（4，2，1）、（5，1，1）、（3，3，1），只有（3，2，1）符合要求，将它存入OPEN表中；接着就要继续扩展（3，2，1）节点，后入先出的堆栈正好满足此要求，从OPEN表中弹出（3，2，1）节点进行扩展，得到（2，2，0）、（3，1，0）、（2，1，0）、（1，2，0）、（3，0，0），只有（3，0，0）满足条件，将它存入OPEN表中；再取（3，0，0）进行扩展……直到搜索得到解答。