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

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