资源描述：
《广度(宽度)优先搜索lppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、广度（宽度）优先搜索深度搜索与广度搜索区分[深度搜索与广度搜索]深度搜索与广度搜索的区别：深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构。广度搜索是求解最优解的一种较好的方法，而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用回溯算法代替。一些基本概念节点：记录扩展的状态。弧/边：记录扩展的路径。搜索树：描述搜索扩展的整个过程。节点的耗散值令C(i,j)为从节点ni到nj的这段路径（或者弧）的耗散值,一条路径的耗散值就等于连接这
2、条路径各节点间所有弧的耗散值总和。可以用递归公式描述如下：C(ni,t)=C(ni,nj)+C(nj,t)4搜索树根节点叶子节点4,5,6,7,88123567广度优先搜索的过程广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节
3、点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即⒈从图中的某一顶点V0开始，先访问V0；⒉访问所有与V0相邻接的顶点V1，V2，......，Vt；⒊依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点；⒋循此以往，直至所有的顶点都被访问过为止。这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。广度搜索策略综合数据库（变量设置）与问题相关的所有数据元素构成的集合，用来表述问题状态或有关事实。产生式规则构建了综合数据库以后，还需要研究问题的移动规则，称为产生式规则。搜索策略搜索策略的实质
4、是确定如何选取规则的方式。有两种基本方式：一种是不考虑给定问题所具有的特定知识，系统根据事先确定好某种固定顺序，依次调用规则或随机调用规则，这实际上是盲目搜索的方法。另一种是考虑问题领域可应用的知识，动态地确定规则的排列次序，优先调用较合适的规则使用，这就是通常所说的启发式搜索策略。广度优先搜索算法描述：Programbfs；初始化，初始状态存入队列；队列首指针head:=0;尾指针tail:=1；repeat指针head后移一位，指向待扩展结点；fori:=1tomaxdobegin//max为产生子结点的规则数if子结点符合条件thenbegintail指针增1
5、，把新结点存入列尾；if新结点与原已产生结点重复then删去该结点（取消入队，tail减1）elseif新结点是目标结点then输出并退出；end;end;until(head>=tail);//队列为空广度优先搜索注意事项1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。当然不要求输出路径，就没必要记父亲。2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间，还有可能陷入死循环。3、如果目标结点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比
6、深度搜索要快些，在求最优解时往往采用广度优先搜索；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。八数码问题在3*3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1—8中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格中移动，如图1所示。这样通过移动将牌就可以不断改变的布局结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状态），问如何移动将牌，才能实现从初始状态到目标状态的转换。下面我们看看怎样用宽度优先搜索
7、来解决八数码问题。图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展第２６个结点，总共生成４６个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。八数码问题扩展搜索树综合数据库（变量设置）{Pxy}，其中1<=x,y<=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等用Pascal语言描述如下：typet8no=array[1..3,1..3]oflongint;{棋盘状态}tList=r
