广度优先搜索

1、8/812。3广度优先搜索从初始状态开始，应用算符生成第一层状态， 检查目标状态是否在这些后继状态中.若没有，再用算符将所有第一层的状态逐一扩展， 得到第二层状态，并逐一检查第二层状态中是否包含目标状态。若没有， 再用算符逐一扩展第二层的所有状态， 如此依次扩展、检查下去，直至发现目标状态为止。这就是所谓的广度优先搜索.一、广度优先搜索的基本思路 在广度优先搜索中，解答树上状态的扩展沿状态深度的“断层”进行，也就是说,状态的扩展是按它们接近起始状态的程度依次进行的。长度为n+1的任一状态进行扩展之前，必须先考虑长度为n的每种可能的算符序列.因此，对于同一层状态来说，求解问题的价值是相同的。 我

2、们可以按任意顺序来扩展它们，这里采用的原则是先生成的状态先扩展。只要目标状态在解答树的有限层上，广度优先搜索第一次扩展到该状态,便保证找到一条通向它的最佳路径。 为了满足先生成的状态先扩展的原则，我们采用队列的数据结构存贮状态.队列是一种线性表，对于它所有的插入都在表尾的一端进行，所有的删除都在表首的一端进行。如同现实生活中的等车、买票的排队，新来的成员总是加入队尾，每次离开的总是队列头上的人，即当前“最老的成员.因此，队列也被称为“先进先出表”（FIFO表)。 在广度优先搜索中,我们将扩展出的状态存贮在一个称为is的数组里，数组容量为lstm。lis数组采用“先进先出的队列结构,设两个指针o

3、pen、clse,分别是队尾指针和队首指针.其中listcd- 存贮已扩展状态(即这些状态的儿子状态已扩展出);listcloopen 存贮待扩展状态（即这些状态的儿子状态尚待扩展）。当pe=coed时，则表示队列空;当pn=listmx时, 则表示队列满（见上图）.List数组的元素为状态。 p node状态的数据类型 r li：ay。listaxofod ; 队列 loe,oen:integer； 队首指针和队尾指针 广度优先搜索的算法流程如下： pen1;closed； 初始状态进入队列 liopen初始状态; whle（lsedopn)and（oenlismx）do begi 若队列非

4、空且未溢出,则移出队首状态,扩展其子状态 cosdcose+； expand（litlos)； 扩展队首状态的所有子状态 en；while if openlisx 若扩展出的状态数超出list表的容量上限 the输出内存溢出信息 lse找到了初始状态所能到达的所有状态ist1.listopn;采用广度优先搜索的试题一般有两种类型：求初始状态所能到达的所有状态求初始状态到某目标状态的最短路径试题要求不同，扩展子状态的方式(exand过程）也不同:二、求初始状态所能到达的所有状态在求初始状态所能到达的所有状态时,扩展子状态的方式(expad过程）如下 prceure expad（：nod）; 扩展

5、q状态的所有子状态 varsuccessor：nod； begin fo i取遍所有的算符 do if pelistmax th 若队列未满 bgn 算符i作用于状态产生一个子状态ucsor; fucessor满足约束条件 then egin penopen+；lisopensucesor; 子状态successor 入队 end；hen end；thn d;expand显然，初始状态可达的状态个数不应超过litma个。若超过，则只能求出其中listmax个。由于广度优先搜索不采用递归，因此运算过程比较回溯法简明。我们在应用上述算法框架解题时，应考虑如下几个因素:定义状态,即如何描述求解过程中

6、每一步的状况和状态间转换的方法；搜索范围，即如何设计算符的值域，即expan过程中循环变量的初值和终值；约束条件，即当前扩展出的子状态应满足什么条件方可进入队列；由于存储所有状态的队列采用了静态数组，因此广度优先搜索的空间效率比较低，容易发生内存溢出.为此我们不妨从以下几个方面考虑优化:不再生成以重合状态为根的子树。但判断所有子状态是否重复的代价相当大，一般在产生重复状态的概率较大时使用此方法。状态尽可能占用空间少，既易于扩展子状态的计算，又方便对重合状态的判断；队列可改用指针类型，以便及时释放无用状态,回收内存;下面,我们举一个实例【例题2 具有不同颜色的个矩形被叠放在一张白纸上,纸的尺寸为

7、ab。摆放矩形时，必须使矩形的边与纸的边平行，并且每个矩形整个放在纸的边界之内。因此不同颜色的各种不同图形可在纸上出现。同一颜色的两个区域中如果至少有一个公共点,则可以认为它们是同一图形的一部份;否则认为是不同图形。题目要求计算每一图形的面积。输入：, b，n （a，b为正偶数且，,）矩形1左下角坐标 矩形1右上角坐标 颜色码1矩形n左下角坐标 矩形右上角坐标 颜色码n注：坐标系的定义为纸的中心,两轴分别平行于纸的两边。颜色码为16间的一个正整数。输出：按颜色码升序要求输出每个彩色图形的面积。一行为一个彩色图形。格式: 颜色码 图形面积分析:1、图形定义纸中央作坐标原点,过原点作平行于纸两边的

8、y轴和x轴。Y轴的坐标区间为，轴的坐标区间为(如下图)纸上的每一坐标位置看作是一个可涂6种颜色的色点,其面积为单位。这样ab的纸即成了一个具有ab个色点的点阵，纸的面积与色点数相等。设 s-染色矩阵,其中sqai,j为（i，j)的色码（-i，j，1sua,j） olhave-颜色标志表，其中oorave为颜色存在的标志（1j）；我们输入数据的同时构造sa矩阵和corhave表: fillcar （squa,sizf（qua）, ）; for o n o 依次读入每个矩形的信息egin frj1to5 d 读n; 读入矩形i的信息 corhvn5te; 置颜色n5存在 for jn to n3-

9、1 do 矩形i涂上颜色5 for kn2 to4 do squaj,kn5； n；forsqua矩阵中的每一坐标点（,y)有8个可能的相邻点,位于不同方向.（如上图(b）中圆圈内的数字表征这8个方向。括号（i，x)为方向i的相邻点(y，x）与(y，x）的垂直增量和水平增量(1i8)、图形面积的计算方法按颜色码递增顺序搜索每一种颜色。每搜索一种颜色i（i6）时,若olohav表中存在该颜色，则按顺序搜索squ矩阵中的每一个元素；若发现一个具的颜色i的色点（y，x)时，则该坐标送入队列，并将该位置的色码置,避免重复搜索。然后队首状态出队扩展，将所有色码为i的相邻坐标送入队列。这样按“先进先出”的

10、顺序扩展下去,直至oen=close为止。此时得出（y.x)所在的一个彩色图形，其面积为(y，x)周围同颜色的色点数,即扩展的状态数opn。显然，通过一次广度优先搜索，可得出一个彩色图形：状态和队列的定义我们将当前块位置（y，x)作为状态，其相邻方向作为算符.状态和队列的定义如下：yp de=recor x，: shotint; 坐标 end；var list:ra1litmax of node; 队列 open,csd：integer； 队尾指针和队首指针ist队列设两个指针:opn-队尾指针。每入队一个状态，open+1；cloed-队首指针。每出队一个状态,clsed+1。然后扩展出队状

11、态lstclose，其生成的子状态从队尾一端进入list表；搜索范围将方向数k作为算符,搜索8个相邻块的颜色.显然方向数k的范围为k8;约束条件若（,x）k方向的相邻块同色,则相邻块作为扩展出的子状态入队; 若squa矩阵中有个涂有颜色i的图形,通过次广度优先搜索便可计算出这些图形的面积。按照颜色码升序要求类推所有种颜色，可以得出每个彩色图形的面积.3、程序流程扩展队首状态listclosed 设当前扩展listlosed,该状态对应坐标的颜色为ol.我们通过epan过程将其四周同色的相邻点送入队列： predur pa （losd,color)； bgin fo ito 8 依次搜索8个相邻

12、方向 egin lstclosed.xi； 生成方向的相邻点坐标 ylstcose.y+yi; ifsqua，x=clr 若方向的相邻点同色，则相邻点位置送入队列,该位置置空 thenbegin opnopen+； istopenxx； listopen。yy； quy，x; end；tn nd;for end；expand计算和输出涂有颜色的所有图形面积 foktodo o j-o isa，j=i 若（,j）为颜色i，则(k,）送入队列 ten begi sed0； opn1； lstopen.xj； istopnyk； squk,j0； 置(k，j)为空 we ope sed do 通过宽

13、度优先搜索计算（k，j）所在的图形面积 bgin loedcosed+1; 队首状态出队 exand(loed， i)； 待扩展队首状态，相邻的同色点入队 en;ile 输出涂有颜色的一个图形面积为pen; e；hn显然，主程序为 for i1 to64do 按颜色码递增顺序搜索 olohavi 存在颜色i的图形 thn 计算和输出涂有颜色i的所有图形面积;三、计算初始状态到目标状态的最短路径求最短路径的广度优先搜索算法，在扩展状态时有如下不同之处:每个状态需要设立父指针fther,因为每扩展出一个子状态suceor，需通过其father指针确认其与iscled的父子关系。为此，状态的数据类型

14、可按如下方式定义 typ norecoett：状态的数据类型;athe：teger; 父指针，指向父状态在is队列中的下标 e;需判别扩展出的子状态suceor是否为目标状态。若是目标状态，则从ccesor的father指针出发,递归输出初始状态至该状态的最短路径，并退出程序；如果产生重复子状态的概率很大，则在生成子状态scceor后判别其是否重复于已扩展状态(li1lscloed）:若不重复，sucesor入队；否则由于重合在两表中的状态是位于susso的上层或同一层,其路径代价必小于或等于ucsor的路径代价,因此不再重复以sucesr为根的子树，避免了多余子状态的计算。但如果产生重复子状

15、态的概率小,则不必进行重复判断,因为对所有子状态重复判断的代价是相当大的.在求最短路径时，扩展子状态的方式(expa过程）如下pocedure exand(q:node); var successor:node； t:inter；bgi for i取遍算符的所有可能值do if openlstm the egn 算符i作用于stat产生子状态successor； if sucssor满足约束条件hn bgi sucesor。atheclosd ; 设置子状态sccesso的父指针 if uceor是目标状态hn begn tt0； 路径代价初始化 rint(scessor）； 递归输出初始状态

16、至状态suessor的路径 输出路径代价tot-1； halt； 退出程序 end；the fsuccssoSa与ist1.satlitcloed。State各不相同 the begin 若产生重复子状态的概率小时，则避免使用该判断 openop1;stensucceso; 状态ccss入队 ed；the end；thn end；he nd；expan其中prt的过程说明为: procedur prt(q：node）； 递归输出初始状态至q状态的路径 begin f qfather= the egi 输出根状态并累计路径代价 oto+； 输出q.stt; endthen ls egin 递归输

17、出初始状态至目标状态的路径并累计路径代价 print(stqathr)； tto+； 输出qstat ed；el ed;pr从广度优先搜索的算法流程可以看出,若当队列空（cosed=opn)时还未搜索到目标状态，则说明初始状态与目标状态之间根本不存在任何路径，失败退出；若当队列满(penaxlis)时还未搜索到目标状态，则说明由于内存限制而无法找到目标状态。如果从初始状态到达最近的目标状态的长度为l,每一个状态可扩展的子状态的个数为m,则它必须在解答树上扩展完l1层的所有状态，而不管目标状态位于哪条树枝上.在整个搜索过程中，扩展的状态数为（忽略由于不满足约束条件而不允许扩展的状态数，即以丰满的

18、完全m叉树计算）。由此看出状态数基本上以指数增长，l愈长,搜索空间愈大,时间愈慢。下面，我们来看一个实例【例题2。2问题描述 在各种棋中,棋子的走法总是一定的，如中国象棋中马走“日。有一位小学生就想如果马能有两种走法将增加其趣味性，因此,他规定马既能按“日”走,也能如象一样走“田字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个(919)的围棋盘上任选两点A、B，A点放上黑子，B点放上白子,代表两匹马.棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为（1，1)的点时,谁获胜.现在他请你帮忙，给你A、两点的坐标,想知道两个位

19、置到（1,）点的可能最少步数.样例输入：1 1 110输出：8 题解由于A、B两点是随机输入的，因此无法找到计算最少步数的数学规律，只能通过广度优先搜索的办法求解。1、确定出发点从(,)出发通过一次广度优先搜索,可以找到从（x,y)至棋盘上所有可达点的最少步数.而问题中要求的是黑马所在的（x1,)和白马所在（x，y2）到达（，1） 目标点的最少步数。虽然两条路径的起点不一样,但是它们的终点却是一样的。如果我们将终点（,1)作为起点,这样只需要一次广度优先搜索便可以得到(1，1）和（x,y2）到达(1，1)的最少步数。2、数据结构设queue队列，存储从(1,1)可达的点(euek，1。）以及到

20、达该点所需要的最少步数(euek,3)（092+1）。队列的首指针为od，尾指针为open。初始时，ueu中只有一个元素为(1,1），最少步数为。S.-记录（1，1)到每点所需要的最少步数.显然,问题的答案是sx，y2和sx2，y2。初始时，s1，为0，除此之外的所有元素值设为-1。为了使得马从棋盘内任意位置扩展出的坐标均在s的范围内,我们将s数组的范围扩大至s。21,-1。21。dx、dy移动后的位置增量数组。马有1种不同的扩展方向:马走“日”：（x，y1）(,y2）（x2,y+)（-1，y2）（x+2,y)（x,2）（x+2,+1）(1,y2)马走“田”：(x2，-2）(x2，y+2）(x+2，2)(x，y）我们将i方向上的位置增量存入常量数组i、dyi中（1i12)consdx：aray1。1 of inter=（,2，1,1,2,2,2,2，1,1，2，2）； y:ary1。1 f integ=(-1，-2，,-2，-,-1,1