您的当前位置是：第三章 确定性推理>>学习内容>>知识点二

一、宽度优先搜索

1．定义

如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索（breadth-first search），如图3.3所示。

2．基本思想

从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。OPEN表中的节点总是按进入的先后排序排列，先进入的节点排在前面，后进入的节点排在后面。

3．特点

这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

4．宽度优先搜索算法

宽度优先搜索算法如下，具体流程如图3.4所示。

①把起始节点放到OPEN表中（如果该起始节点为一目标节点，则求得一个解答）。

②如果OPEN是个空表，则没有解，失败退出；否则继续。

③把第一个节点（节点n）从OPEN表移出，并把它放入CLOSED的扩展节点表中。

④扩展节点n。如果没有后继节点，则转向上述第②步。

⑤把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。

⑥如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第②步。

例3.1 8数码难题。

在3×3的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0，目标状态Sg，如图3.5所示。可以使用的操作有空格左移，空格上移，空格右移，空格下移，即只允许把位于空格左、上、右、下方的牌移入空格。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径。

问题的搜索过程如图3.6所示，图中的圆圈内的数字表示节点的扩展顺序。

1  2  3  4  5