第8章-缩小规模策略.pptx

《第8章-缩小规模策略.pptx》由会员分享，可在线阅读，更多相关《第8章-缩小规模策略.pptx（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1第第八八章章 缩小规模策略缩小规模策略小规模问题的解经过某种组合可以较容易地得到原问题的解。解决这类问题的求解方法有：分治与递归、动态规划和贪心算法，这章将介绍分治与递归。p分治与递归策略p递归的典型应用p分治策略的应用2 2缩小规模策略将一个难以直接解决的大问题，分解成多个规模较小的子问题，以便各个击破、分而治之。分治法：如果原问题可以分割为k个子问题，1kn，且这k个子问题都可解，并可利用子问题的解计算出原问题的解，则可以采用分治法。递归：分治法产生的子问题往往是原问题的较小模式，常使用递归技术。3 3一个直接或间接调用自身的算法称为递归算法。递归策略u 定义u 特点n需少量的程序就

2、可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。n用有限的语句来定义对象的无限集合。u 使用条件n 原问题可以通过转化为较小的子问题来解决，而子问题的求解方法与原问题相同，被处理的数据有规律地减少。n 当子问题减小至一定程度时，调用自身算法的过程终止。递归需要有边界条件、递归推进部分和递归返回4 4递归策略u 整数划分问题将一个正整数n表示为一系列正整数之和： n=n1+n2+nk,其中，n1n2nk1，k1。该表示称为n的一个划分；不同划分的个数称为划分数，记为p(n)。【例1】整数6的11种划分。6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1;2+2+2

3、, 2+2+1+1, 2+1+1+1+1;1+1+1+1+1+1;5 5递归策略n分析在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记为q(n，m)，则可以建立如下的递归关系：(1) q(n，1) = 1，n1当最大加数n1不大于1时，只有一种划分形式：n=1+1+1(2) q(n，m) = q(n，n)，mn最大加数n1不能大于n，因此q(1，m) = 1(3) q( n, n ) = 1 + q ( n, n-1)正整数n的划分，由n1=n的划分和n1n-1的划分组成(4) q(n, m ) = q(n, m-1) + q (n-m, m), nm1正整数n的最大加数n1不大

4、于m的划分，由n1=m的划分和n1m-1的划分组成6 6递归策略1mn m)m,q(n) 1mq(n,mn ) 1nq(n,1mn n)q(n,1m1,n 1m)q(n, n计算q(n, m)的递归计算式7 7分治策略u基本思想将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归求解这些子问题，并将子问题的解合并，则得到原问题解。u分治法求解问题的特征n(1) 问题的规模缩小到一定的程度就可容易解决n(2) 问题可分解为若干个规模较小的相同问题n(3) 利用原问题分解出的子问题的解可合并为原问题的解n(4) 问题所分解出的各个子问题是相互独立的，即子问题之间不

5、包含公共的子问题8 8分治策略u分治法的一般步骤n分解 将要解决的问题划分成若干规模较小的同类问题n求解 当子问题划分得足够小时，用较简单的方法解决n合并 按原问题要求，将子问题的解逐层合并构成原问题解DataType Divide-and-Conquer (P) if ( |P| = n0 ) Adhoc( P ); divide P into smaller subinstances; P1, P2, , Pk; for ( i=1; i0) hanoi(n - 1, from, to, tmp); /将将from杆上的杆上的n-1块金片移至块金片移至tmp杆杆 printf(take %

6、d块金片 from %c to %cn,n ,from,to); /将将from上的一块金片移至上的一块金片移至yo杆杆 hanoi(n - 1, tmp, from, to); /将将tmp杆上的杆上的n-1块金片移至块金片移至to杆上杆上 /Hanoi1313递归算法的典型应用u全排列问题n问题描述R=r1，r2，rn是要进行排列的n个元素，Ri=Rri。集合X中元素的全排列记为Perm(X)；(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。R的全排列可递归定义为：(1) 当n=1时，Perm(R)=(r1)，r1是集合R中的唯一元素。(2) 当n1时

7、，Perm(R)由(r1)Perm(R1)，(r2)Perm(R2)，(rn)Perm(Rn)构成。1414递归算法的典型应用【例2】集合1,2,3的全排列。1515递归算法的典型应用n递归算法void Swap(int &a, int &b) int t = a; a = b; b = t; /Swapvoid Perm(int R, int k, int m ) /产生集合产生集合Rk:m的全的全排列排列 if (k=m) /Rk:m具有一个排列，将其输出具有一个排列，将其输出 for (int i=0; i=k; i+) printf(%d ,Ri); printf(n); else /

8、R k:m具有多个排列并递归生成具有多个排列并递归生成 for (int i = k; ihigh时，查找失败 将k与mid指向的记录比较若k=rmid.key，则若krmid.key，则1818分治策略的应用n查找过程找211 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92highlowmid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid查找成功1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88

9、92lowhighmid211919分治策略的应用找661 2 3 4 5 6 7 8 9 10 5 10 19 21 31 37 42 48 50 55 highlowmid1 2 3 4 5 6 7 8 9 10 5 10 19 21 31 37 42 48 50 55 lowhighmidhighlow mid55high lowlowmid1 2 3 4 5 6 7 8 9 10 5 10 19 21 31 37 42 48 50 55 high查找失败2020分治策略的应用n算法int BinerSerch(int R ,int x) int low,mid,high; low=0;

10、 high=n-1; while(low=high) mid=(low+high)/2 ; if(x=Rmid) return mid; if(xRmid ) high=mid-1; else low=mid+1; return -1; 2121分治策略的应用n性能分析第i次比较 剩余 n/2i 若最后只剩一个，则n/2i=1，即i=log2n即比较次数O(log2n)时间复杂度 O(log2n)n 特点 表中元素需有序排列，且顺序存储。但对需频繁插入或删除操作的数据集来说，维护有序会有较大的工作量。2222分治策略的应用n查找判定树 描述查找过程的二叉树。树中结点的数字表示该结点在有序表中的

11、位置（1n）。6391741025811【例3】 具有11个结点的折半查找判定树。结论：在查找成功时进行的比较次数最多不超过树的深度。 2323分治策略的应用【例4】建立具有13个结点的判定树，并其成功查找的ASL。73101851224139611ASL=1/13 (1+22+34+46)=41/133.152424分治策略的应用u归并排序n基本思想n两路归并 设初始序列含n个记录，可看成n个有序子序列，各序列长度为1；再两两合并，如此重复，直至得到长度为n的有序序列。 两两合并，得到 n/2 个长度为2或1的有序子序列;将元素集合分割成n个（ 2）子集，对每个子集分别排序，再将排好序的子集

12、归并为一个集合。若n为1，排序终止。2525分治策略的应用【例5】两路归并过程示例。2626分治策略的应用n算法两个有序文件的合并void Merge(rectype R,rectype T,int low,int mid,int high) / RlowRlowmidmid与与Rmid+1Rmid+1highhigh是两个有序文件是两个有序文件 / 结果文件结果文件TlowTlowhighhigh int i, j, k; i=low; j=mid+1; k=low; while (i=mid) & (j=high) if (Ri.key=Rj.key) Tk+=Ri+; else Tk+=

13、Rj+; while (i=mid) Tk+=Ri+; while (j=high) Tk+=Rj+;2727分治策略的应用n算法一趟归并void MergePass(rectype R , rectype T , int len) / 对对R R中中 n/n/lenlen 个有序子文件做一趟归并，结果放个有序子文件做一趟归并，结果放在在T T中中 int i, j; i=0 ; / i i向第一对子文件的起始点向第一对子文件的起始点 while (i+2 len 1n) /两个长度为两个长度为lenlen的有序子文件的有序子文件 Merge(R, T, i, i+len-1, i+2 len

14、-1); i=i+2len; / i i指向下一对子文件的起始点指向下一对子文件的起始点 if (i+len-1)n-1) / 子文件个数子文件个数偶数偶数, ,一一个长度小于个长度小于lenlen Merge(R, T, i, i+len-1, n-1); else / 子文件个数为奇数子文件个数为奇数 for (j=i; jn; j+) Tj=Rj; 2828分治策略的应用n算法两路归并void MergeSort(rectype R ) / 对对R R进行二路归并排序进行二路归并排序 int len; len=1; while (len=temp.key) & (ij) j; if (i

15、j) Ri+=Rj; / “交换交换”R”Ri i 和和Rj Rj while (Ri.key=temp.key) & (ij) i+; if (ij) Rj=Ri; / “交换交换”R”Ri i 和和Rj Rj while (i!=j); Ri=temp; / 基准基准temptemp已被最后定位已被最后定位 return i;3434分治策略的应用void QuickSort(rectype R , int s1, int t1) / 对对Rs1Rs1到到Rt1Rt1做快速排序做快速排序 int i; if (s1t1) / 只有一个记录或无记录时无须排序只有一个记录或无记录时无须排序 i

16、=PARTITION(R, s1, t1); / 对对Rs1Rs1到到Rt1Rt1做划分做划分 QuickSort(R, s1, i 1); / 递归处理左区间递归处理左区间 QuickSort(R, i+1, t1); / 递归处理右区间递归处理右区间 3535分治策略的应用n算法评价 时间复杂度T(n)=O(nlog2n) 最好情况 最坏情况)(21) 1(21)()(2211nOnnninnTni待排文件有序时，蜕变为起泡排序每次所选“基准”是序列中的中值记录 )log()(2nnOnT3636本章小结l分治法是将一个难以直接解决的大问题，分解成多个规模较小、更易解决的子问题。l由分治法产生的子问题往往是原问题的较小模式，使用递归策略往往使算法的描述和函数的定义简洁，且易于理解。l分治与递归经常同时应用于算法设计之中，由此产生如快速排序、二分搜索等许多高效算法。