搜索
1深度优先搜索算法优化2回顾搜索算法•给出初始节点，要求寻找到符合约束条件的目标节点•给出初始节点和目标节点，要求找到从初始节点到目标节点的一条路径。•最优解？较优解？全部解？3例：“和最小”题目描述•设有一个长度为N的数字串，要求使用K个加号将它分成K+1个部分，找出一种分法，使得这K+1个部分的和能够为最小。•题目要求的就是在每个数字之间：或者填加号，或者什么都不填。根据这个要求，我们可以从头开始扫描整个数字串，逐个考察是否要填加号，然后检查下一个数字间的位置，直到最后一个数字。•下面是一个例子和它的状态树4•数字7629需要插入2个加号•这是一棵完整的搜索树。•结点内表示当前处理的状态，每向后处理一个空位即深入一层。•我们可以看到，在最后的所有叶子结点中，有三个黄色的结点是满足条件的。7+6+2+977+6767+6+27+6276+27627+62+97+62976+2+976+297629762+97+6+297和6之间不添加加号7和6之间添加一个加号5深搜优化•搜索方法的时间复杂度大多是指数级的，简单的不加优化的搜索，其时间效率往往低的不能忍受，更是难以应付信息学竞赛严格的运行时间限制。•本文所讨论的主要内容就是在建立算法的结构之后，对程序进行优化的一种基本方法——剪枝。6剪枝•剪枝的概念：若我们把搜索的过程看成是对一棵树的遍历，那么剪枝就是将树中的一些不能到达我们需要的解的枝条“剪”掉，即通过某种判断，避免一些不必要的遍历过程以减少搜索的时间。•剪枝的原则•剪枝的分类：可行性剪枝和最优性剪枝7剪枝的原则•正确性如果随便剪枝，把带有最优解的那一分支也剪掉了的话，剪枝也就失去了意义。所以，剪枝的前提是一定要保证不丢失正确的结果。•准确性在保证了正确性的基础上，使不包含最优解的枝条尽可能多的被剪去，以达到程序“最优化”的目的。8•高效性设计优化程序的根本目的，是要减少搜索的次数，使程序运行的时间减少。但为了使搜索次数尽可能的减少，我们又必须花工夫设计出一个准确性较高的优化算法，而当算法的准确性升高，其判断的次数必定增多，从而又导致耗时的增多，这便引出了矛盾。•因此，如何在优化与效率之间寻找一个平衡点，使得程序的时间复杂度尽可能降低，同样是非常重要的。倘若一个剪枝的判断效果非常好，但是它却需要耗费大量的时间来判断、比较，结果整个程序运行起来也跟没有优化过的没什么区别，这样就太得不偿失了。9可行性剪枝•在很多情况下，并不是搜索树中的所有枝条都能通向我们需要的结果，有很多方案到最后我们才发现是不行的，但是这些方案在一开始就已经决定的是不行的，所以尽早的判断出一个方案是否可行，对于问题的优化是很明显的。而所谓可行性剪枝，正是基于这样一种考虑。10再看搜索树对于图中蓝色结点。后面能够插入’+’的位置已经少于未用完’+’的数量，肯定不可能有解。对于这种结点，其子节点不可能有解，可以回溯。这个节点的加号不可能有解,可以进行可行性剪枝77+6767+6+27+6276+27627+62+97+62976+2+976+297629762+97+6+2+97+6+2911最优性剪枝•又称为上下界剪枝，是一种重要的搜索剪枝策略。•我们可以回想一下，平时在做一些要求最优解的问题时，搜索到个解，是不是把这个解保存起来，若下次搜索到的解比这个解更优，就又把更优解保存起来？即记录当前得到的最优值。•其实这个较优解在算法中被称为“下界”，与此类似还有“上界”。•如果当前结点已经无法产生比当前最优解更优的解时，即这一分支的所有子节点都低于下界，或者高于上界，我们就可以将它剪枝。12回到加号题•儿子结点的数一定比父亲大•即搜索树深度越深得到的解越大•满足最优性剪枝的条件•我们可以记录当前得到的解的最小值•如果当前得到的和值已经超过保存的最小解，即不必再继续深入搜索，回溯。13再看搜索树•我们可以看到蓝色结点的子节点不可能有最优解77+6767+6+27+6276+27627+62+97+62976+2+976+297629762+97+6+2+97+6+2914最优性剪枝结果•结点数大大减少。77+6767+6+27+627+6+2+97+6+2915总结•两种常用的剪枝方法：–最优性剪枝•适用范围：子结点的代价全部高于或低于父结点，一般用于求最优解的题中。•又之称为多米诺性质。–可行性剪枝•根据题意作出判断是否继续搜索还有可能得到解16总结•在搜索算法中，几乎都需要采用程序优化,以减少时间复杂度。而这里所说的两种剪枝方法，是最常见的优化方法之一。然而，尽管可以采用众多优化算法使得程序的效率有所提高，搜索算法本身的时间复杂度不能从本质上减少是不可改变的事实。•在信息学竞赛中，还有一个编程复杂度的问题。我们对一个搜索算法使用了很多优化技巧，虽然可能使程序的时间效率得到一定的提高，但却往往要消耗大量的编程时间，很容易造成“拣了芝麻，丢了西瓜”的结果。•不妨在使用搜索算法之前先仔细想想，有没有其他更好的算法。