搜索与剪枝--ACM

DFS和BFS搜索与剪枝----ACM国际大学生程序设计主讲：王树林推荐书籍算法艺术与信息学竞赛作者：刘汝佳黄亮清华大学出版社一引言搜索被称为通用解题法，在算法和人工智能中占有重要地位。搜索是ACM竞赛中的常见算法，本次讲座的主要内容就是分析它的特点,以及在实际问题中如何合理的选择搜索方法，提高效率。首先介绍各种基本的搜索及其各自的特点。在基本搜索方法的基础上学习一些更高级的搜索，提高搜索的效率。然后探讨运用搜索算法高效地解决实际问题的方法，体现搜索的广泛应用性。状态空间状态state状态转移statetransition智能体agent简单的多智能体系统状态空间:搜索的过程实际上是在遍历一个隐式图，遍历结果为解答树。二常用搜索算法（1）盲目搜索纯随机搜索广度优先搜索（BFS）深度优先搜索（DFS）走迷宫重复式搜索迭代加深搜索迭代加宽搜索柱型搜索（2）启发式搜索贪心搜索A*搜索深度搜索与广度搜索深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构.广度搜索是求解最优解的一种较好的方法，在后面将会对其进行进一步的优化。而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。双向广度搜索广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。分支定界分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。周界搜索。初始状态和目标状态都已经确定。由于在每个测试数据中，目标结点都是一样的，反向搜索一次就够了。先反向搜索一次，把结点都保存起来再正向搜索的方法叫周界搜索（perimetersearch）。一般来说，周界中的结点不再变更，只需对它进行检索，而不进行插入和删除，所以采用Hash表或Trie都可以。反向搜索的深度对于程序的效率影响比较大，一般深度为7时，效率较高。深度优先遍历的思想（DFS）在图中从任意一个顶点（设为v0）开始，进行遍历,接着找v0的第一邻接点，若该邻接点未被遍历，则遍历之，再找该邻接点的第一邻接点，若该第一邻接点已被遍历，则找其下一邻接点。若下一邻接点未被遍历，则遍历，再找它的第一邻接点，就这样递归向下进行。若遇到第一邻接点不存在，或下一邻接点也不存在时，则退回到调用的上一层。如此下去，若不能遍历完所有顶点（说明不是连通图），则再选一个未遍历的顶点，重新开始以上过程，直至所有顶点遍历完毕。深度优先遍历的算法intvisited[MAX+1]/*辅助数组，是算法中需用到的全局变量*/voiddfs(g,v)/*从图g的第v号顶点出发深度优先遍历*/AdGraphg[MAX+1]intv;{EdgeNode*p;printf(“6d”,g[v].vexdata)/*首先访问该顶点，假设其数据为整数*/visited[v]=1;p=g[v].link;while(p){if(visited[p-adjnum]!=l)dfs(g,p-adjnum);/*若该顶点末被访问过，则递归调用*/p=p-next;/*p指向下一个与第v个顶点链接的表结点*/}}voiddfstravel(g,n)/*深度优先遍历顶点个数为n的图g*/AdGraphg[MAX+l];intn;{intv;for(v=1;v=n;v++)visited[v]=0;/*初始化辅助数组，表示所有顶点均末被访问过*/for(v=1;v=n;v++)/*对图中所有未被访问过的顶点进行深度优先搜索*/if(visited[v]!=1)dfs(g,v)}一个搜索实例这就是古老而又经典的15数码难题：在4*4的棋盘上，摆有15个棋子，每个棋子分别标有1-15的某一个数字。棋盘中有一个空格，空格周围的棋子可以移到空格中。现给出初始状态和目标状态，要求找到一种移动步骤最少的方法。看到这个题目，会发觉几乎每个搜索算法都可以解这个问题。而事实确实如此。理解状态，算符，状态转移，状态空间，搜索策略宽度优先搜索①从结点v开始，给v标上已到达（或访问）标记——此时称结点v还没有被检测，而当算法访问了邻接于某结点的所有结点时，称该结点被检测了。②访问邻接于v且尚未被访问的所有结点——这些结点是新的未被检测的结点。将这些结点依次放置到一未检测结点表(队列Q)中（末端插入）。③标记v已被检测。④若未检测结点表为空，则算法终止；否则⑤从未检测结点表的表头取一结点作为下一个待检测结点，重复上述过程。宽度优先检索算法procedureBFS(v)//宽度优先检索G，它从结点v开始。所有已访问结点被标记为VISITED(i)=1。VISITED(v)←1;u←v//VISITED(n)是一个标示数组，初始值VISITED(i)=0,1≤i≤n//将Q初始化为空//Q是未检测结点的队列//loopfor邻接于u的所有结点wdoifVISITED(w)=0then//w未被检测//callADDQ(w,Q)//ADDQ将w加入到队列Q的末端//VISITED(w)←1//同时标示w已被访问//endifrepeatifQ为空thenreturnendifcallDELETEQ(u,Q)//DELETEQ取出队列Q的表头，并赋给变量u//repeatendBFSBFS、DFS、D_Search算法比较BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。D_Search：使用栈保存未被检测的结点，结点按照宽度优先的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。12345678无向图GBFS检测序列：12345678DFS检测序列：12485637D_Search检测序列：13785462ACM实战—三角形大战题目描述在如下图所示的棋盘上进行一场游戏。游戏有A、B两人参加。A先走，每人每次任选一条虚线填成实线。而如果某人填完一条线段与另两条实线组成了一个单位三角形，该三角形被标记为该游戏者所有，且该游戏得到一次奖励的机会，其中一步游戏如图所示。当18条线段被填充完毕后，拥有三角形多的玩家获胜。编程求出当两个人都采用最好的对策时最后取胜的玩家。这是一个典型的博弈搜索题目。分析局面估价函数给每个局面State规定一个估价函数值f，评价它对于己方的有利程度。胜利者的估价函数值为正无穷，而失败者的估价函数值为负无穷。假设没有和局。如何计算每一个局面的估价函数？Max局面Min局面终结局面如果双方都不能走，显然胜负已分。这就是最单纯的极大极小算法对于一个局面，递归计算它所有子局面的估价函数值。Functionminmax(State,Player:integer):integer;BeginifWeWonthenminmax:=正无穷；elseifWeLostthenminmax:=负无穷；elsebeginmin:=正无穷；max:=负无穷；forMove:=1toMoveCountdobeginNewState:=DoMove(state,move);Value:=minmax(NewState,Next(Player));ifValueminthenmin:=value;ifValuemaxthenmax:=value;end;IfPlayer=MyProgramthenminmax:=max;IfPlayer=Opponentthenminmax:=min;End;End;主观估价值所有的f值不是正无穷就是负无穷。如果双方都采用最优策略，任意局面都是必胜的或必败的。但是在实际比赛中，完整地计算出一个局面的f值计算量太大，通常规定计算的最大递归深度maxDepth，如果达到了该深度，f值就是按照某种主观方法得出的估价值。只需要在过程参数里加上一个depth，当depth比较大的时候直接把局面估价函数作为minmax的返回值。Alpha-Beta剪枝举一个例子对于一个max局面S，已经计算出了它的第一个子局面S1（min局面）的f值为5，而现在正在计算S的第二个子局面S2（min局面）的值。假设我们已经得知了S2的某个子局面的f值为2，那么S2的f值至多是2，比S1的f值要小。因此选择S1肯定比S2好，因马上停止计算S2。优化方法题目要求当两人都采用最好的策略时的获胜者，意味着搜索必须完全，但这样很慢。方法1：如果一方已经拿到了5个三角形，实际上他已经肯定胜利了。方法2：如果存在一些条填充以后可以获得三角形的线，就只考虑填充他们的情况。此法不可行。但可以大幅度地提高剪枝效果。如果以下一步能得到的三角形数作为权值，用前面提到的节点排序方法可以提高剪枝效果。搜索方法中的剪枝优化搜索的进程可以看作是从树根出发，遍历一棵倒置的树——搜索树的过程。而所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。剪枝的原则原则之一：正确性。剪枝方法之所以能够优化程序的执行效率，正如前所述，是因为它能够“剪去”搜索树中的一些“枝条”。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就都失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。为了满足这个原则，我们就应当利用“必要条件”来进行剪枝判断。也就是说，通过解所必须具备的特征、必须满足的条件等方面来考察待判断的枝条能否被剪枝。这样，就可以保证所剪掉的枝条一定不是正解所在的枝条。当然，由必要条件的定义，我们知道，没有被剪枝不意味着一定可以得到正解（否则，也就不必搜索了）。剪枝的原则--总结原则之二：准确性。在保证了正确性的基础上，对剪枝判断的第二个要求就是准确性，即能够尽可能多的剪去不能通向正解的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。因此，准确性可以说是剪枝优化的生命。当然，为了提高剪枝判断的准确性，我们就必须对题目的特点进行全面而细致的分析，力求发现题目的本质，从而设计出优秀的剪枝判断方案。剪枝的原则原则之三：高效性。一般说来，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的效率的提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性外，经常还需要提高判断操作本身的时间效率。然而这就带来了一个矛盾：我们为了加强优化的效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能减小、甚至完全抵消提高判断准确性所能带来的优化效果，这恐怕也是得不偿失。很多情况下，能否较好的解决这个矛盾，往往成为搜索算法优化的关键。方法当然，我们在应用剪枝优化的时候，仅有上述的原则是不够的，还需要具体研究一些设计剪枝判断方法的思路。我们可以把常用的剪枝判断大致分成以下两类：可行性剪枝。最优性剪枝（