第3章 分治法.ppt

1、第3章 分治法,张阳 信息工程学院,第3章 分治法,目录 概述 二分查找 循环赛日程表 合并排序 快速排序,分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 凡治众如治寡，分数是也。 -孙子兵法,分治策略,将要求解的较大规模的问题分割成k个更小规模的子问题。,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,分治策略,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个

2、子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治策略,将问题的实例划分为同一个问题的几个较小的实例，最好拥有同样的规模。 对这些较小的实例求解。 如果有必要，合并这些较小规模的解，以得到原问题的解。,分治策略,分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问

3、题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,分治法的适用条件,分治法的基本步骤,divide-and-conquer(P) if ( | P | = n0) Adhoc(P); /

4、解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 最好使子问题的规模大致相同。 一种平衡子问题的思想,分治法的复杂性分析,一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且Adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位

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

6、数。 XY = ac 2n + (a-b)(d-c)+ac+bd) 2n/2 + bd XY = ac 2n + (a+b)(d+c)-ac-bd) 2n/2 + bd,大整数的乘法,大整数的乘法,复杂度分析 T(n)=O(nlog3) =O(n1.59)较大的改进,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2) 效率太低 分治法: O(n1.59) 较大的改进 更快的方法?,如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。 最终的，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作

7、是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。 是否能找到线性时间的算法？目前为止还没有结果。,大整数的乘法,二分查找,给定已排好序的n个元素s1,sn，现要在这n个元素中找出一特定元素x。 顺序查找 : O(n),算法思想： 取中间元素与特定查找元素x进行比较，如果x等于中间元素，则算法终止； 如果x小于中间元素，则在序列的左半部继续查找； 否则，在序列的右半部继续查找； 重复利用了元素间的次序关系。,二分查找,步骤1：确定合适的数据结构。设置数组sn来存放n个已排好序的元素；变量low和high表示查找范围在数组中的下界和上界；middle表示查找范围的中间位置；

8、x为特定元素； 步骤2：初始化。令low=0；high=n-1； 步骤3：middle=(low+high)/2，即指示中间元素； 步骤4：判定low小于等于high是否成立，如果成立，转步骤5；否则，算法结束； 步骤5：判断x与smiddle的关系。如果x=smiddle，算法结束；如果xsmiddle，则令low=middle+1；否则令high=middle-1，转步骤3。,二分查找,例： 查找元素x=12,（1）,（2）,二分查找,（3）,（4）,二分查找,递归算法 int BinarySearch(nt sn,int x,int low,int high) if (lowhigh)

9、return -1; int middle=(low+high)/2; if(x=smiddle) return middle; else if(xsmiddle) return BinarySearch (s, x, middle+1, high); else return BinarySearch (s, x, low, middle-1); ,二分查找,迭代算法 int NBinarySearch(int n,int sn,int x) int low=0,high=n-1; while(lowsmiddle) low=middle+1; else high=middle-1; retu

10、rn -1; ,二分查找,当n=1时，T(n)=O(1)。 当n1时，计算序列的中间位置及进行元素的比较，需要常量时间O(1)。递归地求解规模为n/2的子问题，所需时间为T(n/2)。 T(n)=T(n/2)+O(1) = =T(n/2x)+xO(1) 令n=2x，则x=logn。 T(n)=T(1)+logn=O(1)+O(logn)。 时间复杂性为O(logn)。,二分查找：复杂度分析,棋盘覆盖,在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的

11、所有方格，且任何2个L型骨牌不得重叠覆盖。,当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。,棋盘覆盖,public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L

12、型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角,boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s ,棋盘覆盖,问题描述 设有n=2k个运动员要进行羽毛球循环赛，现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其它n-1个

13、选手各赛一次； （2）每个选手一天只能比赛一次； （3）循环赛一共需要进行n-1天。 由于n=2k，显然n为偶数。,循环赛日程表,设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次； (3)循环赛一共进行n-1天。,按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,循环赛日程表,如何分，即如何合理地进行问题的分解？ 一分为二 如何治，即如何进行问题的求解？ 进行合并

14、问题的关键发现循环赛日程表制定过程中存在的规律性。,循环赛日程表,n=21个选手的比赛日程表的制定。,循环赛日程表：求解n=21,n=22个选手的比赛日程表的制定,表3-2子问题的比赛日程表 表3-3 22个选手的比赛日程表,循环赛日程表：求解n=22,表3-4 4个子问题的比赛日程表 表3-5 子问题解的合并,循环赛日程表：求解n=23,表3-6 23个选手的比赛日程表,循环赛日程表：求解n=23,Void Round_Robin_Calendar(int k, int *a) int n=1,i,j,s; for(i=1;i=k;i+) n*=2; for(i=1;i=n;i+) a1i=

15、I; int m=1; for(s=1;s=k;s+) n/=2; for(int t=1;t=n;t+) for(i=m+1;i=2*m;i+) for(j=m+1;j=2*m;j+) aij+(t-1)*m*2=ai-mj+(t-1)*m*2-m; aij+(t-1)*m*2-m=ai-mj+(t-1)*m*2; m*=2; ,循环赛日程表：算法,问题： 对n个元素进行排序 算法思想 （1）分解：将待排序元素分成大小大致相同的两个子序列。 （2）求解子问题：用合并排序法分别对两个子序列递归地进行排序。 （3）合并：将排好序的有序子序列进行合并，得到符合要求的有序序列。,合并排序,例：,合并

16、排序：范例,Merge(A,low,middle,high) 将排好序的两个子序列Alow:middle和Amiddle+1:high进行合并 其中，low、high表示待排序范围在数组中的上界和下界，middle表示两个序列的分开位置,合并排序：合并算法,void Merge(int A，int low，int middle，int high) int i,j,k; int *B=new inthigh-low+1; / 临时存放合并结果 i=low; j=middle+1; k=low; while(i=middle / 搬回原来的数组 ,合并排序：合并算法,void MergeSort

17、(int A，int low，int high) int middle; if (lowhigh) middle=(low+high)/2; /取中点 MergeSort(A,low,middle); MergeSort(A,middle+1,high); Merge(A,low,middle,high); /合并 ,合并排序：排序算法,当n=1时，T(n)=O(1)。 当n1时，将时间T如下分解： 分解：这一步需要常量时间O(1)。 解决子问题：递归求解两个规模为n/2的子问题，所需时间为2T(n/2)。 合并：Merge算法可在O(n)时间内完成。 得到合并排序算法运行时间T(n)的递归形

18、式为：,合并排序：时空复杂度,T(n)=2xT(n/2x)+xO(n) 求得T(n)=nT(1)+nlogn=n+nlogn，即合并排序算法的时间复杂性为O(nlogn)。 工作空间取决于Merge算法 空间复杂性为O(n)。,合并排序：时空复杂度,问题： 对n个元素进行排序 算法思想 通过一趟扫描将待排序的元素分割成独立的三个部分：第一个部分中所有元素均不大于基准元素、第二个是基准元素、第三个部分中所有元素均不小于基准元素。 需要再按此方法对第一个序列和第三个序列分别进行排序。 整个排序过程可以递归进行。,快速排序,分解 在Rlow:high中选定一个元素作为基准元素(pivot)，以此基准

19、元素为标准将待排序序列划分为两个子序列并使序列Rlow:pivotpos-1中所有元素的值均小于等于Rpivotpos，序列Rpivotpos+1:high中所有元素的值均大于等于Rpivotpos。 求解子问题 对子序列Rlow:pivotpos-1和Rpivotpos+1:high,分别通过递归调用快速排序算法来进行排序。 合并 就地排序。,快速排序,（a）取第一个元素。 （b）取最后一个元素。 （c）取位于中间位置的元素。 （d）“三者取中的规则”。 （e）取位于low和high之间的随机数，用Rk作为基准元素。,快速排序：基准元素选取,图1 划分初始状态,图2 1次交换后的状态,图3 i后移1位后的状态,图4 2次交换后的状态,快速排序：范例,原始序列： 49 38 65 97 76 13 27,图6 4次交换后的状态,图5 3次交换后的状态,图7 j前移1位后的状态,快速排序：范例,假设待排序序列为Rlow:high，该划分过程以第一个元素作为基准元素。 步骤1：设置两个参数i和j，i=low，j=high； 步骤2：选取Rlow作为基准元素，并将该值赋给变量pivot； 步骤3：令j自j位置开始向左扫描，如果j位置所对应的元素的值大于等于pivot，则j前移一个位置(