第18讲_广度优先搜索.ppt

《第18讲_广度优先搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、程序设计实习第十八讲广度优先搜索内容提要广度优先搜索的基本思想POJ1077八数码问题广搜双向广搜(扩展，不要求)A*(扩展，不要求)小结：影响搜索效率的因素2广度优先搜索广度优先搜索也称为宽度优先搜索，它是一种先生成的节点先扩展的策略。适合于判定是否有解和求唯一解的情况搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。假设有两个表：Open表存放待处理节点，Closed表存放处理完节点Open表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进

2、入Open表的节点排在后面。广度优先搜索两个状态的集合:未处理完的状态:已处理的状态从中选择被演化状态的原则：离初态S0距离最近的状态sS0到s的距离：从S0到达s使用的动作数量实现方法：用queue表示每次取queue头部的状态演化每次演化出的状态s若不属于，则s将压入queue的尾部深搜vs.广搜深搜1-2-4-8-5-6-3-7广搜1-2-3-4-5-6-7-8广搜算法广度优先搜索算法如下：（用QUEUE）(1)把初始节点S0放入Open表中；(2)如果Open表为空，则问题无解，失败退出；(3)把O

3、pen表的第一个节点取出放入Closed表，并记该节点为n；(4)考察节点n是否为目标节点。若是，则得到问题的解，成功退出；(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。例题：POJ1077八数码问题八数码问题是人工智能中的经典问题POJ1077八数码问题：经典搜索问题有一个3*3的棋盘，其中有0-8共9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态到达目标状态123456780的步数最少的解？12345

4、678823146577例题：POJ1077八数码问题状态空间8234165782341576823416578241357682341576823416578广度优先搜索广度优先搜索（bfs）优先扩展浅层节点，逐渐深入第一层第二层第三层8234165782341576823416578241357682341576823416579广度优先搜索广度优先搜索用队列保存待扩展的节点，从队首队取出节点，扩展出的新节点放入队尾，直到找到目标节点（问题的解）8234165782341576824135768234157682

5、34165710广度优先搜索广度优先搜索的代码框架BFS(){初始化队列while(队列不为空且未找到目标节点){取队首节点扩展，并将扩展出的节点放入队尾；必要时要记住每个节点的父节点；}}11关键问题：判重判重新扩展出的节点如果和以前扩展出的节点相同，则则个新节点就不必再考虑如何判重？重复?823416578234157682341650782413576823415768234165712关键问题：判重需要考虑的问题状态数目巨大，如何存储？怎样才能较快的找到重复节点？时间空间13判重合理编码，减小存储代价不同的编

6、码方式所需要的存储空间会有较大差别82341657方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。（228<99=387,420,489<229）判重需要一个标志位序列，每个状态对应于标志位序列中的1位，标志位为0表示该状态尚未扩展，为1则说明已经扩展过了标志位序列可以用字符数组存放。数组的每个元素存放8个状态的标志位。位序列最多需要99位，因此存放位序列的数组需要99/8+1个字节48,427,562字节如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/

7、8)14判重合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别82341657方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。此方案需要编写字符串形式的9进制数到其整型值的互相转换函数。15判重合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别82341657方案二：为节点编号把每个节点都看一个排列，以此排列在全部排列中的位置作为其编号排列总数：9!=362880只需要一个整数(4字节)即可存下一个节点判重用的标志数组只需要362,880字节即可。此方案比方案1省空间此方案

8、需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。16判重时间与空间的权衡对于状态数较小的问题，可以用最直接的方式编码以空间换时间对于状态数太大的问题，需要利用好的编码方法以时间换空间具体问题具体分析17输入数据：23415x768输出结果：ullddrurdllurdruldr2