浅谈深度优先搜索算法优化.ppt

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