五大经典算法

所需积分/C币:44 2018-04-22 19:27:31 1.17MB PDF
280
收藏 收藏
举报

主要讲解分治法、动态规划、贪心法、回溯法以及分支限界法等几种种经典的算法, 让同学们能够更进步了解算法的魅力所在。 在本章对每一种算法都是从算法的概念思想、计算框架以及算法应用案例实现逐一介绍, 让读者能够综合运用前面几章所学知识,进一步加深对算法的理解。
9if(low=mid) return low;//只有一枚硬币,可以判别; 10 return check Coin(data,low,mid);/继续分解 案例2:利用分治算法进行归)排序 分治法求解排序问题的思想很简单,只需以某种方式将序列分成两个或多个了序列,分 别进行排序,再将己排序的子序列合并成一个有序序列即可。归并排序是典型的运用了分治 策咯的排序算法。 分析:归并排序的分解很简单,难点在于合并( merge)函数。下面使用分治法求解 分治法两跻合并算法可描述为三步:第一步,将待排序的元素序列一分为二,得到两个长度 基本相同的了序列;第二步,对两个了序列分别排序,若了序列较长则继续绀分重复以上 分为二的步骤,直至子序列的长度不大于1为止,此为关键步骤,需要将数列二分到每个子 数列的长度不超过1为止,因为只有不大于1的数列可直接求解;第三步将排好序的了序列 合并成一个有序数列,第八章中的 mergeNce实现函数即为以上的 merge函数。 在这里以数组5,2,4,7,1,3,2,6为例给出出归并过程,如图10.1。 456 merse 457 36 merge merge merge merge /merge 5 2 4 7 2 图10.1归并排序演示图 具体的代码可见本书第八章归并自底向上的代码。 102动态规划算法 1021算法基本概念 动态规划过程是:每次决策依赖于当前状态,又随即触发新的状态,进而引起状态的转 移。一个决策序列就是在变化的状态中不断产生出来的,所以,这种多阶段最优化决策解决 问题的过程就称为动态规划。 基本思想与分治法炎似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求 解子阶段,前一子问题的解,为后一子问题的求解提供了冇用的信息。在求解任一子问题时, 列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依 次解决各子问题,最后一个子问题就是初始问题的解。 由于动态规划解决的问题多数有重叠了问题这个特点,为减少重复计算,对每个了问 趟只解一次,一般情况会将其不同阶段的不同状态休存在一个缓冲区中。 与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往 不是互相独立的(即卜一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步 的求解)。 动态规划求解能进行求解的问题一般要满足如下三个性质: 1)最优化原理:如果问题的最优解所包含的」问趑的解也是最优的,就称该问题只 有最优子结构,即满足最优化原理。 2)无后效性:即某阶段状态·旦桷定,就不受这个状态以后决策的影响,即为某状 态以后的过程不会景响以前的状态,只与当前状态有关。 3)有重叠了问题:即了问题之间是不独立的,个子问题在下“阶段决策中可能被多 次使用到。 (注意:该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划 算法同其他算法相比就不具备优势) 10.22算法解题思路及框架 动态规划所处理的问题是一个多阶段决策问題,一般由初始状态开始,通过对中间阶段 决策的选择,达到结東状态。这些决策形成了一个决策序列,同时确定了完成整个过程的 条活动路线(通常是求最优的活动路线)。如图10.2所示。动态规划的设计都有着·定的模 式,一般要绎历以下几个步骤。 初始状态→|决策1|→|决策2|→…→|决策n|→结束状态 图10.2动态规划决策过程示意图 1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注 意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。 2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态 表示出来。当然,状态的选择要满足无后效性 3)桷定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是 棖据上一阶段的状态和决策来导岀本阶段的状态。所以如果确定了决策,状态转移方程也就 可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和 状态转移方程。 4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界 条件。一般,只要解决问题的阶段、状态和状态转移决簧确定了,就可以写出状态转移方程 (包括边界条件) 1023算法应用案例 在问题提出之前,本节先介纲几个基本概念: (1)子序列的定义:子序就是在给定序列中去掉零个或者多个元素的序列。 例如:给定一个序列X={x1 n},另外一个序列Z={z k},如 果存在X的一个严格递增小标序列<in,ig……,i>,使得对所有j1,2,……k,有x;=zj, 则Z是X的」序列 假定:Z={B,C,D,B}是Ⅹ={A,B,C,B,D,A,B}的一个子序列,相应的小标为<2,3,5,7>从定 义可以看出子序列直接的元素不一定是相邻的 (2)公共子序列:给定两个序列X和Y,如果Z既是X的一个子序列又是Y的一个 子序列,则称序列Z是X和Y的公共子序列 例如:X-{A,B,C,B,D,A,B},Y-{B,D,C,A,B,A,则序列{B,C,A}是X和Y的一个公共子 序刎,但不是最长公共子序列。因为它的长度等3,而子序列{B,C,A,B其长度等4,序列 {B,C,B,A}也是是X和Y的公共子序列。 案例:最长公共子序列Lcs( Longest Common Subsequence),问题描述:给定两个 序列Ⅹ-{x1,x2,…,xm和Y-{y1,y2,……yn},求出X和Y的最人长度公共子序列。 案例分析 如何找出一个最长公共子序列?如果序列比较短,可以采用蛮力法枚举出Ⅹ的所有子 序列(假定它的长度为M,则有2个子序列),然后检查是否是Y的子序列(假定其长度为 N,则有2个子序列),并记录所发现的最长子序列。如果序列比较长,这种方法需要指数级 0(2)的时间,是难以满足需求的 能否采用动态规划算法求解问题,需要知道求解问题是否具有最优子结构解,对于该 案例,看看下面的分析: X三<X1,…,X>即Ⅹ序列的前i个字符(1≤≤m)(前缀) Y=<y1,…,y>即Y序列的前j个字符(1sjsn)(前缀 假定=<z1,…,z>∈LCS(X,Y)。 (1)若xm=yn(最后一个字符相同),则可用反证法证明:该字符必是X与Y的任 最长公共子序列Z(设长度为k)的最后一个字符,即有=xm=y2且有Z:∈ICS(Xm Ya),即Z的前缀厶1是Xn1与Yn1的最长公共了序列。此时,问题转换成求解Ⅺ1与Yn 的LCS(Xn1,Yn-);而LCS(X,Y的长度,它等于LCS(X,Y1-)的长度加1 (2)若xm≠yn,则亦不难用反证法证明:要么Z∈LCS(Xm,Y),要么ZLCS(X Y)。山于水≠xm与水≠y其中至少有一个必成立,若zk≠xm则有Z∈LCS(Xm Y),类似的,若k≠yn则有Z∈1CS(X,Y-)。此时,问题就转换成求Xm1与Y的ICS及 Ⅹ与Y1的LCS。LCS(Ⅹ,Y的长度为:max{LCS(Xn1,Y)的长度,LCs(X,Yn1)的长度:。 由于上述当xm≠n的情况中,求LCS(X,Y)的长度与LCS(X,Y-)的长度,这 两个问题是不相互独立的,两者都需要求LCS(Xm,Y-)的长度。另外两个序列的LCS中包 含了两个序列的前缀的LCS,故此问趣具有最优子结构性质,可以考虑用动态规划法。 下面从三个步骤进行求解 (1)LCS的最优子结构定义:设X={x1,x2,……,xn和Y={y1,y2,……,y为两 个序列,并设Z={z1、2、……,z为X和Y的任意一个LCS,则必须满足如下条件: ①1如果x=y1,那么2=xmy,而且Z1是X1和Yn1的一个LCS。 ②如果xm≠yn,那么z≠xm蕴含Z是Ⅹm和Y的一个LCS。 ③如果xn≠yn,那么zk≠yn蕴含Z是‰和Yn1的一个LCS。 根据上面ICS的子结构的定义可知,要找序列X和Y的LCS,可以根据xn与yn是否相 等进行判断的,如果xn=y则产生个了问题,否则产生两个了问题。 用 engthOD记录序列X和Y的最长公共子序列的长度。其中X三<x1,X2,……,x>,Y=<y1 y2,…,y>。当i=0或户0时,空序列是X和Y的最长公共子序列,故1 ength[i[j-0。 其他情况下,由定理可建立递归关系如卜 设1 ength[i[j为序列X和Y的一个LCS的长度。如果i=0或者j=0,即一个序列的 长度为0,则LCS的长度为0εLCS问题的最优了结构的递归式如下所示 if i=0 or=0 length[illil Length[i-1 -1]+1 ifi,j>0 and xi-yi 式(9.1) max( length[[-1 length[i-1U小)tf;j>0 and xi≠y (2)计算LCS(X,Y)的长度 本算法将计算序列的长度保存到一个二维数组1 ength [w+1][N+1]中,另外引入一个维 度与 length相同的二维数组 token[W+1][N门用来保存最优解的构造过程,便于后续打印公 共了序列。M和N分别表示两个序列的长度。该函数的代码如下所示 void lengthLCS( char X[, char Y[l, int length[[, int token[[)i Int I, J intm= strlen(X);//求得X的长度 intn= strlen(Y);//求得Y的长度 /卜面两循坯是初始化 length数组 for (i=0; i-m: i++) length[i]_0]=0 for(i=0; i=n; i++) length[O][i]=0 i=1;i<=m;i++) for( j=1; j<=n; j++)I f(X[i-1]=Y[j-1]){ length[i]j= length _i-1][j-1]+1;//表示第一种求解 token[i][j]=1;//表示第一种情况 Else if( length i-1ljl >= lengthl illj-1l)I length[i]j= length[i-1]j;表示第种求解 token[i][j]=2;//表示第二种情况 Else lengthIly[j= length[i][j-1];/表示第种求解 token[i][j]-3;/′表小第三种情况 由上述代码可以看出 lengthS运行时间为0《MN),要比蛮力法好得多。为∫让同学史 好的理解上述程序,举一个具体例子:设所给的两个序列为K-<A,B,C,B,D,A,B>和Y-<B, D,C,A,B,A>。由函数1 engthLCS可计算出 length和 token两个数组的值,见图10.3; length和 token两个数组维度是一样的,把两个数组显小到一幅图上, token数组三个数 字用标识符来标识。 j0123456 y B DCABA 000 人表示1 2 B ↑表示2 ←表示3 4B 5 D 233 6A 34 7 B 22344 图10.3案例求解结果 第i行和第j列中的方块包含了 length[i[j的值以及指向 token[i[j的箭头。在 lengh7[6]的项4,表示的右下角为X和Y的一个LCS<B,C,B,A的长度。对于i,j0, lengths][j仅依赖于是否有x=y,及 length[i1[j和 length[i[j1的值,这几个项 都在 length[i[j之前计算。 (3)输出X,Y的最长公共子序列 从计算结果来看, 当 tokenlil[j=1时(意味着x=y:是LCS的一个元素),表示X与Y的最长公共子序 列是由X1与Y的最长公共子序列在尾部加上x1得到的子序列; 当 tokens[j-2时,表示X:与Y的最长公共子序列和X与Y3的最长公共子序列相 当 token[i[j-3时,时,表示X1与Y的最长公共子序列和X与Y的最长公共子 序列相同。 据此分析,木节给出输出LCS的代码如下: 根据第二步中保存的结果,从 token[M[N开始,当遇到1时,表示ⅹy是LCS中的 个元素。通过递归即可求出LCS的序列元素。书中给出了伪代码如下所示 void prntlcs (int token[[, char X[, int m, int n)[ n==0)return if( token m[nl=-1)i printLCS(token, X, m-1, n-1) printf(“-〉%c”,X[m1]) else if token [m][n]== 2) printLCS(token, X, m-1 else printLCS (token, X, m, n-1) 为了重构一个LCS的元素,从右下角开始跟踪 token[ij的箭头即可,这条路径 标示为阴影,这条路径上的每一个“”对应于一个使x=y为一个LCS的成员的项(高亮 标示)。所以根据上述图所示的结果,该函数将最终输出:“BCBA,或“BDAB 103贪心算法 1031基本概念 贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达 到。这是贪心算法可行的第一个基本婓素,也是贪心算法与动态规划算法的主要区别。 贪心选择是采用从顶向下、以迭代的方法做出相继选择,每做一次贪心选择就将所求问 题简化为个规模更小的了问题。对于一个具体问题,要确定它是否具有贪心选择的性质, 我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的 个整体最优解,是从贪心选择开始的,而且作了贪心选择后,原问题简化为一个规模更小的 类似子问题。然后,用数学归纳法证明,通过每一步贪心选择,最终可得到问题的一个整体 最优解。 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。运用 贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或 动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响,而动态规划 则不是。贪心算法对每个子问题的解决方案都做出选择,不能回退;动态规划则会根据以前 的选择结果对当前进行选择,有回退功能。动态规划主要运用于二维或三维问题,而贪心一 般是一维问题。所以对所采用的贪心策略一定要仃细分析其是否满足无后效性。 10.32算法解题思路及框架 贪婪算法可解决的问题通常大部分都有如卜的特性: 1)随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对 象,另一个包含已经被考虑过但被丢弃的候选对象 2)有一个凶数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的 解决方法是否最优 3)还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加 更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 4)最后,目标函数给出解的值。 为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法 步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函 数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行, 那么该对象就被丢弃并不再考虑;否则就加到集合里。每一次都扩充集合,并检查该集合是 否构成解。如果贪婪算法正确工作,那么找到的第一个解通常是最优的。 贪心算法解题框架如图10.4下 从问题的某一初始解出发 while(能朝给定总目标前进一步 利用可行的决策,求出可行解的一个解元素 由所有解元素组合成问题的一个可行解 图10.4贪心算法解题框架 1033算法应用案例 案例1:0-1背包问题:有个背包,背包谷量是M=150kg。有7个物品,物品不可以 分割成仟意人小见表10.1。要求尽可能让装入背包中的物品总价值最人,但不能超过总容 表10.1物品及价值和重量 物品 A B E F G 重量(kg) 35 30 5040 价值(元) 10 40 50 0 30 案例分析: 设定目标函数:∑p最大 约束条件是装入的物品总重量不超过背包容量:∑W<=M(M=150)。 下面要根据一些縈略来进行求解: 策咯1:每次挑选价值最大的物品装入背包,得到的结果是否最优? 策略2:每次挑选所占重量最小的物品装入是否能得到最优解? 策略3:每次选取单位重量价值最大的物品,成为解本题的策略? 贪心算法还是很常见的算法之,这是由于它简单易行,构造贪心策咯不是很困难。 稍微复杂的是,它需要证明后才能真正运用到题目的算法中。值得注意的是,贪心算法 并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。 般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问 题的最优解得来的。对于本例题中的3和贪心策略,都是无法成立(无法被证明)的,解释 如下: 策略1:选取价值最人者 反例:W=30 物品 重量:281212 价值:302020 根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。 策略2:选取重量最小。它的反例与第一种策略的反例差不多。 策略3:选取单位重量价值最大的物品。 反例 W=30 物品:ABC 重量:282010 价值:282010 棖据策略3,三种物品单位重量价值一样,程序无法依扼现有策咯作岀判断,如果选 择A,则答案错误。 对于选取单位重量价值最大的物品这个策略,可以再加一条优化的规则:对于单位重量 价值·样的,则优先选择重量小的!这样,上面的反例就解决了。 但是,如果题目是如下所示,这个策略就也不行了。 W=40 物品:ABC 重量:252015 价值:252015 总体而言本题是个D问题,用贪心法并不·定可以求得最优解,需要了解后续新算法 才有可能得到新的解法。 案例2:本节对本书第·章中提到的十字路冂着色问题,利用贪心算法来给予解决。 该问题可以归为图的m-着色判定问题,即为纶定无向连通图G和m种不同的颜色。用这 些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2 个顶点的颜色是不同的? 分析:本题题采用贪心法根据 Welch powe l1法的思路,按如下规则进行着色 步骤1:将G的结点按照度数递减的次序排列; 步骤2:用第一种颜色对第一个结点着色,并按照结点排列的次序,对与前面着色点 不邻接的每一点着以相同颜色 步骤3:用第二种颜色对尚未着色的点重复步骤②用第三种颜色 绊续这种作法,直到所有点着色完为止 算法代码如下: 对图的存储采用链接矩阵的方式(简化方面一些),假设有在二维数组 graph[NN;N为 顶点个数,默认顶点序列为{0,1,2,3,……,N1} 存储每个点的颜色及度信息采用如下结构休 type struct int index;//在数组的脚标 int color;//着色,初始化为0 int degree;//度数,初始化为0 I Vertex Create Graph( int graph[],intN)函数创建一个无向连通图,数据以链接矩阵进行 存储,参数为传递一个二维数组;本函数的代码可以参加本书第七章; countDegree该函数求出无向连通图所有顶点的度;

...展开详情
试读 22P 五大经典算法
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
五大经典算法 44积分/C币 立即下载
1/22
五大经典算法第1页
五大经典算法第2页
五大经典算法第3页
五大经典算法第4页
五大经典算法第5页

试读结束, 可继续读2页

44积分/C币 立即下载 >