搜索算法在经典问题中的运用

《搜索算法在经典问题中的运用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、搜索算法在经典问题中的运用搜索方式经典问题深度优先搜索（DeepFirstSearch）求割顶和割边求有向图中的强连通分量求欧拉回路Hanoi塔等递归求解问题广度优先搜索（BroadFirstSearch）求单源最短路径（迭代的思想）特别的，当任两点间的权值都相等时，广度优先搜索的时间复杂度为O（n+e），优于传统的Dijkstra算法。求网络流问题中的增广轨表中所列大部分都是图论中的基础问题，很多题目都以其为基本模型而出。可见，搜索算法早已成为选手必须掌握的基本功，而它广泛的灵活性和实用性则是以下我们所要探讨的关键。3.1.2常用的搜索算法一迭代加深搜索先限定搜索树的最

2、大深度MaxDeep再搜索。如果无解就加大MaxDeep继续搜。虽然这样进行了很多重复的工作，但是由于搜索的工作量与深度成指数关系，因此上一次（重复的）工作量比起当前的搜索量来是较小的。这种方法适用于搜索树较宽且深、但可行解较浅的题目。这样的题目用一般的深度优先搜索可能陷入很深又没有解的死胡同，而用广度优先搜索空间规模又难以承受。[例一]埃及分数（OIBH练习赛试题）在古埃及，人们使用单位分数的和(形如1/a的，a是自然数)表示一切有理数。如：2/3=1/2+1/6，但不允许2/3=1/3+1/3，因为加数中有相同的。对于一个分数a/b,表示方法有很多种，但是哪种最好呢？

3、首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：19/45=1/3+1/12+1/180，19/45=1/3+1/15+1/4519/45=1/3+1/18+1/30，19/45=1/4+1/6+1/180，19/45=1/5+1/6+1/18。最好的是最后一种，因为1/18比1/180，1/45，1/30，1/180都大。给出a，b(0

4、分母a/b=1/a1+1/a2+…+1/ann不妨设a1＜a2＜…＜an。2剪枝手段——定分母的上下界设限定的搜索层数为D，当前搜到第C层，当前正要枚举分母ak，还需枚举总和为x/y的分数。answer[D]表示当前最优解中的第D个分母，如果还没有得到解则表示正无穷。则必然有：Max(ëy/xû，ak-1)+1≤ak≤Min(ë(D-C+1)*y/xû，ëMaxlongint/xû，answer[D]-1)枚举的初值容易得出，但终值的确定则要用到我们一开始对分母有序性的假设了。值得注意的是，直接限界避免了搜索过程中屡次使用可行性剪枝，一定程度上提高了程序的运行速度。实际上

5、本题还有一种剪枝手段——借助动态规划预见后续搜索是否有意义。这一点将在下一节“搜索的基本优化手段”中的“最优性和可行性剪枝”一栏的例题“彩票问题”中得到详尽的分析。至此，本题已得到较好的解决。在编程过程中我们可以发现，迭代加深搜索具有以下特点：1空间耗费小这是它最大的优点。2时间效率不低虽然它确实做了一些重复的工作，但是正如前面所分析的那样，之前的搜索量与当前的搜索量比起来是“小巫见大巫”的。3便于剪枝4实现方便，易于调试也正是基于以上优点，迭代加深的思想才被广泛应用于各类模型当中。二记忆化搜索记忆化搜索可以说是动态规划的搜索实现方式。基于有些动态规划的规划方程不好用简单

6、的式子描述，记忆化搜索就以其简洁清晰省事的语言，代替了传统的规划模式。虽然说记忆化搜索的本质是动态规划——目标明确没有重复，但是与后者相比，它还是存在占用栈空间过多、时间效率较低的缺点。因此高级选手不到万不得已是很少使用记忆化搜索的。[例一]选课问题（经典问题）有N（N≤1000）门功课，第i门功课有Si个学分，每门功课可能有一门直接选修课（即必须选完它的直接选修课才能选这门功课），求选M门功课所得的最大学分。分析这是一道树形结构的动态规划试题，我们可以用循环实现，也可以用递归实现。后者称之为记忆化搜索，本题中相对于前者可读性更高。下面我们来介绍它的实现方式。1建模增设虚

7、课程γ为所有无直接选修课程的功课的直接选修课，其学分为0。本题的模型是一棵多叉树，为了降低规划方程的维数，先用儿子~兄弟法将其转化成二叉树。设F[i,j]表示在以节点i为根节点的子树中选j个节点所能得到的最大分数，其中节点i必选。lc为i的左儿子节点，rc为i的右儿子节点，mark[i]为第i门功课的学分。则：F[i,j]=Max(F[lc,k]+F[rc,j-k-1])+mark[i]2实现从根节点开始递归求解，直至找到叶子节点后回溯，自底向上依次求得F函数值。在求某节点的F函数值时，若它的儿子节点的F函数值已经求出，则直接