考研复习资料大总结.ppt

1、分治法大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2) 效率太低 分治法:,X = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd,a,b,c,d,复杂度分析 T(n)=O(n2) 没有改进,分治法大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2) 效率太低 分治法:,XY = ac 2n + (ad+bc) 2n/2 + bd 为了降低时间复杂度，必须减少乘法的次数。 XY = ac 2n + (a-b)(d-c)+ac+bd

2、) 2n/2 + bd XY = ac 2n + (a+b)(d+c)-ac-bd) 2n/2 + bd,复杂度分析 T(n)=O(nlog3) =O(n1.59)较大的改进,细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。,分治法循环赛日程表,设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次； (3)循环赛一共进行n-1天。,按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分

3、割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,分治法线性时间选择,给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素,template Type RandomizedSelect(Type a,int p,int r,int k) if (p=r) return ap; int i=RandomizedPartition(a,p,r), j=i-p+1; if (k=j) return RandomizedSelect(a,p,i,k); else return RandomizedSelect(a,i+1,r,k-j

4、); ,在最坏情况下，算法randomizedSelect需要O(n2)计算时间 但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。,分治法线性时间选择,如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。,例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。,将n个输入元素划分成n/5

5、个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。 递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。,分治法线性时间选择,设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n75时，3(n-5)/10n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。,Type S

6、elect(Type a, int p, int r, int k) if (r-p75) 用某个简单排序算法对数组ap:r排序; return ap+k-1; ; for ( int i = 0; i=(r-p-4)/5; i+ ) 将ap+5*i至ap+5*i+4的第3小元素 与ap+i交换位置; /找中位数的中位数，r-p-4即上面所说的n-5 Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10); int i=Partition(a,p,r, x), j=i-p+1; if (k=j) return Select(a,p,i,k); else r

7、eturn Select(a,i+1,r,k-j); ,复杂度分析 T(n)=O(n),上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=n，01。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。,动态规划0-1背包问题,给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。,动态规划 0-1背包问题,设所给0-1背包问题的子问题,的最优值为m

8、(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。,考虑下列实例： n=3, 物品重量 (w1, w2, w3)=(2, 3, 4), 物品价值(p1, p2, p3)=(1, 2, 5), 背包容量C=6 解：,m(1, 6)=max m(2, 6), m(2, 6-2)+1 ,m(2, 6)=max m(3, 6), m(3, 6-3)+2 ,m(2, 4)=max m(3, 4), m(3, 4-3)+2 ,m(3, 6)=5 m(3, 3)=0,=5,=5,=6,解向量为

9、(x1, x2, x3)=(1, 0, 1),m(3, 4)=5 m(3, 1)=0,动态规划最长公共子序列,若给定序列X=x1, x2, , xm，则另一序列Z=z1, z2, , zk，是X的子序列是指存在一个严格递增下标序列i1, i2, , ik使得对于所有 j=1, 2, , k 有：zj = xij。 例如，序列Z=B, C, D, B是序列X=A, B, C, B, D, A, B的子序列，相应的递增下标序列为2, 3, 5, 7。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X=x1, x2, , xm和Y=y1,

10、 y2, , yn，找出X和Y的最长公共子序列。,动态规划最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则 (1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。 (2)若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列。 (3)若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。

11、用 cij 记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当 i=0 或 j=0时，空序列是 Xi 和 Yj 的最长公共子序列。故此时cij=0。其它情况下，由最优子结构性质可建立递归关系如下：,计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i =cij-1) cij=ci-1j; bij=2; else cij

12、=cij-1; bij=3; ,构造最长公共子序列 void LCS(int i，int j，char *x，int *b) if (i = =0 | j= =0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); ,贪心法活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用

13、公共资源。,贪心法活动安排问题,设有 n 个活动的集合 E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi ,且 si fi 。如果选择了活动 i，则它在半开时间区间si, fi)内占用资源。若区间 si, fi)与区间 sj, fj)不相交，则称活动 i 与活动 j 是相容的。也就是说，当sifj 或 sjfi 时，活动 i 与活动 j 相容。,在下面所给出的解活动安排问题的贪心算法 : int greedySelector(int s, int f, boolea

14、n a) int n=s.length; a1=true; int j=1; int count=1; for (int i=2; i=fj) ai=true; j=i; count+; else ai=false; return count; ,各活动的起始时间和结束时间存储于数组 s和 f 中且按结束时间的非减序排列,贪心法活动安排问题,由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便

15、安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,贪心法活动安排问题,例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：,贪心法活动安排问题,4.1 活动安排问题,算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。,贪心法多机调度问题,多机调度问题要求给出一

16、种作业调度方案，使所给的 n个作业在尽可能短的时间内由 m 台机器加工处理完成。 设有 n 个独立的作业1,2,n，由 m 台相同的机器进行加工处理。作业 i 所需的处理时间为 ti。 这个问题是 NP 完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。,约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。,贪心法多机调度问题,采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。 按此策略，当 时，只要将机器 i 的0, ti时间区间分配给作业 i 即可。 当 时，首先将

17、n 个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。,贪心法多机调度问题,例如，设 7 个独立作业 1,2,3,4,5,6,7 由 3 台机器 M1，M2 和 M3 加工处理。各作业所需的处理时间分别为2, 14, 4, 16, 6, 5, 3。按算法Greedy产生的作业调度如下图所示，所需的加工时间为 17。,贪心法最优装载,有一批集装箱要装上一艘载重量为 c 的轮船。其中集装箱 i 的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 1.算法描述,最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最

18、优装载问题的最优解。,最优装载问题可形式化描述为：,xi=0 表示不装入集装箱 i，xi=1 表示装入集装箱 i。,贪心法最优装载,贪心法最优装载,float loading(float c, float w, int x) int n=w.length; Element d = new Element n; for (int i = 0; i n; i+) di = new Element(wi, i); MergeSort (d); /按重量从小到大排序 float opt=0; for (int i = 0; i n; i+) xi = 0; for (int i = 0; i n ,贪

19、心法最优装载,2.贪心选择性质 可以证明最优装载问题具有贪心选择性质。 3.最优子结构性质 最优装载问题具有最优子结构性质。,由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。 算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。,贪心法汽车加油问题,问题描述： 一辆汽车加满油后可行驶 n 公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 编程任务： 对于给定的 n 和 k 个加油站位置，编程计算最少加油次数。,贪心法汽车加油问题,数据输入： 输入 2 个正整数

20、n 和 k ，表示汽车加满油后可行驶 n 公里，且旅途中有 k 个加油站。输入 k+1 个整数，表示第 k 个加油站与第 k-1 个加油站之间的距离。第 0 个加油站表示出发地，汽车已加满油。第 k+1个加油站表示目的地。 数据输出： 将编程计算出的最少加油次数输出。如果无法到达目的地，则输出“No Solution”。,贪心法汽车加油问题,最优子结构性质： 设 1i1i2ikm 是所述问题的一个最优解。容易看出， i2i3ik 是当出发地为 i1 时的一个最优解，否则将导致 i1,i2,ik 不是原问题的最优解。,贪心法汽车加油问题,贪心选择性质： 采用每次加满油后使汽车行驶尽可能远的贪心选

21、择策略。设 1i1i2ikm 是一个最优解，如果汽车在加油站 i1 不停靠加油站 j1 再加油，则我们在 j1 站停靠加油，其后再按最优解提供的停靠站加油，也能到达目的地，且停靠加油次数不会比最优次数更多。因此这是一个满足贪心选择性质的最优解。,回溯法 n皇后问题,在 nn 格的棋盘上放置彼此不受攻击的 n 个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题等价于在 nn 格的棋盘上放置 n 个皇后，任何 2 个皇后不放在同一行或同一列或同一斜线上。,解向量：(x1, x2, , xn)， xi 表示皇后 i 放在棋盘的第 i 行第 xi列 显约束

22、：xi = 1,2, ,n 隐约束： 1)不同列：xi xj 2)不处于同一正、反对角线：|i-j|xi-xj|,回溯法 n皇后问题,回溯法 n皇后问题,boolean place (int k) for ( int j=1; jk; j+) if ( (abs(k-j)=abs(xj-xk)|(xj=xk) ) return false; return true; ,void backtrack (int t) if ( tn ) sum+; else for ( int i=1; i=n; i+) xt=i; if ( place(t) ) backtrack(t+1); ,回溯法 n皇后

23、问题,用回溯法解 n 皇后问题时，可以用一棵完全 n 叉树表示其解空间。 用可行性约束函数 palce( ) 剪去不满足行、列和斜线约束的子树。 上述给出的解 n 皇后问题的回溯法描述中，递归函数 backtrack(1) 实现对整个解空间的回溯搜索。,回溯法 n皇后问题,在函数 backtrack( ) 中，当 in 时，表示算法已搜索到一个叶子结点，得到一个新的 n 皇后互不攻击放置方案，因此当前已找到的可行方案数 sum 增1。 当 i=n 时，当前扩展结点 Z 是解空间中的一个内部结点。该结点有 xi=1,2,n 共 n 个儿子结点。对当前扩展结点 Z 的每一个儿子结点，由函数 place( ) 检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或减去不可行子树。,回溯法 图的 m 着色问题,给定无向连通图 G 和 m 种不同的颜色。用这些颜色为图 G 的各顶点着色，每个顶点着一种颜色。是否有一种着色法使 G 中每条边的 2 个顶点着不同颜色。 这个问题是图的 m 可着色判定问题。若一个图最