信息学奥赛宽搜及应用课件.ppt

《信息学奥赛宽搜及应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、宽搜及应用本讲要点宽搜及其算法思想宽搜的算法实现宽搜应用初步引言搜索算法是基于计算机高速运算的特点而使用的求解方法。它从问题的初始状态出发，根据约束条件，按照一定的策略，有序推进，不断深入，最终到达所有符合条件的目标状态（或无解），或者找出所有可行解中的最优解。按照推进的控制策略，搜索一般分为宽度优先搜索和深度优先搜索。白色表示未访问的节点，黑色表示已经访问的节点，灰色表示：DFS中为正在访问的节点，BFS中为已入队等待访问的节点。深度优先搜索（DFS）与宽度优先搜索（BFS)的比较DFSBFS一、宽度优先搜索的算法思想

2、宽度优先搜索（BreadthFirstSearch,BFS)，简称宽搜，又称为广度优先搜索。它是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一拓展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则拓展第二层结点。如此依次拓展，检查下去，直到发现目标结点为止。如果拓展完所有结点，都没有发现目标结点，则问题无解。对于同一层结点来说，它们对于问题的解的价值是相同的，所以第一个找到的目标结点一定是应用产生式规则

3、最少的，因此，宽搜适合求最少步骤或最短解序列这类最优解问题。一、宽度优先搜索的算法思想abcdehfg第0层第1层第2层第3层逐层遍历二、宽度优先搜索的算法分析BFS问题解决的关键状态表示：状态一般是指现场信息的描述，通常用T表示。一般用T0表示初始状态，Tn表示目标状态。状态转移：根据产生式规则和约束条件控制从当前状态转移到下一个状态。状态判重：大多数情况下，出现重复状态会造成死循环或空间的浪费。现在在哪儿？下一步去哪儿？去过的就别再去了！三、宽度优先搜索的算法实现为保证“先生成的结点先扩展”，宽搜需用到符合“先进先出

4、”特点的这种重要的数据结构。队列队列的概念队列：限定仅在一端进行插入，而在另一端进行删除操作的线性表。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。队列(Queues)是生活中“排队”的抽象。三、宽度优先搜索的算法实现队列(Queue)允许用户从表的一端(队尾)入队，从表的另一端(队头)出队。因此，队列也被称作先进先出线性表(FIFO-FirstInFirstOut)。三、宽度优先搜索的

5、算法实现队列实现：数组模拟、STL（queue）用数组模拟队列头指针front、尾指针rear入队与出队队空三、宽度优先搜索的算法实现constintMAXN=1010;//队列的容量上限intq[MAXN];//队列的元素类型intfront,rear;//头指针、尾指针rearfront队列定义（数组）三、宽度优先搜索的算法实现队列初始化，初始状态入队front=0;rear=1;q[1]=1;//q[rear]=1;rearfront11约定：从1号结点开始存放队列元素三、宽度优先搜索的算法实现取队首元素，准备扩展

6、front++;x=q[front];rearfront11三、宽度优先搜索的算法实现扩展队首结点，新状态入队rear++;q[rear]=x;rearfront123123三、宽度优先搜索的算法实现队首结点扩展完毕，出队front++;x=q[front];指针后移一位，指向待扩展节点。rearfront123123三、宽度优先搜索的算法实现判断队列是否为空队列不空：front=rear三、宽度优先搜索的算法实现队列基本操作constintMAXN=101;intq

7、[MAXN];intfront,rear;intmain(){front=0;rear=1;q[1]=1;rear++;q[rear]=2;rear++;q[rear]=3;while(front

8、{if(新状态合法)入队;if(当前状态是目标状态)处理(输出解或比较解的优劣);}}1.将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；用循环队列节约存储空间2.将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为１。在结构上采用这种技巧来存储的队列称为循环队列。STL