分治策略2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征,：,该问题的规模缩小到一定的程度就可以容易地解决；,该问题可以分解为若干个规模较小的相同问题，即该问题具有,最优子结构性质,利用该问题分解出的子问题的解可以合并为该问题的解；,该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,1,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑,贪心算法,或,动态规划,。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用,动态规划,较好。,使用分治法的前提是问题是可分治的。所谓可分治，是指满足下列两点：,（1）,可分解,问题能分解为更小、更容易解决的子问题。,（2）,可综合,由子问题的综合，可以解决真个问题。,2,分治法的基本步骤,divide-and-conquer(P),if(|P|=n0)adhoc(P);/,解决小规模的问题,divide P into smaller subinstances P1,P2,.,Pk；/,分解问题,for(i=1,i=k,i+),yi=divide-and-conquer(Pi);/,递归的解各子问题,return merge(y1,.,yk);/,将各子问题的解合并为原问题的解,3,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的,k,个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种,平衡,(,balancing),子问题,的思想，它几乎总是比子问题规模不等的做法要好。,4,分治法的复杂性分析,一个分治法将规模为,n,的问题分成,k,个,规模为,nm,的子问题去解。设分解阀值,n0=1，,且,adhoc,解规模为1的问题耗费1个单位时间。再设将原问题分解为,k,个子问题以及用,merge,将,k,个子问题的解合并为原问题的解需用,f(n),个单位时间。用,T(n),表示该分治法解规模为|,P|=n,的问题所需的计算时间，则有：,5,通过迭代法求得方程的解：,注意：,递归方程及其解只给出,n,等于,m,的方幂时,T(n),的值，但是如果认为,T(n),足够平滑，那么由,n,等于,m,的方幂时,T(n),的值可以估计,T(n),的增长速度。通常假定,T(n),是单调上升的，从而当,m,i,nm,i+1,时，,T(m,i,)T(n)=l),int m=l+r)/2;,if(x=am)return m;,if(x=0,时，有,4,k,种不同的特殊棋盘。,如图：当,k=2,时，有16个特殊棋盘。,用图示的4种不同形态的,L,型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个,L,型骨牌不得重叠覆盖。在一个2,k,2,k,个方格组成的棋盘中，,L,型骨牌个数恰为,（,4,k,-1）/3,22,当,k0,时，将2,k,2,k,棋盘分割为,4个2,k-1,2,k-1,子棋盘(,a),所示,。,特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，,可以用一个,L,型骨牌覆盖这3个较小棋盘的会合处，如(,b),所示，,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1,1。,23,void chessBoard(int tr,int tc,int dr,int dc,int size),if(size=1)return;,int t=tile+,/L,型骨牌号,s=size/2;/,分割棋盘,/覆盖左上角子棋盘,if(dr tr+s&dc=tr+s&dc=tr+s&dc=tc+s),/,特殊方格在此棋盘中,chessBoard(tr+s,tc+s,dr,dc,s);,else/,用,t,号,L,型骨牌覆盖左上角,boardtr+stc+s=t;,/,覆盖其余方格,chessBoard(tr+s,tc+s,tr+s,tc+s,s);,复杂度分析,T(n)=O(4,k,),渐进意义下的最优算法,25,排序问题,在一般情况下，排序问题的输入是,n,个数的一个序列，要设计一个有效的排序算法，产生输入序列的一个重排，是序列从小到大的顺序排列。,算法的输入通常是一个有,n,个元素的数组，当然也可以用其它形式来表示输入，如链表等。,在实际中，待排序的对象往往不是单一的数而是一个记录，我们是根据其中的一个关键字作为排序的依据。,26,合并排序,基本思想：,将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。,void MergeSort(Type a,int left,int right),if(leftright)/,至少有2个元素,int i=(left+right)/2;/,取中点,mergeSort(a,left,i);,mergeSort(a,i+1,right);,merge(a,b,left,i,right);/,合并到数组,b,copy(a,b,left,right);/,复制回数组,a,27,算法,mergeSort,的递归过程可以消去。,初始序列,49 38 65 97 76 13 27,38 49 65 97 13 76 27,第一步,第二步38 49 65 97 13 27 76,第三步,13 27 38 49 65 76 97,28,复杂度分析,T(n)=O(nlogn),渐进意义下的最优算法,最坏时间复杂度：,O(,nlogn,),平均时间复杂度：,O(,nlogn,),辅助空间：,O(n),29,快速排序,在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。,template,void QuickSort(Type a,int p,int r),if(pr),int q=Partition(a,p,r);,QuickSort(a,p,q-1);/,对左半段排序,QuickSort(a,q+1,r);/,对右半段排序,30,template,int Partition(Type a,int p,int r),int i=p,j=r+1;,Type x=ap;,/,将,x,的元素交换到右边区域,while(true),while(a+i x);,if(i=j)break;,Swap(ai,aj);,ap=aj;,aj=x;,return j;,31,例,初始关键字：,49,38 65 97 76 13 27 50,i,j,j,i,完成一趟排序：(27 38 13),49,(76 97 65 50),分别进行快速排序：(13),27,(,38),49,(50 65),76,(97),快速排序结束：13,27,38,49,50,65,76,97,49,27,i,j,i,j,i,j,49,65,j,i,13,49,i,j,49,97,i,j,32,快速排序算法的性能,取决于划分的对称性,。通过修改算法,partition，,可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在,ap:r,中随机选出一个元素作为,划分基准,，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。,template,int RandomizedPartition(Type a,int p,int r),int i=Random(p,r);,Swap(ai,ap);,return Partition(a,p,r);,最坏时间复杂度：,O(n,2,),平均时间复杂度：,O(,nlogn,),辅助空间：,O(n),或,O(,logn,),33,