资源描述
广度搜索在程序设计中的应用广度搜索在程序设计中的应用深度优先:SLMN F F O P F Q F 广搜优先:SLOMF PQN FFF 深度优先:SLMN F F O P“广搜广搜”用来解决那类问题用来解决那类问题?用深度优先搜索找最优解时必须搜索完所有路径，即使一个目标用深度优先搜索找最优解时必须搜索完所有路径，即使一个目标结点在很浅的树枝上，也得等到它左边所有结点均被搜索后才能结点在很浅的树枝上，也得等到它左边所有结点均被搜索后才能找到它。用这种方法求某些最优解时，效率比较低。而广度优先找到它。用这种方法求某些最优解时，效率比较低。而广度优先搜索，能较好地解决这个问题。搜索，能较好地解决这个问题。广度优先搜索是最简便和常用的图形搜索算法之一，从对图形的广度优先搜索是最简便和常用的图形搜索算法之一，从对图形的遍历来看，遵循遍历来看，遵循“从浅入深从浅入深”的搜索策略。在这种搜索过程中，的搜索策略。在这种搜索过程中，树上的结点扩展是沿着深度的树上的结点扩展是沿着深度的“断层断层”进行的，所以这种方法一进行的，所以这种方法一定能保证找到最短（步数最少）的解答序列。在不少题中要求找定能保证找到最短（步数最少）的解答序列。在不少题中要求找到经历步骤最少而达到目标的方案时，多采用此种搜索方法。到经历步骤最少而达到目标的方案时，多采用此种搜索方法。“广搜”用来解决那类问题?用深度优先搜索找最优解时必须搜索完“广搜广搜”所用的数据结构所用的数据结构-队列队列为了体现先生成先扩展的执行方式又能保留所有生成的结点以待为了体现先生成先扩展的执行方式又能保留所有生成的结点以待进一步扩展，广度优先搜索在数据结构上引用了进一步扩展，广度优先搜索在数据结构上引用了“队列队列”结构。结构。队列是一种线性表，具有队列是一种线性表，具有先进先出先进先出的特点，对于它所有的插入和的特点，对于它所有的插入和删除操作分别仅在队列尾和队列首进行。定义两个删除操作分别仅在队列尾和队列首进行。定义两个“指针指针”变量变量head和和tail，分别用来指向队列的头和尾。初始结点先入队，头，分别用来指向队列的头和尾。初始结点先入队，头指针指向待扩展结点，每生成一个子结点，则尾指针指针指向待扩展结点，每生成一个子结点，则尾指针tail增加增加1，当前结点的所有子结点均生成后，头指针向后移动（即加当前结点的所有子结点均生成后，头指针向后移动（即加1），），位于位于head指针之前的（已被删除）为已扩展结点，指针之前的（已被删除）为已扩展结点，tail指向所有指向所有已生成结点的最后一个。若已生成结点的最后一个。若head指针大于指针大于tail指针，表示所有解指针，表示所有解答树上的结点已产生。如果目标结点仍求出现，说明答树上的结点已产生。如果目标结点仍求出现，说明“无解无解”。“广搜”所用的数据结构-队列为了体现先生成先扩展的执行方式又原理解析原理解析headtailsLOMFPQNFFF01122334678原理解析headtailsLOMFPQNFFF0112233广度优先搜索的算法描述广度优先搜索的算法描述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 enduntil(head=tail);广度优先搜索的算法描述Procedure BFS广度优先搜索的注意事项广度优先搜索的注意事项（1）每生成一个子结点，就要提供指向它们）每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时，通过逆向跟踪，父亲结点的指针。当解出现时，通过逆向跟踪，找到从根结点到目标结点的一条路径。找到从根结点到目标结点的一条路径。（2）生成的子结点要与前面的所有已产生结）生成的子结点要与前面的所有已产生结点比较，以免出现重复结点，浪费时间，还可点比较，以免出现重复结点，浪费时间，还可能陷入死循环。能陷入死循环。（3）广度优先搜索的效率还有赖于目标结点）广度优先搜索的效率还有赖于目标结点所有位置情况，如果目标结点处在比较深的层所有位置情况，如果目标结点处在比较深的层上时，需搜索的结点数基本上以指数增长。上时，需搜索的结点数基本上以指数增长。广度优先搜索的注意事项（1）每生成一个子结点，就要提供指向它例例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 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例1:电子老鼠闯迷宫电子老鼠闯迷宫。如下图1212方格图，数据结构定义：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;/入队 fathertail:=head;procedure bfs;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;statetail,1例例2:骑士旅行骑士旅行在一个n*m(m,n=50)格子的棋盘上,请你要测算出从初始位置(1,1)到格子(I,j)最少需要多少次移动。1122222223333333445例2:骑士旅行在一个n*m(m,n=1)and(x=1)and(y=tail;end;if(x=1)and(x=例例3:翻币问题翻币问题有有N个硬币个硬币(6=N=20000)全部正面朝上排成一排，每次将全部正面朝上排成一排，每次将其中其中5个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。试编程找出步数最少的翻法，输出最少步数及翻法。上为止。试编程找出步数最少的翻法，输出最少步数及翻法。分析分析:本题的关键是找出从当前状态如何变化到下一状态（即变化本题的关键是找出从当前状态如何变化到下一状态（即变化的规律）。的规律）。任意翻转任意翻转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例3:翻币问题有N个硬币(6=N=w)and(n-statehead=5-w)/生成子节生成子节点条件点条件 then begin tail:=tail+1;fathertail:=head;statetail:=statehead-w+5-w;即有6种变化，用statei表示节点i正面的个数，完成翻 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;for k:=1 to tail-1 do /判重例例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例4:最优乘车 一名旅客最近到H城旅游，他广度搜索的优化广度搜索的优化Hash的应用启发式涵数双向广度搜索广度搜索的优化Hash的应用THK!
展开阅读全文