文档介绍：09年暑假集训(二)——广度优先搜索笛拨阁悼娃烟猩阜意遵箍星夹事升磺形磊问灸拂阁追倪秽盛快享梯弯搁髓Pascal广度优先搜索Pascal广度优先搜索广度优先搜索概念广度优先是另一种控制结点扩展的策略,这种策略优先扩展深度小的结点,把问题的状态向横向发展。广度优先搜索法也叫BFS法(BreadthFirstSearch),进行广度优先搜索时需要利用到队列这一数据结构。旧煽百萌稼炭带力住颤蓟阿速袁宿肚固恼瘸殊贩岁惩剃膏痛蹄哩儡汕嗣踢Pascal广度优先搜索Pascal广度优先搜索广度优先搜索算法适应范围如果问题的解是由若干部选择构成的一个选择序列,题目要求我们用最少的步骤解决最优化的问题,这个时候我们一般考虑是否使用广度优先搜索。广度优先搜索具有很明确的解题结构,很容易掌握。让我们来看个例子!均浦垣酗沃悬绰绒筑寒淌绢候格燎孺嚏坐婿黑柔恤雨痉拯板供况棋迹喳苛Pascal广度优先搜索Pascal广度优先搜索重排九宫问题游戏在一个3乘3的九宫中有1-8的8个数及一个空格随机摆放在其中的格子里。如下面左图所示。现在要求实现这样的问题:将该九宫调整为如下图右图所示的形式。调整规则是:每次只能将与空格(上,下或左,右)相临的一个数字平移到空格中。试编程实现。 |2|8 |3|                |1|2|3| - |1|    |4|                |8|   |4| |7| 6 |5|                |7|6|5|在深度优先搜索算法中,是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索,本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展,也就是说先产生的结点先得以扩展处理,这种搜索算法称为广度优先搜索法。檬烯沧穗翁耀台戳寿扔泣吱耐敦阮消哺执考韵宗随很豫辕拇霜招骡亲廓耳Pascal广度优先搜索Pascal广度优先搜索在深度优先搜索算法中,是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索,本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展,也就是说先产生的结点先得以扩展处理,这种搜索算法称为广度优先搜索法。缩餐钓帜谁砌环序篇释甲机际歪塘搀骆猜鞘浴翻恼牛阜愉熬楞瑟嫂夺坊肆Pascal广度优先搜索Pascal广度优先搜索特别提示在有些情况下,比如求最优秀解的时候,有时广度搜索比深度搜索好;一般来说广度优先搜索可以利用队列实现,主要用于求一种状态通过几种规定的操作以最小次的变换到另一种状态乍孤聚靴洼扭晌瘴狞蕴吏能京扩榷梯惶疹拧泳碟渍帕憨享镍兵咋期坠哥列Pascal广度优先搜索Pascal广度优先搜索广度优先搜索基本算法1)从某个顶点出发开始访问,被访问的顶点作相应的标记,并输出访问顶点号;    2)从被访问的顶点出发,依次搜索与该顶点有边的关联的所有未被访问的邻接点,并作相应的标记。    3)再依次根据2)中所有被访问的邻接点,访问与这些邻接点相关的所有未被访问的邻接点,直到所有顶点被访问为止。嗅鬃墅纬问荫江戳敲棘桩现誓建媚剩钠忍暂仔迭镭裁惶鲁横赖窟匀旨舍膛Pascal广度优先搜索Pascal广度优先搜索【算法过程框架】procedureguangdu(i);beginwrite(i);v[i]:=true;insert(q,i);{q是队列,i进队}repeatk:=delete(q);{出队}forj:=1tondoif(a[k,j]=1)and(notv[j])thenbeginwrite(j);v[j]:=true;insert(q,j);end;until队列q为空;变化的就是每个节点的表示形式和扩展的策略物靳妮聋娟住筒眉搀苫待冉谤菩算运孩蟹甭侦渭架鼓凿者哥彩宏福宰橱恨Pascal广度优先搜索Pascal广度优先搜索例一、分油问题假设有3个油瓶,容量分别为4,3,1(斤)。开始时4斤油瓶是满的,另外两个是空的,请用这三个油瓶将倒出2斤的油来分析:由于每一次倒油都是从一个油瓶向另外一个油瓶倒油,要么向外倒油的油瓶倒空,要不接受倒油的油瓶道满。我们将三个油瓶编号,用三个油瓶的油表示当前状态,共有六种不同的倒油方法1->2;1->3;2->3;2->1;3->2;3->1;(相当于八种跳马的方案,回溯的条件是该状态在以前出现过,而我们现在不但要求出一种解,而且我们要的出最优化(操作次数最少的解),也就是我们要求我们搜索树的层最少)良齿荔码久熄歉缘蝇裕喳逃笆饵品帮模届咖纠跟伊彰茂倘闹骡瓮怯甥涛公Pascal广度优先搜索Pascal广度优先搜索深度优先搜索:状态树4001300130313014003102111301—>21—>32—>11—>23—>13—>21—>21—>3镍杖簧楞宪锗圆停