搜索
1Ch10算法设计技术(AlgorithmDesignTechniques)10.1穷举法（ExhaustiveAlgorithm）10.2递推法与迭代法（RecurrenceandIterativeAlgorithm）10.3递归（RecursiveAlgorithm）10.4逐步求精（StepwiseRefinement）10.5分治法（DivideandConquer）10.6贪心法（GreedyAlgorithm）10.7回溯法（BacktrackingAlgorithm）10.8动态规划法（DynamicProgramming）10.9分支界限法（BranchandBoundAlgorithm）10.10随机化算法（RandomizedAlgorithm）Summary210.1穷举法（ExhaustiveAlgorithm）穷举法(枚举法/试探法)基本思想是：分别列举出各种可能解，测试（试探）其是否满足条件（是否是欲求的解），若是，则输出之。特点是算法简单，但是运算量大。当问题的规模变大，执行的的速度变慢。310.1穷举法（ExhaustiveAlgorithm）[例]解不定方程。不定方程（组）是指独立方程个数少于变量个数而导致方程有多解。如，2x+3y=20是一个不定方程（设x,y为正整数）。解这个方程，就是求出所有的解。不定方程一般都有限定条件，我们这里考虑正整数解的情况。解这个方程，一个简单的做法是，让x和y分别遍取0到20内的正整数，并代入方程计算，若值为20，则表示找到一组解。具体的程序片断如下。for(i=0;i=20;i++)for(j=0;j=20;j++)if(2*i+3*j==20)cout\ni,j;410.2递推法与迭代法（RecurrenceandIterativeAlgorithm）递推法与迭代法是两种风格类似的方法，它们都是基于分步递增方式进行求解。5（1）递推法（RecurrenceAlgorithm）递推法是针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成。把这种由前面的子解得出后面的子解的规则称为递推关系。例如，对于Fibonacci数列：112358132134…设f(n)表示数列中第n项，则有：f(1)=1f(2)=1f(k)=f(k-1)+f(k-2)6递推法实现Fibonacci数列intFibonacci(intn){intf1,f2,f3;intk;f1=1;f2=1;if(n==1)return1;if(n==2)return1;for(k=3;k=n;k++){f3=f1+f2;f1=f2;f2=f3;}returnf3;}非递归7递推法运用的关键•寻找递推关系：递推关系有解析和非解析两种。（1）解析递推关系是指能用一般数学公式描述的关系，也称递推公式。（2）非解析递推关系是指不能用一般的数学公式描述的关系，这类关系的描述，也许本身就是一个递推过程。•递推关系必须有始基（最小子解）。如上例中，f1=1,f2=18（2）迭代法（IterativeAlgorithm）•迭代法和递推法类似，也是递增求解。不同：递推法每步得到的解都是相对于对应问题规模的完整解。迭代法中间步骤得到的解一般只是“近似解”，并不代表子问题的解（常常没有明确的子问题）。•当误差达到可接受的范围时，则认为“近似解”就是需要的结果。9例：求a的平方根(迭代法)floatSqrt(floata){floatprecision=0.0001;//定义解的精度floatx,x0;x=1;do{x0=x;x=1+(a-1)/(x+1);}while(x-x0precision||x0-xprecision);//当最近两个近似解的差的绝对值小于给定精度时结束returnx;}1010.3递归（RecursiveAlgorithm）（1）递归与递归程序的概念递归(Recursion)用来解决一类可归纳描述的问题，或说可分解为结构自相似的问题。所谓结构自相似，是指构成问题的部分与问题本身在结构上相似。这类问题具有的特点是：整个问题的解决，可以分为两大部分：一些特殊（基础）情况，有直接的解法，即始基；这部分与原问题“相似”，可用类似（与整个问题的解法类似）的方法解决（即递归），但比原问题的规模小。11递归问题在数学中很常见。例如，计算阶乘：F(0)=1F(n)=n!=n*F(n-1)当n0在该式中，f(n-1)的计算与原问题f(n)的计算“相似”，只是规模较小。例如，算术求和：S(0)=0S(n)=k=S(n-1)+nnk010.3递归（RecursiveAlgorithm）12阶乘的计算，可通过下列的递归程序：longFact(intn){if(n=0)return1;//第一部份，始基elsereturnn*Fact(n-1);//第二部份，用实参n-1递归调用}10.3递归（RecursiveAlgorithm）13（2）递归程序设计要点划分问题、寻找递归：许多问题，并没有明显的递归解法，这就需要寻找递归方案。首先要试着看能否把问题的处理分为两大类情况。一类情况是可以直接解决（不需要递归，为基本情况），另一类情况可按与原问题的解法（即现在正使用的解法）类似的解法进行（称为递归情况）。设计函数、确定参数：使用递归，必须设计为子程序（函数或过程）的形式。子程序的参数尤为重要，决定着递归的实现。递归子程序中的参数，除了应具有一般子程序所需要的参数外，还需要递归参数。设置边界、控制递归：递归中，第一类情况（非递归的情况）就起到循环条件的作用，这是因为，满足第一类情况时，就不递归调用了，本次调用即可结束。把第一类情况的判别条件称为递归控制条件。1410.4逐步求精（StepwiseRefinement）简单地讲，逐步求精方法，是一种逐步“划分”的方法，即将问题的解决，先用几个大/粗的模块的组合表示。对这些模块，先不考虑它们的内部实现，只规定其功能。然后再按类似方法继续划分这些模块，直到它们都变为程序设计语句。在这种划分中，应遵循下列规则：保证模块的粒度应逐步变小。粒度越大/粗，“说明性”越强，越远离程序设计语言，但越容易给出（设计）；保证当前正确。对每次划分，若假定各模块都可正确实现，则它们的当前组合（即划分方式）是整个问题的正确实现；对逐步求精的描述，一般采用“伪码”。所谓伪码，是指不完全的程序代码，它一般以程序设计语言(典型的是C/Pascal之类的结构化程序设计语言)的流程控制语句（如while,for,if等）为主体，夹杂自然语言的描述。15[例]求矩阵的鞍点考虑求矩阵鞍点的问题。所谓矩阵鞍点，是指满足这样条件的矩阵元素：它是所在行上的最小元素，同时是所在列上的最大元素。可以证明，一个矩阵可以有多个鞍点，但它们的值均相等。显然，求鞍点的一个直接的方法是，检查矩阵中每个元素是否为鞍点，用伪码描述为（设矩阵名为a，有n行m列，元素下标从0起）：for(i=0;in;i++)for(j=0;jm;j++){判断a[i][j]是否为鞍点；if(a[i][j]是鞍点)输出a[i][j];}16[例]求矩阵的鞍点(续1)这里，关键问题是判断a[i][j]是否为鞍点，所以关键是细化模块“判断a[i][j]是否为鞍点”。解决该问题，先检查a[i][j]是否为i行上的最小者，若是，则继续检查其是否为j列上最大者，若是，则为鞍点。其他情况都不是鞍点。该过程的伪码描述为：isSaddle=0;检查a[i][j]是否为i行上最小者；if(是){检查a[i][j]是否为j列上最大者；if(是)isSaddle=1;}17[例]求矩阵的鞍点（续2）这段程序结束后，isSaddle为非0时表示a[i][j]为鞍点，否则不是鞍点。在这里，有两个模块需要细化：a)检查a[i][j]是否为i行上最小者，这可以先找出i行上最小者的下标，然后与a[i][j]比较即可：kk=0;for(k=1;km;k++)if(a[i][k]a[i][kk])kk=k;if(a[i][kk]==a[i][j])a[i][j]为i行上最小者；18[例]求矩阵的鞍点（续3）b)检查a[i][j]是否为j列上最大者：kk=0;for(k=1;km;k++)if(a[k][j]a[kk][j])kk=k;if(a[kk][j]==a[i][j])a[i][j]为j列上最大者；1910.5分治法（DivideandConquer）分治是指“分而治之”（Divideandconquer），是把一个规模为n的问题分成两个或多个较小的与原问题类型相同的子问题，通过对子问题的求解，并把子问题的解合并起来从而构造出整个问题的解，即对问题分而治之。如果子问题的规模仍然相当大，还不足以很容易地求得它的解，这时可以对此子问题重复地应用分治策略。20•分治法的算法框架return_typed_and_c(objArray*p,inti,intj){inttemp;if(simple(p,i,j))returnsolve(p,i,j);/*基值处理*/temp=divide(p,i,j);/*分解问题*/return(combine(d_and_c(p,i,temp-1),d_and_c(p,j,temp)));/*递归调用与合并处理*/}10.5分治法（DivideandConquer）2110.5分治法（DivideandConquer）•二分法检索就是我们所学过的应用分治策略的典型的例子。•快速排序算法，归并排序算法、梵塔问题等都可以用分治策略求解。•快速排序算法每趟把一个元素放入排完序后它所应在的位置，这个位置把原表分成了两个宏观有序的子表；•归并排序算法是把规模为ｎ的问题分成规模为[n/2]的两个子问题；•而梵塔问题分原问题为两个规模为n-1的子问题。例子2210.5分治法（DivideandConquer）讨论•分治策略把问题分成若干个子问题，分成的子问题的数目一般不大。•如果每次分成的各子问题的规模相等或近乎相等的话，则分治策略的效率较高，否则效率就比较低。•例如：直接插入排序可以看作是把原问题分解成两个子问题，一个是规模为１的问题，另一个是规模为n-1的问题，算法的时间代价是O(n２)级的。•而归并排序把原问题分成了两个大小为n/2的问题，算法的时间代价是O(nlog2n)级的。2310.6贪心法（GreedyAlgorithm）•求着色问题近似解的贪心法(greedy)其基本思想为：先用一种颜色给尽可能多的结点上色，然后再用另一种颜色在未着色的结点中给尽可能多的结点上色，如此反复直到所有结点都被着色为止。2410.6贪心法（GreedyAlgorithm）•Dijkstra的最短路径算法求从源点到其它各结点的最短路径它总是从那些最短路径还不知道的结点中挑选一个到源点最近的结点。•另一采用贪心策略的算法是Kruskal的求最小生成树算法25背包问题给定n个物体和一个背包，已知物体i的重量为wi0，价值为pi，背包能容纳物体的重量为M。要求确定一组分数xi(xi[0,1])，能够把物体i的xi部分放入背包，使得最大，即将尽量多的价值装入背包。这是一个求最优解的问题。在仅仅限制装入背包的物品重量的前提下，为了使得装入背包的物品得到尽量大的价值，应该优先放入按单位重量价值最大的物品。可以用贪心法求解。贪心法是一个很直接的算法设计技术，可以很容易地用算法实现。10.6贪心法（GreedyAlgorithm）niiixp12610.6贪心法（GreedyAlgorithm）因为：p１/w１＝25/18＝1.38，p２/w２＝24/15＝1.6，p3/w3＝15/10＝1.5，p２/w２＞p３/w３＞p１/w１。所以首先把物品2全部放入背包，然后考虑物品3，最后如果还有余地考虑物品1。这样得到的结果为（x１，x2，x3）＝（0，1，1/2），