浅谈广搜优化课件_第1页
浅谈广搜优化课件_第2页
浅谈广搜优化课件_第3页
浅谈广搜优化课件_第4页
浅谈广搜优化课件_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

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

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

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

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论