2.1.3　宽度优先搜索

如果搜索顺利，则纵向搜索将快速找到解。但在最坏的情况下，也会导致灾难性的结果。那么，有没有一种更稳定的搜索方法？其中一种有效的方法是宽度优先搜索（width-first search）。在这个方法中，我们检查树的某个级别（深度）处出现的所有节点，然后才会进入下一级（深度）（见图2.8）。因此，它也被称为“横向搜索”。横向搜索具有以下优点。

1）只要有解，那么肯定能找到解。

2）找到目标的最短路径（解）。

但另一方面，它的缺点就是会占用大量内存资源。树的节点数会随着深度的加深呈现指数级别的增长，但又不得不记住所有这些信息。

图2.8　深度优先搜索与宽度优先搜索

横向搜索的算法如下所示。

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

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

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

Step3　先从OPEN里的首端开始搜索节点。并将其作为k，从OPEN里面去除k后把它加入CLOSED。

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

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

然后返回Step2。

Step5　如果不存在k可到达的节点，则返回Step2。

在Step4中向OPEN的末端追加了新的状态，然后从Step3的首端取出k是十分重要的。根据这个步骤，会从树中比较浅的节点开始一一尝试。

那么，我们再来思考一下传教士与野人的问题。这个问题将以如图2.9所示的方式进行搜索。

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.41）

（1,1,1,1,R）=k2　（2.42）

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

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

以上状态都没有被包含在CLOSED里面，因此

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

然后返回Step2。

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

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

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

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

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

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

因为s被包含在CLOSED，所以只把k5添加至OPEN，然后返回Step2。结果如下：

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

Step4　扩展k3可以得到k5和s，但它们都无法添加至OPEN和CLOSED。接着返回Step2。

Step4　扩展k4获得s，但无法将其添加至OPEN和CLOSED，此时

OPEN:=（k5）　（2.49）

CLOSED:=（s,k1,k2,k3,k4）　（2.50）

接着返回Step2。

图2.9　横向搜索（传教士与野人的问题）

接下来我们再看看稍微复杂的8谜题。初始状态和终点状态与之前的纵向搜索是相同的，也就是说初始状态为：

---

X23
146
758

---

终点状态为：

---

123
456
78X

---

这种情况下的搜索结果如图2.10所示。节点号是扩展生成的节点的顺序。从图2.10中可以看出，正确的答案是在第29个生成的节点获得的。在横向搜索中，节点生成号（按生成顺序）与节点扩展号相同。也就是说以如下顺序扩展。

1→2→3→4→5→6→7→8→9→10→11→12→…　（2.51）

与纵向搜索相比，横向搜索具有更少的扩展节点和较小的深度。但是，横向搜索并非总是更好。

图2.10　8谜题（横向搜索）