《浅谈广搜优化》课件.pptVIP

广度优先有哪些信誉好的足球投注网站优化 From：S.R. 复习广搜 1 2 6 5 4 9 8 7 3 复习广搜 于是我们的出了一个结论：广搜主要应用于在有向无环图中求两状态间最短距离的问题 另外，还有一个很重要的问题，在广搜中，经常会涉及到状态这个问题，那么，什么是状态呢？…… 广搜优化涉及的算法 1.哈希判重 2.双向广搜 3.分支定界 4.A*算法 这两个，以后再说…… 1.哈希判重 基本思路: 进行广搜时，将已出现过的状态存在哈希表中，以及通过在哈希表中查找，判断当前状态是否出现过。 适用范围： 由于哈希表的特性，哈希判重更适用于较为复杂的状态。 1.哈希判重 那么，我们再来看上文的例题。 我们可以设计一个哈希函数，并如此地记录状态：从棋盘左上到右下，16个格子依次对应integer的二进制的前16位，其中1为黑色，0为白色。 例如：0110 1101 0110 1000 这样的棋盘我们便可以简化为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 5 4 9 8 7 3 11 10 3.分支定界 然后，做道题吧： 3.分支定界 返回 4.A*算法 具体请参阅深度优先有哪些信誉好的足球投注网站优化…… 返回