[计算机]浅谈广搜优化课件.ppt

上传人(卖家):晟晟文业 文档编号:5102866 上传时间:2023-02-11 格式:PPT 页数:16 大小:936.52KB
下载 相关 举报
[计算机]浅谈广搜优化课件.ppt_第1页
第1页 / 共16页
[计算机]浅谈广搜优化课件.ppt_第2页
第2页 / 共16页
[计算机]浅谈广搜优化课件.ppt_第3页
第3页 / 共16页
[计算机]浅谈广搜优化课件.ppt_第4页
第4页 / 共16页
[计算机]浅谈广搜优化课件.ppt_第5页
第5页 / 共16页
点击查看更多>>
资源描述

1、广度优先搜索优化 From:S.R.复习广搜1265 49873复习广搜于是我们的出了一个结论:广搜主要应用于在有向无环图中求两状态间最短距离的问题另外,还有一个很重要的问题,在广搜中,经常会涉及到状态这个问题,那么,什么是状态呢?广搜优化涉及的算法1.哈希判重2.双向广搜3.分支定界4.A*算法这两个,以后再说1.哈希判重基本思路:进行广搜时,将已出现过的状态存在哈希表中,以及通过在哈希表中查找,判断当前状态是否出现过。适用范围:由于哈希表的特性,哈希判重更适用于较为复杂的状态。1.哈希判重那么,我们再来看上文的例题。我们可以设计一个哈希函数,并如此地记录状态:从棋盘左上到右下,16个格子依

2、次对应integer的二进制的前16位,其中1为黑色,0为白色。例如:0110 1101 0110 1000这样的棋盘我们便可以简化为0110110101101000,转化成十进制就是28008.我们可以计算得到,这样的哈希函数一共只有216=65536种状态,且没有冲突,每次查找的时间复杂度为O(1)。相比之下,如果逐位对比进行判重的话,每次查找的时间复杂度是O(16*n)n为已出现的状态数。如此比较,哈希判重的优势应该很明显了吧事实上,这种思想应该叫做状态压缩,但状态压缩与哈希判重往往是共通的返回2.双向广搜概念:沿两个方向同时进行的BFS。正向搜索:从初始结点向目标结点方向搜索;逆向搜索

3、:从目标结点向初始结点方向搜索;当两个方向的搜索生成同一子结点时终止此搜索过程。2.双向广搜基本思路:1)双向广搜的两个起始点分别是初状态和末状态。2)搜索的结束条件有二成功:两个方向相遇,即出现相同状态。失败:任意一方向的队列的首尾指针相遇。时间复杂度:由于广搜自身的时间复杂度不稳定,在此不作具体计算,相比单向广搜会减少不止1/2.2.双向广搜一道例题:一个44的棋盘,每个格子放着一个棋子。棋子一面是白色,一面是黑色。一次操作可以将某一个格子以及上下左右共5个格子的棋子都翻过来,即白色变黑色,黑色变白色。现在给出一种棋盘状态,问最少需要几次操作可以将棋盘全部变为同种颜色。2.双向广搜分析:1

4、)双向搜索:使用两个队列a1,a2分别记录两个方向的展开,当两个队列中首次出现相同状态时,两队列的层数和减一即为最少操作数。但是同时问题也出现了,这么复杂的状态我么怎么去表示和管理呢?我们接着往下看,哈希判重。返回3.分支定界一种粗略的定义:分支定界是一种系统地搜索解空间的算法,常以广度优先或最大效益优先的方式搜索问题的解。3.分支定界在分支定界法中,每一个活结点只有一次成为扩展结点。活结点一旦成为扩展结点,就一次产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子节点被加入活节点中。此后,从活结点表中取消一个结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空为止。3.分支定界我们用图来更清晰地看一下:1265 4987311103.分支定界然后,做道题吧:3.分支定界返回4.A*算法具体请参阅深度优先搜索优化返回

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文([计算机]浅谈广搜优化课件.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|