算法设计与分析第3章分治法.ppt

第3章 分治法,学习要点: 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 （1）二分搜索技术； （2）找最大值和最小值； （3）合并排序和快速排序； （4）选择问题。,分治法的思想将一个难以直接解决的问题分解成容易求解的子问题，以便各个击破、分而治之。,3.1 一般算法,分治法的求解步骤 1 分解 2 解决 3 合并,将要求解的较大规模的问题分割成k个更小规模的子问题。,算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,算法总体思想,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。,divide-and-conquer(P) 1 if ( n = n0) /解决小规模的问题 2 then 解决子问题 return(子问题的解) for (i=2 to k)/分解问题 do yiDivided-and-Conquerer(|Pi|) TMERGE(y1,y2,yk); return,分治法的基本步骤,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件,分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。,3.2 二分检索,给定已按升序排好序的n个元素a1:n，现要在这n个元素中找出一特定元素x。 分析：,该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。,给定已按升序排好序的n个元素a1:n，现要在这n个元素中找出一特定元素x。,BINSEARCH(A,n,x) low1 highn while low=high do mid(low+high)/2; if x=Amid; then return mid; else if xAmid then highmid-1 else lowmid+1 return 0;,算法复杂度分析： 每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。,3.3 找最大值和最小值,1 将数据等分为两组，目的是分别选取其中的最大和最小值 2 递归分解直到每组元素的个数=2， 可简单找到最大和最小值 3 回溯时合并子问题的解,float An maxmin(i,j,fmax,fmin) 1 if i=j 2 then 3 fmaxAi 5 fminAi 7 else if i=j-1 8 then if AiAj 9 then 11 fmaxAj 12 fminApi 14 else 15 21 mid(i+j)/2 22 maxmin(i, mid, lmax, lmin) 23 maxmin(mid+1, j, rmax,rmin) 24,3.4 归并分类,3.4.1 基本方法 基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。,MERGESORT(A, low, high) if lowhigh then mid(low+high)/2 MERGESORT(A, low, mid) MERGESORT(A, mid+1, high); MERGE(A, low, mid, high) ,MERGE(A, low, mid, high) 1 hlow 2 ilow 3 jmid+1 4 While h=mid and j=high 5 do 7 if Ah=Aj 8 then 10 BiAh ; hh+1 13 else 14 BiAj; jj+1,20 if hmid 21 then 23 for kj to high 24 do 25 BiAk ii+1 30 else 32 for kh to mid 33 do 34 BiAk; ii+1 39 for klow to high 40 do AkBk,合并排序,最坏时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn) 辅助空间：O(n),3.4.2 改进的归并分类,MERGESORT(A, low, high, p) 1 if high-low+116 2 then INSERTIONSORT(A, LINK, low,high, p) 3 else 5 mid(low+high)/2 6 MERGESORT1(low, mid, q) 7 MERGESORT1(mid+1, high, r); 8 MERGE1(q,r p); 9 ,MERGE1(A, q, r,p) 1 iq; jr; k0; 4 while i0 and j0 5 do 7 if Ai=Aj 8 then 9 LINKki; ki; iLINKi 14 else 15 LINKkj; kj; jLINKj 21 if (i=0) then LINKkj; 23 else LINKki; 25 pLINK0,3.5 快速分类,3.5.1 快速分类算法 基本思想：选取A的某个元素， 如t=Ai， 然后将其他元素重新排序， 使A1,n中在t以前出现的元素都小于或等于t， 而所有在t后面出现的元素都大于或等于t,Partition(A,m,p) 1 vm 2 while true 3 do 5 im 6 while Ai=v do pp-1; 8 if ip then swap(Ai, Ap 9 else break 12 AmAp 13 Apv,QUICKSORT(A,p,q) 1 if pq 2 then 4 jq+1; 5 Partion (p,j); 6 QUICKSORT(p, j-1); 7 QUICKSORT(j+1, q);,3.5.2 快速分类的分析,3.6 选择问题,3.6.1 选择问题的算法 如果划分元素放在Aj的位置上，则有j-1个元素小于或等于Aj.因此，若kj, 则k小元素在Aj+1, ,n中第k-j小元素。,Select(A,n,k) 1 m1; rn+1; An+1 4 while TRUE 5 do jr; 6 Partion(m,j); 7 if k=j 8 then return 9 else if kj then rj 11 else mj+1 12 ,3.6.2 SELECT2的实现 Select2(a,left,right,k) 1 if left=right then return aleft; 3 pivotaleft;ileft+1;jright; 6 while true do 9 ii+1; while aipivot do jj+1; 15 if i=j break; 16 swap(ai,aj) 18 if j-left+1=k then return privot; 20 aleftaj;ajpivot; 22 if j-left+1k then return select (a,j+1,right, k-j-1+left); 24 else return select(a,left,j-1,k),棋盘覆盖,在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,棋盘覆盖,当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。,分治法求解棋盘覆盖问题的技巧在于划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。 k0时，可将2k2k的棋盘划分为4个2k-12k-1的子棋盘，这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为11的子棋盘。,(a)棋盘分割 (b) 构造相同子问题,下面讨论棋盘覆盖问题中数据结构的设计。 （1）棋盘：可以用一个二维数组boardsizesize表示一个棋盘，其中，size=2k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量； （2）子棋盘：整个棋盘用二维数组boardsizesize表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示； （3）特殊方格：用boarddrdc表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标; （4） L型骨牌：一个2k2k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。,/ 覆盖右上角子棋盘 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个选手各赛一次； （2）每个选手一天只能赛一次。 按此要求，可将比赛日程表设计成一个 n 行n-1列的二维表，其中，第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。,按照分治的策略，可将所有参赛的选手分为两部分，n2k个选手的比赛日程表就可以通过为n/22k-1个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单：只要让这2个选手进行比赛就可以了。,显然，这个求解过程是自底向上的迭代过程，其中左上角和左下角分别为选手1至选手4以及选手5至选手8前3天的比赛日程，据此，将左上角部分的所有数字按其对应位置抄到右下角，将左下角的所有数字按其对应位置抄到右上角，这样，就分别安排好了选手1至选手4以及选手5至选手8在后4天的比赛日程，如图(c)所示。具有多个选手的情况可以依此类推。,(b) 2k(k=2)个选手比赛 (c) 2k(k=3)个选手比赛,加4,加2,(a) 2k(k=1)个选手比赛,这种解法是把求解2k个选手比赛日程问题划分成依次求解21、22、2k个选手的比赛日程问题，换言之，2k个选手的比赛日程是在2k-1个选手的比赛日程的基础上通过迭代的方法求得的。在每次迭代中，将问题划分为4部分： （1）左上角：左上角为2k-1个选手在前半程的比赛日程； （2）左下角：左下角为另2k-1个选手在前半程的比赛日程，由左上角加2k-1得到，例如22个选手比赛，左下角由左上角直接加2得到，23个选手比赛，左下角由左上角直接加4得到； （3）右上角：将左下角直接抄到右上角得到另2k-1个选手在后半程的比赛日程； （4）右下角：将左上角直接抄到右下角得到2k-1个选手在后半程的比赛日程； 算法设计的关键在于寻找这4部分元素之间的对应关系。,temp=n; n=n*2; /填左下角元素 for (i=temp+1; i=n; i+ ) for (j=1; j=temp; j+) aij=ai-tempj+temp; /左下角元素和左上角元素的对应关系 /填右上角元素 for (i=1; i=temp; i+) for (j=temp+1; j=n; j+) aij=ai+temp(j+temp)% n; /填右下角元素 for (i=temp+1; i=n; i+) for (j=temp+1; j=n; j+) aij=ai-tempj-temp; ,分析算法4.9的时间性能，迭代处理的循环体内部有3个循环语句，每个循环语句都是一个嵌套的for循环，且他们的执行次数相同，基本语句是最内层循环体的赋值语句，即填写比赛日程表中的元素。基本语句的执行次数是： 所以，算法4.9的其时间复杂性为O(4k)。,最近对问题,设p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。 严格地讲，最接近点对可能多于一对，简单起见，只找出其中的一对作为问题的解。,用分治法解决最近对问题，很自然的想法就是将集合S分成两个子集 S1和 S2，每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合 S 中最接近的两个点都在子集 S1或 S2中，则问题很容易解决，如果这两个点分别在 S1和 S2中，问题就比较复杂了。,为了使问题易于理解，先考虑一维的情形。 此时，S中的点退化为x轴上的n个点x1, x2, , xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S