《浅谈广搜优化》PPT课件.ppt

广度优先搜索优化 From S R 复习广搜 复习广搜 于是我们的出了一个结论 广搜主要应用于在有向无环图中求两状态间最短距离的问题 另外 还有一个很重要的问题 在广搜中 经常会涉及到状态这个问题 那么 什么是状态呢 广搜优化涉及的算法 1 哈希判重2 双向广搜3 分支定界4 A 算法 这两个 以后再说 1 哈希判重 基本思路 进行广搜时 将已出现过的状态存在哈希表中 以及通过在哈希表中查找 判断当前状态是否出现过 适用范围 由于哈希表的特性 哈希判重更适用于较为复杂的状态 1 哈希判重 那么 我们再来看上文的例题 我们可以设计一个哈希函数 并如此地记录状态 从棋盘左上到右下 16个格子依次对应integer的二进制的前16位 其中1为黑色 0为白色 例如 0110110101101000这样的棋盘我们便可以简化为0110110101101000 转化成十进制就是28008 我们可以计算得到 这样的哈希函数一共只有2 16 65536种状态 且没有冲突 每次查找的时间复杂度为O 1 相比之下 如果逐位对比进行判重的话 每次查找的时间复杂度是O 16 n n为已出现的状态数 如此比较 哈希判重的优势应该很明显了吧 事实上 这种思想应该叫做状态压缩 但状态压缩与哈希判重往往是共通的 返回 2 双向广搜 概念 沿两个方向同时进行的BFS 正向搜索 从初始结点向目标结点方向搜索 逆向搜索 从目标结点向初始结点方向搜索 当两个方向的搜索生成同一子结点时终止此搜索过程 2 双向广搜 基本思路 1 双向广搜的两个起始点分别是初状态和末状态 2 搜索的结束条件有二 成功 两个方向相遇 即出现相同状态 失败 任意一方向的队列的首尾指针相遇 时间复杂度 由于广搜自身的时间复杂度不稳定 在此不作具体计算 相比单向广搜会减少不止1 2 2 双向广搜 一道例题 一个4 4的棋盘 每个格子放着一个棋子 棋子一面是白色 一面是黑色 一次操作可以将某一个格子以及上下左右共5个格子的棋子都翻过来 即白色变黑色 黑色变白色 现在给出一种棋盘状态 问最少需要几次操作可以将棋盘全部变为同种颜色 2 双向广搜 分析 1 双向搜索 使用两个队列a 1 a 2 分别记录两个方向的展开 当两个队列中首次出现相同状态时 两队列的层数和减一即为最少操作数 但是同时问题也出现了 这么复杂的状态我么怎么去表示和管理呢 我们接着往下看 哈希判重 返回 3 分支定界 一种粗略的定义 分支定界是一种系统地搜索解空间的算法 常以广度优先或最大效益优先的方式搜索问题的解 3 分支定界 在分支定界法中 每一个活结点只有一次成为扩展结点 活结点一旦成为扩展结点 就一次产生其所有儿子结点 在这些儿子结点中 导致不可行解或导致非最优解的儿子结点被舍弃 其余儿子节点被加入活节点中 此后 从活结点表中取消一个结点成为当前扩展结点 并重复上述结点扩展过程 这个过程一直持续到找到所需的解或活结点表为空为止 3 分支定界 我们用图来更清晰地看一下 1 2 6