队-列-其他广度优先搜索

一、广度优先搜索的基本思路能的算符序列。因此，对于同一层状态来说，求解问题的价值是相同的。可以按任意顺序来扩展它称为“先进先出表”（FIFO表。listcloed‥open子状态尚待扩展open=closedopen=listmax(见上图)。List while ifopen≥listmax then输出内存溢出信息二、求初始状态所能到达的所有状态procedureexpand(q：node)； varsuccessor：node； i ifsuccessor满足约束条件then 优先搜索不采用递归，因此运算过程比较回溯法简明。在应用上述算法框架解题时，应考虑如下几个【例题12.3.1】求图形面积na*b。摆放矩形时，必须使矩形的边与纸a，b (a，b为正偶数且a，b≤30，1na*b2矩形1左下角坐 矩形1右上角坐 矩形n左下角坐 矩形n右上角坐 分析：1、图形定义

区间为

aa

2 2有a*b个色点的点阵，纸的面积与色点数相等。设squa—染色矩阵，其中squa[i，j]为（i，j）的色码（-b≤ib，-a≤ja a*b≤22fillchar(squa，sizeof(squa)，fori←1ton forj←1to5do读 forj←n1ton3-1 fork←n2ton4-1dosqua[j，k]←n5；squa矩阵中的每一坐标点(x，y)8个可能的相邻点，位于不同方向。(如上图(b))中圆圈内的数字表征这8个方向。括号(△yi，△xi)为方向i的相邻点(y’，x’)与(y，x)的垂直增量和水平增量(1≤i≤8)i(1≤i≤64)colorhave表中存在该颜色，squai的色点(y，x)时，则该坐标送入队列，并0i的相邻坐标送入队列。这为(y，x)open。显然，通过一次广度优先搜索，可得出一个彩x，y list队列设两个指针：态从队尾一端进入list表；3、程序流程procedureexpand(closed，color)；fori←to8 ifsqua[y，x]=color {i方向的相邻点同色，则相邻点位置送入队列，该位置置空}thenbeginlist[open]．x←x；list[open]．y←y；forj←-atoaifsqua[k，j]=i thenbeginclosed←0；open←1；list[open]．x←j；list[open]．y←k； whileopen<>closeddo expand(closed，i)； fori←1to64 if 三、计算初始状态到目标状态的最短路径 succesorsuccesor的father指针出发，⑶如果产生重复子状态的概率很大，则在生成子状态succesor后判别其是否重复于已扩展状态procedureexpand(q：node)；foridoifopen≤listmaxthenifsuccessor满足约束条件thensuccessor．fathe←closed； ifsuccessor是目标状态then 输出路径代价tot-1； ifsuccessor.Statelist[1].staist[cloed].Statethenbegin {状态successor入队}procedureprint(q：node)； ifq．father=0thenbegin elsebegin 状态，则说明由于内存限制而无法找到目标状态。如果从初始状态到达最近的目标状态的长度为l，每一ml-1层的所有状态，而不管目标状态位于m*(ml m愈慢。下面，来看一个实例【例题12.3.2】最少步数[问题描述知道这件事后觉得很有趣，就想试一试，在一个（19*19）A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走，一个走白马。谁用最少的步数走到左上角坐标为(1,1)A、B两点的坐标，想知道1218891、确定出发点要求的是所在的（x1，y1）和白马所在（x2，y2）到达(1,1)目标点的最少步数。虽然两条路径的起点2、数据结构设（0≤k≤192+1步数为0。除此之外的所有元素值设为-1。为了使得马从棋盘内任意位置扩展出的坐标均在s的范围内，s数组的范围扩大至s[-1..21,-1..21]。(i方向上的位置增量存入常量数组dx[i]、dy[i]中（1≤i≤12）3、约束条件4、算法流程fillchar(s,sizeof(s),0);s[1,1]←0; forx1←1to19dofory1←1to19dos[x1,y1]←- {读入和白马的出发位置}whileclosed<opendo ford←1to12 if