队列宽搜及其优化课件

1、 队列、宽搜及其优化臧方青TelQ：54703551E-mail：本节课的主要内容1.队列的简单回顾。2.五个不同风格的宽搜的例题。3.宽搜的优化一、二及其例题。4.宽搜的其它优化简介。一：队列的回顾与简单宽搜实例1、队列的知识回顾队列是一种先进先出（First In First Out,缩写为FIFO）的线性表。它只允许在表的一端插入元素，在表的另一端删除元素。正象排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队的未尾（插入）。通常把队列的删除和插入操作分别称为出队和入队。允许出队的一端称为队头(front)，允许入队的一端称为队尾(rear

2、)。所有需要进队的数据，只能从队尾进入，队列中的数据只能从队头离去。这时头指针向上移动一个位置，指向q(3)，表示q(3)已出队。见图1 (b)。如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1，这时q(9)入队，见图1 (c)。当队尾已经处理在最上面时，即tail=10，见图1 (d)，如果还要执行入队操作，则要发生上溢，但实际上队列中还有三个空位置，所以这种溢出称为假溢出。克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就翻转为。在结构

3、上采用这种技巧来存储的队列称为循环队列，见图2。循环队列的入队算法如下：1.tail=tail+1；2.若tail=n+1，则tail=1；3.若tail=head，尾指针与头指针重合，表示队列已满，需作上溢处理；4.否则，q(tail)=X，结束（X为新入队元素）。队列和栈一样，有着非常广泛的应用。分析：我们可以利用“队结构”来模拟绕圈数的过程。数1到4时，每数一人，则出队并把其插入到队尾，数到5时，则出队，并输出该人的编号，表示从圈里出去一人。重复上述操作十三次即可。因每入队4次，才出除去一人，因此共需13+13*4= 65个存贮单元。初始化时，把113顺序入队表示这13人开始时的顺序。广

4、度优先搜索基本算法的基本结构：program bfs;初始化；建立队列data;设队列首指针closed:=0;队列尾指针open:=1;repeatclosed 增1，取出closed所指结点进行扩展； for i:=1 to r do begin if 子结点符合条件then begin open增1，并把新结点存入数据库队尾；if新结点与原有结点有重复 then 删于该结点(open减1)else if 新结点即目标 then 输出并退出 ; endif; endfor;until closed=open;队列为空输入：每组测试数据的第一行有两个整数w，h （1=w，h=75），表示平板

5、的宽和高。 接下来h行描述平板信息，每行包含w个字符，如果某格子有一张牌，则这个格子上有个X，否则是一个空格。 平板上最左上角格子的坐标为（1，1），最右下角格子的坐标为（w,h）。 接下来的m行，每行有四个数x1， y1， x2， y2 ，且满足1=x1,x2=w，1=y1,y2=h， 表示两张牌的坐标（这两张牌的坐标总是不同的）。 输出：输出文件中，对于每一对牌输出占一行，为连接这一对牌的路径最少包含的线段数。 如果不存在路径则输出0。 样例输入：（mj.in）5 4XXXXXX X XXX X XXX 32 3 5 31 3 4 42 3 3 4输出(mj.out)560 广搜算法：co

6、nst maxw=10;maxh=10; xf:array1.4of shortint=(1,0,-1,0); yf:array1.4of shortint=(0,1,0,-1);var a:array1.(maxw+1)*(maxh+1),1.2of integer; b:array-1.maxw+2,-1.maxh+2of boolean; c:array-1.maxw+2,-1.maxh+2of integer; w,h,n,i,j,k,xm,ym,t,z,x,y:integer; ok:boolean;procedure init; var i,j:integer; ch:char;

7、begin readln(w,h); for i:=0 to w+1 do for j:=0 to h+1 do bi,j:=true; for j:=1 to h do begin for i:=1 to w do begin read(ch);bi,j:=chX; end; readln; end; end;广度优先搜索procedure bfs; begin readln(n); for k:=1 to n do begin readln(a1,1,a1,2,xm,ym); bxm,ym:=true; ok:=false; fillchar(c,sizeof(c),0); t:=0;头

8、z:=1;尾 while tz do begin if ok then break; inc(t); j:=cat,1,at,2+1; for i:=1 to 4 do begin x:=at,1+xfi;y:=at,2+yfi; if bx,y and (cx,y=0) then begin if (x=xm) and (y=ym) then begin writeln(j); ok:=true; break; end; cx,y:=j; inc(z);az,1:=x;az,2:=y; end; end; end; bxm,ym:=false; if not ok then writeln(

9、0); end; end;主程序begin assign(input,mj.in); reset(input); init; bfs; close(input);end.算法如下： 用队列的方法。用a记录搜索过程，a.city记录经过的城市,a.pre记录前趋元素，这样就可以倒推出最短线路。具体过程如下：（1） 将城市A入队，队首、队尾都为1。（2） 将队首所指的城市所有可直通的城市入队（如果这个城市在队中出现过就不入队，可用一个集合来判断），将入队城市的pre指向队首的位置。然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。利用pre可倒推出最少城

10、市线路。procedure out; 输出过程beginwrite(a.cityd);repeatd:= a.pred;write (-,a.cityd);until a.pred=0;writeln;halt;end;procedure doit;beginh:=0; d:=1;a.city1:=A;a.pre1:=0;s:=A; repeat 步骤2inc(h); 队首加一，出队引例4最少步数问题描述在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这

11、件事后觉得很有趣，就想试一试，在一个（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)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（

12、x1，y1）和白马所在（x2，y2）到达 (1,1) 目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点(1,1)作为起点，这样只需要一次广度优先搜索便可以得到（x1，y1）和（x2，y2）到达(1,1)的最少步数。const dx:array1.12 of longint=(-2,-1,-2,-1,2,1,2,1,-2,-2,2,2); dy:array1.12 of longint=(-1,-2,1,2,-1,-2,1,2,-2,2,-2,2);var a:array-5.30,-5.30 of longint; q:array2.1000,1.2 of

13、longint; a1,a2,b1,b2,i,j,h,t,x,y:longint;begin readln(a1,b1); readln(a2,b2); h:=0;t:=1; q1,1:=1; q1,2:=1;引例5：流星雨题目描述夜深了，小Q独自坐在校园里，仰望着天空，等待着流星雨的到来。我们假设二中校园是一个无穷大的矩阵，小Q所在地点为(0,0)。因为某种原因，一些流星会在某一时刻砸落到地面上，并毁坏它降落的地点及相邻的上下左右四个格，被毁坏的点就不能再通行了。虽然流星雨很美，但生命诚可贵，所以小Q希望移动到一个永远不会被流星砸到的点来欣赏流星雨。已知，每秒钟，小Q可以移动到相邻的一个没有

14、被毁坏的格子，请你求出，小Q移动到一个永远不会被毁坏的点，也就是安全的点，最短需要多少时间。输入格式第一行共一个整数M，表示共有M颗流星会砸落到地面上。接下来M行，每行三个整数Xi,Yi,Ti，表示在第Ti秒流星会毁坏 (Xi,Yi)及相邻的四个点。输出格式第一行，一个整数，表示小Q最短需要多少时间才能到达一个永远不会被流星毁坏的地点。如果无法到达，输出-1。样例输入40 0 22 1 21 1 20 3 5样例输出5数据规模及约定对于20%的数据,M=15.对于40%的数据,M=200.对于100%的数据,M=50000,0=Xi,Yi=300,0=Tit then ax+dxj,y+dyj

15、:=t; end; head:=0;tail:=1; while head=0)and(xi=0)and(yitime)then begin if axi,yi=maxlongint then begin writeln(time); close(input); close(output); halt; end; tail:=(tail+1) mod 10000; qtail,0:=time; qtail,1:=xi; qtail,2:=yi; axi,yi:=0; end; end; end; writeln(-1); close(input); close(output);end.宽搜的优

16、化之一：双向搜索使用广度优先搜索时，离根结点最近的结点先扩展，所以广度优先搜索法比较适合求步数最少的解，因为广度优先要保留所有搜索过的节点，随着搜索程度的加深，所需的存储空间成指数增加。因此在必要时我们采用双向搜索来减少搜索空间和存储空间，如下面的例子。例 字串变换（NOIP2002tg）问题描述:已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:A1$ - B1$A2$ - B2$ 规则的含义为：在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ 。例如：A$abcdB$xyz 变换规则为：abc-xuud-yy-yz则此时，A$ 可以经过一系列的变换

17、变为 B$，其变换的过程为：abcd-xud-xy-xyz 共进行了三次变换，使得 A$ 变换为B$。输入:输入文件名。文件格式如下：A$ B$A1$ B1$ A2$ B2$ |- 变换规则. . /所有字符串长度的上限为 20。输出:输格式如下：若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出NO ANSWER!输入输出样例b.in:abcd xyzabc xuud yy yzB.out：3算法分析：此题是求变换的最少步数，很显然可以使用广度优先搜索法，如果直接从初状态搜到目标状态，最坏情况下存储的结点数超过6的10次方幂，搜索空间过大，因此我们考

18、虑使双向搜索，同时从初始状态和目标状态向中间状态搜索，当相遇时搜索结束。采用双向搜索，存储的结点数还有可能超限，我们在前向搜索队列中存储5步内变换的结点，在后向搜索队列中，由于第5步产生的结点只是用来与前向队列中的结点比较，所以可以不存储在队列中，后向搜索队列只需存储4步内的结点，这样就解决了存储空间问题。为了使用方便，在程序设计中用一个数组a1.max存储两个队列，前向搜索队列为a1.mid，后向搜索队列为amid.max，用st存储搜索方向，st=0表示前向搜索，st=1表示后向搜索，用opst和clst分别表示队列尾指针和首指针，用be表示队列起始位置，循环产生每一个结点，若在10内无解

19、退出循环，若在10内找到解则输出解并退出程序。源程序：const mid=12000;max=16000;type node=record s:string;x:byte;end;var i,mark:integer; a:array 1.maxof node; x:array0.6,0.1of string20; d:string; op,cl:array 0.1 of integer;procedure Init;读取数据，初始化var t:string;begin assign(input,b.in);reset(input);i:=0; while not eof do begin r

20、eadln(t); xi,0:=copy(t,1,pos( ,t)-1); xi,1:=copy(t,pos( ,t)+1,length(t); inc(i); end;while mark:=i-1;close(input);end;判断是否到达目标状态procedure bool(be,st:integer);begin for i:=mid-be+1 to cl1-st do if aclst.s=ai.s then begin writeln(aclst.x+ai.x); halt; end;ifend;判断节点是否与前面的结点重复procedure check(be,st:integ

21、er);begin for i:=be+1 to clst-1 doif ai.s=aclst.s thenbegin dec(clst);exit; end; bool(be,st);end;扩展产生新节点procedure expand(be,st:integer);var i,j,k,lx,ld:integer;begin inc(opst);d:=aopst.s; k:=aopst.x;ld:=length(d); for i:=1 to mark do begin lx:=length(xi,st); for j:=1 to ld do begin if (copy(d,j,lx)=

22、xi,st) then begin if (st1)or(k4)then begin inc(clst); end;if aclst.s:= copy(d,1,j-1)+ xi,1-st+ copy(d,j+lx,ld); aclst.x:=k+1; check(be,st);检查是否重复 end;if end;for end;forend;procedure bfs;var be,k,st:integer;Begin for st:=0 to 1 do begin if st=0 then be:=0 else be:=mid; opst:=be+0;clst:=be+1; aclst.s:

23、=x0,st; aclst.x:=0; end;for repeat if (op0cl0)and(acl0.x=5)then expand(0,0); if (op1cl1)and(acl1.x=cl0)or(acl0.x5)or(op1=cl1)or (acl1.x5);End;BEGIN init;bfs;writeln(NO ANSWER!)END.宽搜的优化之二：分支定界法分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。 例1：设有A,B,C,D,E 5人从事j1,j2,j3,j4,j5 5项工作每人只能从事一项,它们的效益表如下:求最佳安排,使

24、效益最高？本题可用回溯或其它方法解，但当人数稍多是，运行超时？用分支定界法，搜索中减掉不必要的分支？program plan_job;const maxn=20;type arr=array1.maxn of integer;pnt=node;node=recordjob,flag:arr;up,dep:integer;nxt:pnt;end;var tp,p:pnt; n,min,row,depth:integer; goal:arr; a:array1.maxn,1.maxn of integer; f:text;function cost(p:pnt):integer;var i,j,m

25、ax,y:integer;begin y:=0; with p do begin for j:=1 to n do if jdep+1 then y:=y+ajobj,j else begin max:=0; for i:=1 to n do if (max=y.up); x.nxt:=p; p.nxt:=y;end;procedure goals(p:pnt);begin if p.upmin then begin goal:=p.job;min:=p.up end;end;procedure print;var i,k:word;begin for i:=1 to n do write(j

26、,i,:,chr(goali+64), ); writeln; writeln(maxcost=,min); readln; end;begin init; repeat if tp.upmin then begin depth:=tp.dep+1; for row:=1 to 5 do if tp.flagrow=0 then begin new(p); p:=tp; process(p); if p.upmin then dispose(p) else sort(p); if depth=n then goals(p); end; end; tp:=tp.nxt; until tp=nil

27、; print;end.拓展：A*算法A*算法中更一般的引入了一个估价函数f,其定义为f=g+h。其中g为到达当前节点的耗费，而h表示对从当前节点到达目标节点的耗费的估计。其必须满足两个条件：。h必须小于等于实际的从当前节点到达目标节点的最小耗费h*。f必须保持单调递增。A*算法的控制结构与广度搜索的十分类似，只是每次扩展的都是当前待扩展节点中f值最小的一个，如果扩展出来的节点与已扩展的节点重复，则删去这个节点。如果与待扩展节点重复，如果这个节点的估价函数值较小，则用其代替原待扩展节点，具体算法描述如下: 例：一个3*3的棋盘中有1-8八个数字和一个空格，现给出一个初始态和一个目标态，要求利用这个空格，用最少的步数，使其到达目标态。 问题分析：预期值定义为h=|x-dx|+|y-dy|。估价函数定义为f=g+h。Node(节点类型)RecordSitutation:TSituation（当前节点状态）;g:Integer;(到达当前状态的耗费)h:Integer;(预计的耗费)f:Real;(估价函数值)Last:Integer;(父节点)EndList(节点表):Array1.Max(最多节点数)ofNode(节点类