广度优先搜索.doc

§12.3广度优先搜索
从初始状态开始， 应用算符生成第一层状态， 检查目标状态是否在这些后继状态中。若没有，再用算符将所有第一层的状态逐一扩展， 得到第二层状态， 并逐一检查第二层状态中是否包含目标状态。若没有， 再用算符逐一扩展第二层的所有状态，……， 如此依次扩展、检查下去，直至发现目标状态为止。这就是所谓的广度优先搜索。
一、广度优先搜索的基本思路
在广度优先搜索中，解答树上状态的扩展沿状态深度的“断层”进行，也就是说，状态的扩展是按它们接近起始状态的程度依次进行的。长度为n+1的任一状态进行扩展之前，必须先考虑长度为n的每种可能的算符序列。因此，对于同一层状态来说，求解问题的价值是相同的。 我们可以按任意顺序来扩展它们，这里采用的原则是先生成的状态先扩展。只要目标状态在解答树的有限层上，广度优先搜索第一次扩展到该状态，便保证找到一条通向它的最佳路径。
为了满足先生成的状态先扩展的原则，我们采用队列的数据结构存贮状态。队列是一种线性表，对于它所有的插入都在表尾的一端进行，所有的删除都在表首的一端进行。如同现实生活中的等车、买票的排队，新来的成员总是加入队尾，每次离开的总是队列头上的人，即当前“最老”的成员。因此，队列也被称为“先进先出表”（FIFO表）。

在广度优先搜索中，我们将扩展出的状态存贮在一个称为list的数组里，数组容量为listmax。list数组采用“先进先出”的队列结构，设两个指针open、closed，分别是队尾指针和队首指针。其中list[1‥cloed-1] 存贮已扩展状态（即这些状态的儿子状态已扩展出）；list[cloed‥open] 存贮待扩展状态（即这些状态的儿子状态尚待扩展）。当open=closed时，则表示队列空；当open=listmax时， 则表示队列满(见上图)。List数组的元素为状态。
type
node=状态的数据类型
var
list：array[1．．listmax]of node ； {队列}
cloed，open：integer； {队首指针和队尾指针}
广度优先搜索的算法流程如下：
open←1；closed←0； {初始状态进入队列}
list[open]←初始状态；
while (closed {若队列非空且未溢出，则移出队首状态，扩展其子状态}
closed←closed+1；
expand(list[closed])； {扩展队首状态的所有子状态}
end；{while}
if open≥listmax {若扩展出的状态数超出list表的容量上限}
then输出内存溢出信息
else找到了初始状态所能到达的所有状态list[1]．．list[open]；

采用广度优先搜索的试题一般有两种类型：
⑴求初始状态所能到达的所有状态
⑵求初始状态到某目标状态的最短路径
试题要求不同，扩展子状态的方式(expand过程)也不同：

二、求初始状态所能到达的所有状态
在求初始状态所能到达的所有状态时，扩展子状态的方式(expand过程)如下
procedure expand(q：node)； {扩展q状态的所有子状态}
var successor：node；
begin
for i取遍所有的算符 do
if open≤listmax then {若队列未满}
begin
算符i作用于q状态产生一个子状态successor；
if successor满足约束条件
then begin
open←open+1；list[open]←successor； {子状态successor 入队}
end；{then}
end；{then}
end；{expand}
显然，初始状态可达的状态个数不应超过listmax个。若超过，则只能求出其中listmax个。由于广度优先搜索不采用递归，因此运算过程比较回溯法简明。我们在应用上述算法框架解题时，应考虑如下几个因素：
⑴定义状态，即如何描述求解过程中每一步的状况和状态间转换的方法；
⑵搜索范围，即如何设计算符的值域，即expand过程中循环变量的初值和终值；
⑶约束条件，即当前扩展出的子状态应满足什么条件方可进入队列；
由于存储所有状态的队列采用了静态数组，因此广度优先搜索的空间效率比较低，容易发生内存溢出。为此我们不妨从以下几个方面考虑优化：
⑴不再生成以重合状态为根的子树。但判断所有子状态是否重复的代价相当大，一般在产生重复状态的概率较大时使用此方法。
⑵状态尽可能占用空间少，既易于扩展子状态的计算，又方便对重合状态的判断；
⑶队列可改用指针类型，以便及时释放无用状态，回收内存；

下面，我们举一个实例
【例题12.3.1】求图形面积
具有不同颜色的n个矩形被叠放在一张白纸上，纸的尺寸为a*b。摆放矩形时，必须使矩形的边与纸的边平行，并且每个矩形整个放在纸的边界之内。因此不同颜色的各种不同图形可在纸上出现。同一颜色的两个区域中如果至少有一个公共点，则可以认为它们是同一图形的一部份；否则认为是不同图形。题目要求计算每一图形的面积。
输入：
a， b， n (a，b为正偶数且a，b≤30，)
矩形1左下角坐标 矩形1右上角坐标 颜色码1
……………………………………………
矩形n左下角坐标 矩形n右上角坐标 颜色码n
注：坐标系的定义为纸的中心，两轴分别平行于纸的两边。颜色码为1～64间的一个正整数。
输出：
按颜色码升序要求输出每个彩色图形的面积。一行为一个彩色图形。格式：
颜色码 图形面积
分析：
1、图形定义
纸中央作坐标原点，过原点作平行于纸两边的y轴和x轴。Y轴的坐标区间为，x轴的坐标区间为（如下图）

纸上的每一坐标位置看作是一个可涂64种颜色的色点，其面积为单位1。这样a*b的纸即成了一个具有a*b个色点的点阵，纸的面积与色点数相等。设
squa—染色矩阵，其中squa[i，j]为（i，j）的色码（-≤i≤，-≤j≤，1≤squa[i，j]≤）
colorhave—颜色标志表，其中colorhave[j]为颜色j存在的标志(1≤j≤)；
我们输入数据的同时构造squa矩阵和colorhave表：
fillchar (squa， sizeof(squa)， 1)；
for i←1 to n do {依次读入每个矩形的信息}
begin
for j←1 to 5 do 读nj； {读入矩形i的信息}
colorhave[n5]←true； {置颜色n5存在}
for j←n1 to n3-1 do {矩形i涂上颜色n5}
for k←n2 to n4-1 do squa[j，k]←n5；
end;{for}
squa矩阵中的每一坐标点(x，y)有8个可能的相邻点，位于不同方向。(如上图(b))中圆圈内的数字表征这8个方向。括号(△yi，△xi)为方向i的相邻点(y’，x’)与(y，x)的垂直增量和水平增量(1≤i≤8)

2、图形面积的计算方法
按颜色码递增顺序搜索每一种颜色。每搜索一种颜色i(1≤i≤64)时，若colorhave表中存在该颜色，则按顺序搜索squa矩阵中的每一个元素；若发现一个具的颜色i的色点(y，x)时，则该坐标送入队列，并将该位置的色码置0，避免重复搜索。然后队首状态出队扩展，将所有色码为i的相邻坐标送入队列。这样按“先进先出”的顺序扩展下去，直至open=closed为止。此时得出(y．x)所在的一个彩色图形，其面积为(y，x)周围同颜色的色点数，即扩展的状态数open。显然，通过一次广度优先搜索，可得出一个彩色图形：
①状态和队列的定义
我们将当前块位置（y，x）作为状态，其相邻方向作为算符。状态和队列的定义如下：
Type
node=record
x，y： shortint； {坐标}
end；
var list：array[1‥listmax] of node； {队列}
open，closed：integer； {队尾指针和队首指针}
list队列设两个指针：
open——队尾指针。每入队一个状态，open+1；
closed——队首指针。每出队一个状态，closed+1。然后扩展出队状态list[closed]，其生成的子状态从队尾一端进入list表；

②搜索范围
将方向数k作为算符，搜索8个相邻块的颜色。显然方向数k的范围为1≤k≤8；
③约束条件

若（y，x）k方向的相邻块同色，则相邻块作为扩展出的子状态入队；

若squa矩阵中有p个涂有颜色i的图形，通过p次广度优先搜索便可计算出这些图形的面积。按照颜色码升序要求类推所有种颜色，可以得出每个彩色图形的面积。

3、程序流程
①扩展队首状态list[closed]
设当前扩展list[closed]，该状态对应坐标的颜色为color。我们通过expand过程将其四周同色的相邻点送入队列：
procedure expand (closed， color)；
begin
for i←to 8 do {依次搜索8个相邻方向}
begin
x←list[closed]．x+△xi； {生成i方向的相邻点坐标}
y←list[closed]．y+△yi；
if squa[y，x]=color {若i方向的相邻点同色，则相邻点位置送入队列，该位置置空}
then begin
open←open+1；
list[open]．x←x； list[open]．y←y；
squa[y，x]←0；
end；{then}
end；{for}
end；{expand}

②计算和输出涂有颜色i的所有图形面积
for k←-todo
for j←-todo
if squa[k，j]=i {若(k，j)为颜色i，则(k，j)送入队列}
then begin
closed←0； open←1；
list[open]．x←j； list[open]．y←k；
squa[k，j]←0； {置(k，j)为空}
while open <> closed do {通过宽度优先搜索计算(k，j)所在的图形面积}
begin
closed←closed+1； {队首状态出队}
expand (closed， i)； {待扩展队首状态，相邻的同色点入队}
end；{while}
输出涂有颜色i的一个图形面积为open；
end；{then}

显然，主程序为
for i←1 to 64 do {按颜色码递增顺序搜索}
if colorhave[i] {存在颜色i的图形}
then 计算和输出涂有颜色i的所有图形面积；

三、计算初始状态到目标状态的最短路径
求最短路径的广度优先搜索算法，在扩展状态时有如下不同之处：
⑴每个状态需要设立父指针father，因为每扩展出一个子状态succesor，需通过其father指针确认其与list[closed]的父子关系。为此，状态的数据类型可按如下方式定义
type
node=recode
state：状态的数据类型；
father：integer； {父指针，指向父状态在list队列中的下标}
end；
⑵需判别扩展出的子状态succesor是否为目标状态。若是目标状态，则从succesor的father指针出发，递归输出初始状态至该状态的最短路径，并退出程序；
⑶如果产生重复子状态的概率很大，则在生成子状态succesor后判别其是否重复于已扩展状态(list[1]．．list[closed])：若不重复，succesor入队；否则由于重合在两表中的状态是位于successor的上层或同一层，其路径代价必小于或等于succesor的路径代价，因此不再重复以successor为根的子树，避免了多余子状态的计算。但如果产生重复子状态的概率小，则不必进行重复判断，因为对所有子状态重复判断的代价是相当大的。
在求最短路径时，扩展子状态的方式(expand过程)如下
procedure expand(q：node)；
var
successor：node；
tot：integer；
begin
for i取遍算符的所有可能值 do
if open≤listmax then
begin
算符i作用于q．state产生子状态successor；
if successor满足约束条件then
begin
successor．fathe←closed ； {设置子状态successor的父指针 }
if successor是目标状态then
begin
tot←0； {路径代价初始化}
print(successor)； {递归输出初始状态至状态successor的路径}
输出路径代价tot-1；
halt； {退出程序}
end；{then}
if successor.State与list[1].state‥list[cloed].State各不相同
then begin {若产生重复子状态的概率小时，则避免使用该判断}
open←open+1；list[open]←successor； {状态successor入队}
end；{then}
end；{then}
end；{then}
end；{expand}
其中print的过程说明为：
procedure print(q：node)； {递归输出初始状态至q状态的路径}
begin
if q．father=0 then begin {输出根状态q并累计路径代价}
tot←tot+1；
输出q．state；
end{then}
else begin {递归输出初始状态至目标状态q的路径并累计路径代价}
print(list[q．father])；
tot←tot+1；
输出q．state
end；{else}
end；{print}

从广度优先搜索的算法流程可以看出，若当队列空（closed=open）时还未搜索到目标状态，则说明初始状态与目标状态之间根本不存在任何路径，失败退出；若当队列满（open≥maxlist）时还未搜索到目标状态，则说明由于内存限制而无法找到目标状态。如果从初始状态到达最近的目标状态的长度为l，每一个状态可扩展的子状态的个数为m，则它必须在解答树上扩展完l-1层的所有状态，而不管目标状态位于哪条树枝上。在整个搜索过程中，扩展的状态数为(忽略由于不满足约束条件而不允许扩展的状态数，即以丰满的完全m叉树计算)。由此看出状态数基本上以指数增长，l愈长，搜索空间愈大，时间愈慢。 下面，我们来看一个实例
【例题12.3.2】最少步数
[问题描述]
　　在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（19*19）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点的可能最少步数。
[样例]
输入：
　12 16
18 10
输出：
　8
9
题解
由于A、B两点是随机输入的，因此无法找到计算最少步数的数学规律，只能通过广度优先搜索的办法求解。
1、确定出发点
从（x,y）出发通过一次广度优先搜索，可以找到从(x,y)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（x1，y1）和白马所在（x2，y2）到达 (1,1) 目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点(1,1)作为起点，这样只需要一次广度优先搜索便可以得到（x1，y1）和（x2，y2）到达(1,1)的最少步数。
2、数据结构
设
queue——队列，存储从(1,1)可达的点（queue[k,1..2]）以及到达该点所需要的最少步数（queue[k,3]）（0≤k≤192+1）。队列的首指针为closed，尾指针为open。初始时，queue中只有一个元素为(1,1)，最少步数为0。
S——记录(1,1)到每点所需要的最少步数。显然，问题的答案是s[x1,y2]和s[x2,y2]。初始时，s[1,1]为0，除此之外的所有元素值设为-1。为了使得马从棋盘内任意位置扩展出的坐标均在s的范围内，我们将s数组的范围扩大至s[-1..21,-1..21]。
dx、dy——移动后的位置增量数组。马有12种不同的扩展方向：
马走“日”：(x-2,y-1)(x-1,y-2)(x-2,y+1)(x-1,y+2)(x+2,y-1)(x+1,y-2)(x+2,y+1)(x+1,y+2)
马走“田”：(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2)
我们将i方向上的位置增量存入常量数组dx[i]、dy[i]中（1≤i≤12）
const
dx：array[1..12] of integer=(-2,-2,-1,1,2,2,2,2,1,-1,-2,-2);
dy：array[1..12] of integer=(-1,-2,-2,-2,-2,-1,1,2,2,2,2,1);

3、约束条件
⑴不能越出界外。由于马的所有可能的落脚点s均在s的范围内，因此一旦马越出界外，就将其s值赋为0，表示“已经扩展过，且(1,1)到达其最少需要0步”。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。
⑵该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展下去。
由此得出，马的跳后位置（x,y）是否可以入队的约束条件是s[x,y]<0

4、算法流程
fillchar(s,sizeof(s),0); s[1,1]←0; {s数组的初始化}
for x1←1 to 19 do
for y1←1 to 19 do s[x1,y1]←-1;
fillchar(que,sizeof(que),0); { 队列初始化}
open←1;closed←0; {初始位置入队}
que[1,1]←1que[1,2]←1;
read(x1,y1,x2,y2); {读入黑马和白马的出发位置}
while closed begin
x←que[closed,1]+dx[d]; {计算马按d方向跳跃后的位置}
y←que[closed,2]+dy[d];
if s[x,y]<0 then {若（x,y）满足约束条件}
begin
s[x,y]←que[closed,3]+1; {计算(1,1)到(x,y)的最少步数}
inc(open); {（x,y）和（1,1）至（x,y）的最少步数入队}
que[open,1]←x; que[open,2]←y; que[open,3]←s[x,y];
end;{then}
end;{for}
end;{of while}
end; {of work}
writeln(s[x1,y1]); writeln(s[x2,y2]); {输出问题的解}