信息学奥赛：广度搜索课件.ppt

1、广度搜索在程序设计中的应用深度优先:SLMN F F O P F Q F 广搜优先:SLOMF PQN FFF“广搜广搜”用来解决那类问题用来解决那类问题?用深度优先搜索找最优解时必须搜索完所有路径，即使一个目标用深度优先搜索找最优解时必须搜索完所有路径，即使一个目标结点在很浅的树枝上，也得等到它左边所有结点均被搜索后才能结点在很浅的树枝上，也得等到它左边所有结点均被搜索后才能找到它。用这种方法求某些最优解时，效率比较低。而广度优先找到它。用这种方法求某些最优解时，效率比较低。而广度优先搜索，能较好地解决这个问题。搜索，能较好地解决这个问题。广度优先搜索是最简便和常用的图形搜索算法之一，从对图

2、形的广度优先搜索是最简便和常用的图形搜索算法之一，从对图形的遍历来看，遵循遍历来看，遵循“从浅入深从浅入深”的搜索策略。在这种搜索过程中，的搜索策略。在这种搜索过程中，树上的结点扩展是沿着深度的树上的结点扩展是沿着深度的“断层断层”进行的，所以这种方法一进行的，所以这种方法一定能保证找到最短（步数最少）的解答序列。在不少题中要求找定能保证找到最短（步数最少）的解答序列。在不少题中要求找到经历步骤最少而达到目标的方案时，多采用此种搜索方法。到经历步骤最少而达到目标的方案时，多采用此种搜索方法。“广搜广搜”所用的数据结构所用的数据结构-队列队列为了体现先生成先扩展的执行方式又能保留所有生成的结点以

3、待为了体现先生成先扩展的执行方式又能保留所有生成的结点以待进一步扩展，广度优先搜索在数据结构上引用了进一步扩展，广度优先搜索在数据结构上引用了“队列队列”结构。结构。队列是一种线性表，具有队列是一种线性表，具有先进先出先进先出的特点，对于它所有的插入和的特点，对于它所有的插入和删除操作分别仅在队列尾和队列首进行。定义两个删除操作分别仅在队列尾和队列首进行。定义两个“指针指针”变量变量head和和tail，分别用来指向队列的头和尾。初始结点先入队，头，分别用来指向队列的头和尾。初始结点先入队，头指针指向待扩展结点，每生成一个子结点，则尾指针指针指向待扩展结点，每生成一个子结点，则尾指针tail增

4、加增加1，当前结点的所有子结点均生成后，头指针向后移动（即加当前结点的所有子结点均生成后，头指针向后移动（即加1），），位于位于head指针之前的（已被删除）为已扩展结点，指针之前的（已被删除）为已扩展结点，tail指向所有指向所有已生成结点的最后一个。若已生成结点的最后一个。若head指针大于指针大于tail指针，表示所有解指针，表示所有解答树上的结点已产生。如果目标结点仍求出现，说明答树上的结点已产生。如果目标结点仍求出现，说明“无解无解”。原理解析原理解析headtailsLOMFPQNFFF01122334678广度优先搜索的算法描述广度优先搜索的算法描述Procedure BFS初始

5、化，初始状态存入初始化，初始状态存入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 endunt

6、il(head=tail);广度优先搜索的注意事项广度优先搜索的注意事项（1）每生成一个子结点，就要提供指向它们）每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时，通过逆向跟踪，父亲结点的指针。当解出现时，通过逆向跟踪，找到从根结点到目标结点的一条路径。找到从根结点到目标结点的一条路径。（2）生成的子结点要与前面的所有已产生结）生成的子结点要与前面的所有已产生结点比较，以免出现重复结点，浪费时间，还可点比较，以免出现重复结点，浪费时间，还可能陷入死循环。能陷入死循环。（3）广度优先搜索的效率还有赖于目标结点）广度优先搜索的效率还有赖于目标结点所有位置情况，如果目标结点处在比较深的层

7、所有位置情况，如果目标结点处在比较深的层上时，需搜索的结点数基本上以指数增长。上时，需搜索的结点数基本上以指数增长。例例1:电子老鼠闯迷宫电子老鼠闯迷宫电子老鼠闯迷宫。如下图电子老鼠闯迷宫。如下图1212方方格图，找出一条自入口（格图，找出一条自入口（2，9）到）到出口（出口（11，8）的最短路径。）的最短路径。12 /迷宫大小2 9 11 8/起点和终点1 1 1 1 1 1 1 1 1 1 1 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

8、 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 11 223344455566667788899101112131415152322222125252424161617 1802026262619192727272828输入:输出:28数据结构定义：A1.maxn,1.maxn表示邻接矩阵Father1.maxn*maxn表示队列Sta

9、te1.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;/入队 fathertail:=head;statetail,1:=statehead,1+dxk;state

10、tail,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=1)and(x=1)and(y=tail;end;例例3:翻币问题翻币问题有有N个硬币个硬币(6=N=w)and(n-statehead=5-w)/生成子节生成子节点条件点条件 then begin tail:=tail+1;f

11、athertail:=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公园游玩，但如果从他所在的饭店公园游玩，但如果从他所在的饭店没有

12、一路已士可以直接到达没有一路已士可以直接到达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的应用启发式涵数双向广度搜索