2.1.2　深度优先搜索

深度优先搜索（depth-first search）是一种往树结构深处搜索的方法。这个方法也被称为“纵向搜索”。使用这种方法时，如果运气好，则可以很快求解，但反过来，如果运气差，则找不到解的可能性也是存在的。以下是这个方法的算法。

Step1　生成包含初始状态s的链表（list）OPEN:=(s)。

Step2　如果OPEN为空，则以无解为终结。

Step3　取出OPEN里面最前面的状态作为k，然后从OPEN里面去除k。

Step4　将从k出发可以到达的状态作为k1,k2,…,kl。如果其中存在终点（目标状态空间）则表示“成功”。如果不存在，则OPEN:=（k1,k2,…kl:OPEN），然后返回至Step 2。也就是说，在OPEN的最前面加入k1,k2,…,kl。

Step5　如果没有可以到达的状态，则返回Step2。

在这里，（A:B）表示在链表A后面添加链表B。假设A=（1,2,3）、B=（a,b,c），那么（A:B）=（1,2,3,a,b,c）。所以，以上的算法就是把k1,k2,…,kl添加到OPEN的首位位置。在这种情况下，OPEN里的元素会从首位位置被依次取出，越是前面被取出的元素，越要以树的深度作为优先级进行搜索。值得注意的是，从k生成k1,k2,…,kl（也就是依次生成可以到达的状态），被称为扩展节点k。

是否注意到以上的算法中含有一个Bug？就是存在再次陷入之前到达过的相同状态的可能性。从而导致不断地兜圈子，无法找到有效解。为了避免出现这种情况，需要准备新的变量CLOSED，然后把Step3和Step4改为如下所示。

Step3　把OPEN的首位状态取出作为k。把k加入CLOSED。然后删除OPEN里的k。

Step4　从k可到达的状态定义为k1,k2,…,kl。如果其中有终点（目标状态），则为成功——流程结束。如果没有，则把CLOSED和OPEN都不包含的状态作为k'1,…,k'm。然后有OPEN:=（k'1,…,k'm:OPEN），并返回Step2。

这种方法使已经生成的节点不会被加进OPEN。

那么，我们用这种搜索方法试着解决传教士与野人的问题吧。

Step1　初始状态s:=（2,2,0,0,L），然后OPEN:=(s)。

Step3　OPEN:=()，k:=s，CLOSED:=(s)。

Step4　从k=s可以到达的状态如下所示。

（0,2,2,0,R）=k1　（2.14）

（1,1,1,1,R）=k2　（2.15）

（2,0,0,2,R）=k3　（2.16）

（2,1,0,1,R）=k4　（2.17）

以上状态都被添加至CLOSED里面，然后

OPEN:=（k1,k2,k3,k4）　（2.18）

并返回Step2。

Step3　OPEN:=（k2,k3,k4），k:=k1，CLOSED:=（k1,s）。

Step4　虽然从k=k1可以到达的可能状态有s，但它被包含在CLOSED里，而不包含在OPENED里，所以直接返回Step2。

Step3　OPEN:=（k3,k4），k:=k2，CLOSED:=（k2,k1,s）。

Step4　从k=k2可以到达的可能状态如下所示。

（2,2,0,0,L）=s　（2.19）

（2,1,0,1,L）=k5　（2.20）

s被包含在CLOSED里，所以只有k5添加至OPEN，并返回Step2。结果如下所示。

OPEN:=（k5,k3,k4）　（2.21）

Step3　OPEN:=（k3,k4），k:=k5，CLOSED:=（k5,k2,k1,s）。

Step4　从k=k5可以到达的状态如下所示。

（1,1,1,1,R）=k2　（2.22）

（2,0,0,2,R）=k3　（2.23）

（0,1,2,1,R）=k6　（2.24）

其中k2和k3分别包含在OPENED和CLOSED里，所以不会被采用，从而只有k5添加至OPEN。

如果这样的搜索方法一直继续下去，会如图2.5所示，在第六次节点扩展的时候可以到达（0,0,2,2,R）。图2.5的节点号和Step4扩展的节点顺序一一对应。当搜索结束并到达终点以后，S里还剩下如下状态。

（1,1,1,1,L）　（2.25）

（2,0,0,2,R）　（2.26）

（2,1,0,1,R）　（2.27）

图2.5　纵向搜索（传教士与野人问题）

从图2.5可以看出，深度优先的搜索就是对树结构进行纵向的搜索，因此它被称为“纵向搜索”。纵向搜索的重点在于，如果像（0,2,2,0,R）这样后面没有可以到达的状态，就会重新考虑OPEN里包含的状态。这时上面的例子就会重新选择状态（1,1,1,1,R）。该动作被称为“回溯”（backtrack），这样就可以从无路可前进的状态中重新恢复过来。关于这一点，将会在3.1节中进行详细说明。

在纵向搜索的Step5里加入的状态顺序是很重要的。在前面的例子里状态顺序如下所示。

OPEN:=（k1,k2,k3,k4）　（2.28）

但如果状态顺序如下：

OPEN:=（k1,k4,k2,k3）　（2.29）

则k1和k4都会发生回溯。如果状态顺序如下所示：

OPEN:=（k2,k1,k3,k4）　（2.30）

那么，回溯一次都不会发生。如同上述内容，OPEN里的放置顺序的不同会导致到达终点（得到解）的效率（节点的扩展数）也完全不同。

以上这种现象可能还会导致更严重的问题——无法找到解。想象一下如图2.6a所示的情况。从s可到达k1和k2。从k2可以到达终点。但另一方面，从k1不仅无法到达终点，而且会沿搜索树无限地伸展下去。这个时候，以下的两种顺序会决定性地左右搜索树的性能。

图2.6　深度限制和纵向搜索

OPEN:=（k1,k2）　（2.31）

OPEN:=（k2,k1）　（2.32）

针对这种问题进行防范的方法就是搜索到一定的深度后强制回溯。在这里，树的深度是指从根节点开始的最短路径距离。比如：

根节点=深度1　（2.33）

根节点的子节点=深度2　（2.34）

根节点的孙节点=深度3　（2.35）

一般来说，节点的深度如下：

节点的深度：=（父节点的深度）+1　（2.36）

但如果在图构造上有多个父节点时，则节点的深度如下：

节点的深度：=min{父节点的深度}+1　（2.37）

如果各个节点的深度可以定义，那么可以如下实现回溯。第n阶段考虑深度为n×D的节点，并在深度为n×D（D为进行回溯的深度极限值）时回溯。如果在OPEN中没有深度小于n×D的节点，则n:=n+1并进入下一阶段。这保证了即使对于图2.6a所示的例子也总能获得解（见图2.6b）。这种方法称为“迭代加深”。

迭代加深的算法总结如下所示。

Step1　n:=1,s作为初始状态。

然后OPEN:=(s),CLOSED:=()。

Step2　如果OPEN为空，那么就说明该问题无解并终止搜索。

Step3　先从OPEN里的首端开始搜索，取出深度n×D以下的节点作为k。从OPEN里去除k后把它加入CLOSED。如果没有这样的节点，则前往Step5。

Step4　将k可到达的节点分别定义为k1,…,km。其中既没有被包含在OPEN中也没有包含在CLOSED中的节点定义为k'1,…,k'l。如果k'1,…,k'l中有目标状态，则说明到达了终点。如果没有目标状态，则

OPEN:=（k'1,…,k'l: OPEN）　（2.38）

然后返回Step2。如果没有k可达到的节点，则返回Step2。

Step5　n:=n+1，然后返回Step3。

接下来，让我们根据8谜题的例子来看看这个搜索过程。8谜题的规模比起开始提到的15谜题要小。将标号1到8的滑块放入3×3的盒子中，并不断地通过把滑块滑入空白位置（在下面用x表示空白位置）来实现目标。

图2.7是初始状态为

---

x23
146
758

---

终点状态为

---

123
456
78x

---

的纵向搜索的结果。在这里将D（进行回溯的深度极限值）赋值为6。节点号是按照在Step4中扩展的顺序生成的（相当于k'1,…,k'l）。也就是说，节点号是按照生成顺序赋予的，有可能与被扩展的节点顺序不同。图2.7以如下所示的顺序扩展：

1→2→4→6→7→8→5→13→16→17→14→20→…　（2.39）

图2.7　8谜题（纵向搜索）

从纵向搜索的结果中可以得知，在第41个节点中得到了解。