《队列与广搜.ppt》由会员分享，可在线阅读，更多相关《队列与广搜.ppt（53页珍藏版）》请在三一文库上搜索。
1、队列与广度优先搜索,队,规定：,只能从队首出队 只能从队尾入队 每个人只能进出队一次,一 、队列的概念,队列是一种的线性表，删除在表头（队头），插入在表尾（队尾）进行。 先进先出（First In First Out） 假设入队的顺序是：a1,a2,an， 则出队列的顺序也是： a1,a2,an。,队尾：tail （指向队尾，最后一个元素） 队首：head (习惯指向队首的前一位置，空的位置),队列数组q下标： 3 4 5 6 7 ,初始：head=tail=0 非空： head=tail ;,定义： Const max=队列的大小； Var queue:array1.max of datat
2、ype; head,tail: longint;,队列的两种操作： 入队：procedure add(x); 出队：function del,datatype=record data:各种需要保存状态 depth:longint; / 深度 End;,1）、过程ADD(x)在队列q的尾端插入元素x procedure ADD( x：qtyper)； begin inc(tail); qtail：=x； end；ADD,2）、函数DEL取出q队列的队首元素 function DEL； begin inc(head); del:=qhead； end；DEL,二、广度优先搜索,BFS (Bread
3、th First Serach),也称为宽度优先搜索 按层遍历的一种搜索方法,深度优先搜索(Depth-First Search),dfs状态空间图,状态搜索树：先扩展最左边的结点，再扩展右边的结点,广度优先搜索(Breadth -First Search),bfs状态空间图,状态搜索树：先扩展深度小的结点，从上而下扩展结点,图的遍历(输出结点)：深度优先遍历（dfs）,原则：能向前走就走，不能走就后退一步再选择可行点,a:array1.maxn,1.maxn of integer;/邻接矩阵 visited:array1.maxn of boolean; /访问标志 procedure df
4、s(i:integer); /深度优先遍历结点 var j:integer; begin write(i, ); visitedi:=true; for j:=1 to n do if (ai,j=1)and(not visitedj) then dfs(j); end; begin init; dfs(1); end.,广度优先遍历（bfs）,1,搜索过程如下： 从起点开始由近及远按层次遍历。,/q:array1.maxn of longint;/队列保存结点 head:=0; tail:=1; /队列初始化 q1:=1; visited1:=true; /1进队列，避免重复 while h
5、eadtail do /队列不空 begin inc(head); /出队列 k:=qhead; write(k, ); for j:=1 to n do /找没有遍历过的邻接点 if (ak,j=1)and(visitedj=false) then begin inc(tail); /进队列 qtail:=j; visitedj:=true; end; end;,【问题描述：】 在n*n的棋盘上有一匹马在第x行第y列的格子上。棋盘上有些格子上有障碍物，马不能达到有障碍物的格子。已知马在棋盘中的走法按“日“字8个方向可走，如下图所示：,问：哪些格子能到达，到达这些格子的最小步数是多少。 【输入
6、：】 第一行:n（n=100）,x,y(马的开始位置)。 接下来n行为棋盘的描述：“-“为空格子，”+“表示该格子有障碍物。 【输出：】 n行，每行n个用空格隔开的数，表示马到达该格子的最少步数，如果无法到达则用-1表示。,1、跳马,4 2 2 - - -+- -,【样例输入：】,4 3 2 1 3 0 3 2 2 3 -1 1 1 2 1 4,【样例输出：】,dx:array1.8 of integer=(-1,-2,-2,-1,1,2,2,1); dy:array1.8 of integer=(2,1,-1,-2,-2,-1,1,2); var can:array-1.maxn+2,-1.
7、maxn+2 of boolean; dist:array1.maxn,1.maxn of integer; /记录最少步数 q:array1.maxn*maxn,1.2 of integer; head,tail:longint； procedure init; var s:string; begin readln(n,x0,y0); fillchar(can,sizeof(can),false); for i:=1 to n do begin readln(s); for j:=1 to n do cani,j:=sj=-; end; end;,procedure bfs;/广度优先搜索
8、begin for i:=1 to n do for j:=1 to n do disti,j:=-1; head:=0; tail:=1; / 队列初始化 distx0,y0:=0; q1,1:=x0; q1,2:= y0; / 起点进队列 while headtail do begin inc(head); /出队列 x:=qhead,1; y:=qhead,2; /记录出队结点状态 for k:=1 to 8 do /扩张结点：走下一步 begin xx:=x+dxk; yy:=y+dyk; if canxx,yy and (distxx,yy=-1) then /能走但没走过 begi
9、n distxx,yy:=distx,y+1; inc(tail); qtail,1:=xx; qtail,2:=yy; end; end; end; end;,设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角。迷 宫格子中分别放有0和1，0表示可通，1表示不能，迷宫走的规则如下图 所示：即从某点开始，有八个方向可走，前进方格中数字为0时表示可通 过，为1时表示不可通过，要另找路径。 输入例子：（从文件中读取数据） 8 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1
10、1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 入口：（1，1）；出口：（1，8） 输出要求：找出一条 从入口（左上角）到出口（又上角）的最短路径。 8 (1 1)(2 2)(3 3)(3 4)(4 5)(3 6)(3 7)(2 8)(1 8),2、迷宫问题,Bfs算法：,1）先求最少步数,const fin=migong.in; fout=migong.out; maxn=100; dx:array1.8of integer=(0,1,1,1,0,-1,-1,-1); dy:array1.8of integer=(-1,-1,0,1,1,1,0,-1)
11、; type node=record row,col:integer; /记录行与列 depth:integer; /离起点的距离 end; var can:array0.maxn+1,0.maxn+1 of boolean; q:array1.maxn*maxn of node; n,head,tail:integer;,head:=0; tail:=1; q1.row:=1; q1.col:=1; q1.depth:=0; can1,1:=false; while headtail do begin inc(head); x:=qhead.row; y:=qhead.col; step:=
12、qhead.depth; for k:=1 to 8 do begin xx:=x+dxk; yy:=y+dyk; if canxx,yy then /没走过，没入过队 begin if (xx=1)and(yy=n) then print(step+1); inc(tail); qtail.row:=xx; qtail.col:=yy; qtail.depth:=step+1; canxx,yy:=false; end; end; end; print(-1);/无解的情况,procedure print(ans:integer); var j:integer; begin assign(o
13、utput,fout); rewrite(output); if ans=-1 then writeln(no answer) else writeln(ans); close(output); halt; end;,1和2是怎样保证不重复进队列的？,重复进队列，做了无用功，浪费空间和时间。 设置合适的布尔数组,给定10个盒子排成一行，其中有两个相邻的盒子是空的，其余的盒子中有4个A和4个B。 移动规则：任意两相邻字母可移到空盒子中去，但这两个字母的原来顺序保持不变。 目标：全部的A在左边，全部的B在右边，空格在中间。 对于任意给定的一个排列顺序，最少经过多少次移动，能达到目标序列。 输入：
14、一行：初始序列，空格用0代替。 输出： 初始序列达到目标的最少移动次数。 样例： 输入： 输出： 5,3、中国盒子问题 （box）,初始：,目标：,ABAB00ABAB A00BBAABAB AAABB00BAB AAA00BBBAB AAAABBBB00 AAAA00BBBB,1,2,3,4,5,1)、问题：初始序列达到目标的最少移动次数。 适合使用bfs算法。,2)、队列需要保存的状态： 转化后的字符串s; 转换需要的步数depth。 适合用记录数据类型： type node=record str:string; depth:integer; end;,3)、状态的多少（队列的大小）：,9
15、!/(4!*4!)=630,4)、状态的转移：看两个空格的能移动的位置 任意两相邻字母可移到空盒子中去，但这两个字母的原来顺序保持改变,1）、确定空格的位置： sp:=pos(0,s);,sp,S=,i （1-9）,2）、i，i+1与sp，sp+1位置的字符交换： 条件：( i+1 sp ) or ( sp+1i ) /前后情况,3）、交换： Tem=s temsp:=si; temsp+1:=si+1; temi:=0; temi+1:=0;,？,5)、判重：是否已进过队列 从队中的所有状态查找：1.tail,function find(tem:string):boolean; var j:
16、integer; begin for j:=1 to tail do if tem=qj.str then exit(true); exit(false); end;,head:=0; tail:=1; q1.str:=s1; q1.depth:=0; while headtail do begin inc(head); s:=qhead.str; step:=qhead.depth; sp:=pos(0,s); for i:=1 to 9 do begin tem:=s; if (i+1sp)or(sp+1i) then begin temsp:=si; temsp+1:=si+1; tem
17、i:=0; temi+1:=0; if tem=st then print(step+1); if not find(tem) then begin inc(tail); qtail.str:=tem; qtail.depth:=step+1; end; end; end; end;,广度优先 搜索算法（bfs）: 1、适合的题目类型： 1）、求从给定初始状态到目标状态最少需要的步数。 2）、给定初始状态，经过k步后能够到达哪些状态。 2、利用的数据结构：队列。 3、状态的最大值：决定队列的大小（非常重要） 4、队列里需要记住哪些状态：一般使用记录数据类型。 5、状态的转移：不能遗漏。 6、状
18、态的判重：避免重复进入队列。 7、无解的判断,head=0：队列的首指针；tail=1：队列的尾指针； Quene1:初始结点; While headtail do /还有未扩展的结点，队列不空 Begin Inc（head）； /移动队列的首指针：出队列 记录head状态； For i=1 to method do /按规则扩展下一层新的子结点 if 条件满足 then Begin 生成新的结点; if 新结点队列中没出现过 then 保存新结点（入队列）； if 新结点是目标结点 then print(tail) 搜索结束； End End； Print(-1); /无解,BFS的基本框架
19、：,type queue=record 必要的有用的状态; father:longint;/父亲结点，输出路径 depth:longint; end;,q:array1.maxn of queue; 队列的大小 作为全局变量，避免用作局部变量，尤其当maxn很多时。,/输出转化过程：路线 procedure dfs(i:longint);/从当前点递归输出 begin if qi.father0 then dfs(qi.father); write(qi.v, ); end; procedure print(k:longint); begin writeln(qk.depth); dfs(k)
20、; halt; end;,常用的判重方法：,合适的布尔类型 (迷宫类) 朴素的队列查找 find(1.tail)：如果多，时间长 构造合适的哈希函数：为了分类，减少查找时间,影响bfs时间的关键：重点 减少不必要的扩展结点,【问题描述】 对于只含有字母A和B的字符串，给定初始串s1和目标串s2。 同时给定串中字母的移动规则：每次移动只能交换两个相邻的字母。 任务：求s1最少经过多少次交换得到s2。 【输入】 第一行：初始串s1。 第二行：目标串s2。 【输出】 由s1生成s2的最少交换次数。 【数据范围限制】 100%的数据：s1和s2长度=20。 【输入输出样例】,4、A B交换,保存的状态
21、 状态数量：队列的大小 状态的扩展条件 判重方法,分析：,判重的改进： 构造哈希函数：把AB串对应于二进制,A:0 B:1 AB串和二进制一一对应关系。 AABBAA00110012。 f12=true 大小：20位：220,function hash(s:string):longint; var k,i:longint; begin k:=0; for i:=n downto 1 do k:=k*2+ord(si)-65; hash:=k; end;,构造函数：hash(s),fhash(s)=true,head:=0; tail:=1; q1.str:=s1; q1.depth:=0; f
22、hash(s1):=true; while headsi+1 then begin ss:=s; ssi:=si+1; ssi+1:=si; if not fhash(ss) then begin inc(tail); qtail.str:=ss; qtail.depth:=step+1; fhash(ss):=true; if ss=s2 then print(tail); end; end; end;,有两个无刻度标志的水杯，分别可装x升和y升的水。设另一个水缸，可以用来向水杯灌水或从水杯向水缸里倒水，两个水杯之间也可以相互倒水。已知x升的水杯开始是盛满水的，y升的杯子是空的，问如何通过倒
23、水和灌水操作，用最少的步数能在y升的杯子里量出z升水。,5：倒水问题,C,A,水缸（足够的水,未满）,X=20 Y=15 Z=10,Y=10,？,B,输入： 一行：x，y，z（=100）,整数。中间一个空格隔开。 说明：x:A的容量（开始满）；y：B的容量（开始空）；z：最终B中需要量出的水 输出： 第一行：最少步数s。 以下共s行，每行两个用空格隔开的整数，第一个表示操作一次后，x杯中的水的数量，第二个整数表示y杯中的水的数量。 样例输入： 20 15 10 输出： 5 5 15 0 15 15 0 15 15 20 10,问题分析：,每次操作都是下列6种中的一种操作： AB； AC； BA
24、； BC； CA； CB； 每一次操作，要么使一个容器满；要么使一个容器空。否则这次操作无意义。,1:AB,条件： A中有水且B不满： (a0)and(by-b）。 可以从A中倒mina,y-b升水给B。 状态： A：a-mina,y-b; B：b+mina,y-b。,2: AC,条件： A中有水：a0 结果： 把A中水全倒入C 状态： A: 0; B:b不变。,3: BA,条件：B中有水且A不满，即 (b0)and(ax-a）。 可以从B中倒minb,a-x升水给A。 状态：A：a+minb,x-a; B：b-minb,x-a。,4: BC,条件： B中有水：b0 结果: 把B中水全倒入C
25、状态： A: a ;B:0升。,5: CA,条件： A不满: ax。 结果: 把A倒满 状态： A: x满，B：b不变。,6: CB,条件： B不满：by。 结果: 把B倒满 状态： A：a不变，B：y满。,算法实现：,每倒一次需要保存的状态：a,b,father,depth 倒完一次后检查：a和b的值：出现 ? b=z ? 队列的大小：max=100；（max+1）*（max+1） 怎样判断重复： fi,j:boolean。A中出现i升，B中出现j升水的情况；,Const max=100; type node=record a,b:integer; father:integer; depth
26、:integer; /a:A中水；b：B中的水； end; var x,y,z:integer; q:array1.(max+1)*(max+1) of node; f:array0.max,0.max of boolean; /fi，j：A中i升水，B中j升水的情况是否出现过 head,tail:longint;,bfs,fillchar(f,sizeof(f),false); head:=0; tail:=1; fx,0:=true; q1.a:=x; q1.b:=0; q1.father:=0; q1.depth:=0; while head0) and (bB check(a-min(
27、a,y-b),b+min(a,y-b),step); if (a0) then check(0,b,step); / A-C if (b0) and (aA check(a+min(x-a,b),b-min(x-a,b),step); if (b0) then check(a,0,step); / B-C if (aA if (bB end; print(-1);,procedure check(i,j,d:integer);入队列 begin if not fi,j then begin inc(tail); qtail.a:=i; qtail.b:=j; qtail.father:=hea
28、d; qtail.depth:=d; fi,j:=true; if j=z then print(tail); end; end;,输出：,procedure print(k:integer); procedure dfs(i:integer); begin if qi.father1 then dfs(qi.father); writeln(qi.a, ,qi.b);/初始状态不输出 end; begin assign(output,fout);rewrite(output); if k=-1 then writeln(no answer) else begin writeln(qk.depth);dfs(k);end; close(output); halt; end;,