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*算法具体请参阅深度优先搜索优化返回