《信息学奥赛广度搜索课件.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛广度搜索课件.ppt（20页珍藏版）》请在三一办公上搜索。
1、广度搜索在程序设计中的应用,深度优先:SLMN F F O P F Q F,广搜优先:SLOMF PQN FFF,“广搜”用来解决那类问题?,用深度优先搜索找最优解时必须搜索完所有路径，即使一个目标结点在很浅的树枝上，也得等到它左边所有结点均被搜索后才能找到它。用这种方法求某些最优解时，效率比较低。而广度优先搜索，能较好地解决这个问题。广度优先搜索是最简便和常用的图形搜索算法之一，从对图形的遍历来看，遵循“从浅入深”的搜索策略。在这种搜索过程中，树上的结点扩展是沿着深度的“断层”进行的，所以这种方法一定能保证找到最短（步数最少）的解答序列。在不少题中要求找到经历步骤最少而达到目标的方案时，多采
2、用此种搜索方法。,最优化问题,“广搜”所用的数据结构-队列,为了体现先生成先扩展的执行方式又能保留所有生成的结点以待进一步扩展，广度优先搜索在数据结构上引用了“队列”结构。队列是一种线性表，具有先进先出的特点，对于它所有的插入和删除操作分别仅在队列尾和队列首进行。定义两个“指针”变量head和tail，分别用来指向队列的头和尾。初始结点先入队，头指针指向待扩展结点，每生成一个子结点，则尾指针tail增加1，当前结点的所有子结点均生成后，头指针向后移动（即加1），位于head指针之前的（已被删除）为已扩展结点，tail指向所有已生成结点的最后一个。若head指针大于tail指针，表示所有解答树上
3、的结点已产生。如果目标结点仍求出现，说明“无解”。,原理解析,s,L,O,M,F,P,Q,N,F,F,F,0,1,1,2,2,3,3,4,6,7,8,广度优先搜索的算法描述,Procedure BFS初始化，初始状态存入OPEN表；队列首指针head:=0；尾指针tail:=1；repeatfor I:=1 to max do/其中，max为产生子结点的规则数 begin if 子结点符合条件 then begin tail指针增1，把新结点存入队列尾；if 新结点与原已产生的结点重复 then 删去该结点（取消入队，tail减1）else if 新结点是目标结点 then 输出并退出；end
4、 enduntil(head=tail);,广度优先搜索的注意事项,（1）每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时，通过逆向跟踪，找到从根结点到目标结点的一条路径。（2）生成的子结点要与前面的所有已产生结点比较，以免出现重复结点，浪费时间，还可能陷入死循环。（3）广度优先搜索的效率还有赖于目标结点所有位置情况，如果目标结点处在比较深的层上时，需搜索的结点数基本上以指数增长。,例1:电子老鼠闯迷宫,电子老鼠闯迷宫。如下图1212方格图，找出一条自入口（2，9）到出口（11，8）的最短路径。,12/迷宫大小2 9 11 8/起点和终点1 1 1 1 1 1 1 1 1 1 1
5、1 1 0 0 0 0 0 0 1 0 1 1 11 0 1 0 1 1 0 0 0 0 0 11 0 1 0 1 1 0 1 1 1 0 11 0 1 0 0 0 0 0 1 0 0 11 0 1 0 1 1 1 1 1 1 1 11 0 0 0 1 0 1 0 0 0 0 11 0 1 1 1 0 0 0 1 1 1 11 0 0 0 0 0 1 0 0 0 0 11 1 1 0 1 1 1 1 0 1 0 11 1 1 1 1 1 1 0 0 1 1 11 1 1 1 1 1 1 1 1 1 1 1,1,10,11,12,13,14,23,21,17,18,0,20,输入:,输出:28,
6、数据结构定义：A1.maxn,1.maxn表示邻接矩阵Father1.maxn*maxn表示队列State1.maxn*maxn,1.2，1表示当前点的横坐标，2表示纵坐标，记录状态,procedure bfs;var tail,head,k,i:integer;begin head:=0;tail:=1;state1,1:=px;state1,2:=py;father1:=0;/初始点状态 repeat for k:=1 to wayn do if check(statehead,1+dxk,statehead,2+dyk)/扩展子节点 then begin tail:=tail+1;/入队
7、 fathertail:=head;,statetail,1:=statehead,1+dxk;statetail,2:=statehead,2+dyk;astatetail,1,statetail,2:=1;/判重标记 if(statetail,1=qx)and(statetail,2=qy)/是否为目标节点 then begin print(tail);tail:=0;end;end;until head=tail;end;,例2:骑士旅行,在一个n*m(m,n=50)格子的棋盘上,请你要测算出从初始位置(1,1)到格子(I,j)最少需要多少次移动。,5,procedure bfs;var
8、 head,tail,wayn,x,y,k:integer;begin father1:=0;head:=0;tail:=1;state1,1:=1;state1,2:=1;state1,3:=0;repeat for wayn:=1 to 8 do begin x:=statehead,1+dxwayn;y:=statehead,2+dywayn;,if(x=1)and(x=1)and(y=tail;end;,例3:翻币问题,有N个硬币(6=N=20000)全部正面朝上排成一排，每次将其中5个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。试编程找出步数最少的翻法，输出最少步数及翻法
9、。分析:本题的关键是找出从当前状态如何变化到下一状态（即变化的规律）。任意翻转5个硬币，正反面的个数变化为：5正0反 正-5 反+5 4正1反 正-3 反+3 3正2反 正-1 反+1 2正3反 正+1 反-1 1正4反 正+3 反-3 0 正5反 正+5 反-5,即有6种变化，用statei表示节点i正面的个数，完成翻转即正面的个数为0，在执行上面6种翻转时要检查是否符合翻条件，即正面的个数和反面的个数要大于其对应的翻转数，生成新节点时要判断此节点是否出现过，否则就会出现相同的5个硬币翻来翻去的情况。repeat for w:=0 to 5 do if(statehead=w)and(n-s
10、tatehead=5-w)/生成子节点条件 then begin tail:=tail+1;fathertail:=head;statetail:=statehead-w+5-w;,for k:=1 to tail-1 do/判重 if statek=statetail then begin tail:=tail-1;break;end;if statetail=0 then/判断是否为目标结点 begin step:=0;print(tail);tail:=0;end;end;until head=tail;,例4:最优乘车,一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路已士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士,这样换乘几次后到达S公园。现在用整数1,2,N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1S公园巴士站的编号为N。写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。输入:3 7/3条线路,7个车站 6 7 4 7 3 6 1 2 3 5 输出:2,广度搜索的优化,Hash的应用启发式涵数双向广度搜索,THK!,
