1、第2章 分治策略(2)教学目的与要求1.掌握设计有效算法的分治策略。2.要求通过范例的学习掌握分治策略的技巧。2.9 线性时间选择线性时间选择v给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素。v采用分治策略，利用在快速排序中使用到的RandomizedPartition算法，将序列随机分成两部分api和ai+1r，使得api的每个元素都不大于ai+1r的每个元素，而此时ai恰好为第i小元素，接着计算子数组api的元素个数j，如果kj，则apr中第k小的数落在子数组api中，如果kj，则apr中第k小的数落在子数组ai+1r中，此时要找的apr中第k小的元素是ai+
2、1r中第k-j小的元素。vtemplatevint Partition(Type a,int p,int r)vv int i=p,j=r+1;v Type x=ap,t;v /将 x的元素交换到右边区域v while(true)v v while(a+i x);/从右到左找到第一个不大于ap的元素ajv if(i=j)break;v t=ai;ai=aj;aj=t;/交换ai和ajv v ap=aj;aj=x;/交换ap和ajv return j;vvtemplatevint RandomizedPartition(Type a,int p,int r)vv int i=Random(p,r
3、);v Type t;v t=ai;ai=ap;ap=t;v return Partition(a,p,r);vvtemplatevType RandomizedSelect(Type a,int p,int r,int k)vv int i,j;v if(p=r)return ap;v i=RandomizedPartition(a,p,r);v j=i-p+1;/计算子数组api的元素个数jv if(k=j)return RandomizedSelect(a,p,i,k);v else return RandomizedSelect(a,i+1,r,k-j);vv在最坏情况下（如在找最小元
4、素时，总在最大元素处划分），算法RandomizedSelect需要(n2)计算时间，但该算法的平均性能较好。v如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最坏情况下在最坏情况下用O(n)时间完成选择任务。例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n)。由此可得T(n)=O(n)。v例如，将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素
5、排好序，并取出每组的中位数，共n/5个。递归调用Select来找出这n/5个元素的中位数（也就是这些中位数的中位数），若n/5是偶数，则找它的两个中位数中较大的一个，然后以这个元素作为基准划分。v设所有元素互不相同。在这种情况下，找出的基准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 vtemplatevint Partition(Type*a,int p,int r,T
6、ype x)vv int i,left=p,right=r;v Type*b=new Type r-p+1;v for(i=0;i r-p+1;i+)bi=ap+i;v for(i=p;i=r;i+)v v if(bi x)aright-=bi;v v for(i=left;i=right;i+)ai=x;v delete b;return left;vv/找ap.r中第k小的元素返回vtemplatevType Select(Type a,int p,int r,int k)vv int i,j;Type x,t;v if(r-p75)Sort(a,p,r);return ap+k-1;v
7、for(i=0;i=(r-p-4)/5;i+)v v x=ap+5*i至ap+5*i+4的第3小元素;v /将ap+5*i.p+5*i+4的第3小元素与ap+i交换位置v t=ap+i;ap+i=x;x=t;v v /*每一组的中位数排在了ap.p+(r-p-4)/5的位置，现在找中位数的中位数x，r-p-4即上面所说的n-5*/v x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);v /*将apr中不大于x的放在x左边，比x大的放在x右边，返回中位数的中位数x的下标i*/v i=Partition(a,p,r,x),v j=i-p+1;/求x左边有多少个元素，这些元素
8、都比x小v if(k=j)return Select(a,p,i,k);v else return Select(a,i+1,r,k-j);vv上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=n，01。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。v设n=r-p+1，即n为输入数组的长度，算法的递归调用在n75时才执行，n75的时候，算法Select所用的计算时间不超过常数C1，找到中位数的中位数x后，算法Select以x为基准调用函数Partition对数组apr进行划
9、分，这需要O(n)时间，算法Select的for循环体执行了n/5次，每一次需要O(1)时间，因此执行for循环共需要O(n)时间。v设对n个元素数组调用Select算法需要T(n)时间，那么找中位数的中位数x至多用了T(n/5)次时间，既然按照基准x划分所得到的两个子数组分别至多3n/4个元素，所以不论对哪一个子数组调用Select算法都至多用了T(3n/4)的时间。v因此，v得到，T(n)=O(n)7575)4/3()5/()(21nnnTnTnCCnT2.10 最接近点对问题最接近点对问题v给定平面上n个点，找出其中一对点，使得在n个点所构成的所有点对中，该点对的距离最小。v最接近点对可
10、能多于一对，简单起见，只考虑找其中的一对作为问题的解。如果我们将每一个点和其他n-1个点的距离算出来，找到最小距离的两个点，算法效率需要O(n2)的计算时间，效率太低。下面设计一个耗时O(nlog2n)的算法：v为了使问题易于理解和分析，先来考虑一维一维的情形。此时，S中的n个点退化为x轴上的n个实数 x1,x2,xn。最接近点对即为这n个实数中相差最小的2个实数。假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设d=min|p1-p2|,|q1-q2|，S中的最接近点对
11、或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。v问题在于：能否在线性时间内找到能否在线性时间内找到p3、q3？v如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3(m-d,m，q3(m,m+d。由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，如果(m-d,m中有S中的点，则此点就是S1中最大点。因此，我们用线性时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。从而我们用线性时间就可以将S1
12、的解和S2的解合并成为S的解。v选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=mind1,d2，S中的最接近点对或者是d，或者是某个p,q，其中pP1且qP2。v问题在于：能否在线性时间内找到能否在线性时间内找到p、q？v考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p,q)d。满足这个条件的P2中的点一定落在一个d2d的矩形R中。由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。因此，在分治法的合并步
13、骤中最多只需要检查6n/2=3n个候选者。v证明：证明：将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)(2d/3)的矩形。若矩形R中有多于6个S中的点，由鸽舍原理易知至少有一个(d/2)(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则vdistance(u,v)d，与d的意义矛盾。222223625)3/2()2/()()()()(dddvyuyvxuxv为了确切地知道要检查哪6个点，可将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点，距离p在l上投影
14、点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。v下面给出用分治法求二维最接近点对算法：vbool Cpair2(S,&d)vv n=|S|;v if(n 2)return false;v 1、m=S中各点x坐标下标的中位数;v 构造S1和S2,S1=pS|x(p)x(m)v 2、Cpair2(S1,d1);Cpair2(S2,d2);v 3、dm=min(d1,d2);v 4、令P1是S1中距垂直分割线l
15、的距离在dm之内的所有点组成的集合；P2是S2中距分割线l的距离在dm之内所有点组成的集合；v 将P1和P2中的点依其y坐标值排序；并设X和Y是相应的已排好序的点列；第1步：O(n)第3步：O(1)第2步：2T(n/2)第4步：O(nlog2n)第5步：O(n)v 5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；v 当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；v 设dl是按这种扫描方式找到的点对间的最小距离；v 6、d=min(dm,dl);v return true;v v若在每次执行第4步的时候进行排序，则最坏情况下
16、第4步需要O(nlog2n)时间，这不符合要求，需要做一个技术处理。第6步：O(1)v使用预排序技术，在使用分治法之前，预先将S中n个点依其y坐标排好序，设排好序的点为P*，在执行分治法的第4步时，只要对P*进行1次线性扫描，即可抽取出我们所需要排好序的点列X和Y。然后，在第5步中再对X做一次线性扫描，即可求得dl。因此，第4步和第5步两遍扫描合在一起只要用O(n)时间。这样，经过预排序处理后算法后，算法Cpair2所需的计算时间T(n)满足递归方程 v即T(n)=O(nlog2n)。v根据这个思想，写出的程序如下：44)()2/(2)1()(nnnOnTOnTv#include v#incl
17、ude vconst int TOTAL=10000;vusing namespace std;vclass Pointvvpublic:v double getx()const return x;v double gety()const return y;v double setx(double xx)x=xx;return x;v double sety(double yy)y=yy;return y;v virtual bool operator=(Point a)return true;vprotected:v double x,y;v;v/类PointX和PointY分别表示按照x坐
18、标和y坐标排序的点vclass PointX:public Pointvvpublic:v bool operator=(Point a)const return(x=a.getx();v friend inline double distance(const PointX&u,const PointX&v);v;vclass PointY:public Pointvvpublic:v bool operator=(Point a)const return(y=a.gety();v int setp(int pp)p=pp;return p;v int getp()return p;v fri
19、end inline double distance(const PointY&u,const PointY&v);vprivate:v int p;/p表示以x坐标排序时，该点对应的下标(序号)v;vinline double distance(const PointX&u,const PointX&v)vv double dx=u.getx()-v.getx();v double dy=u.gety()-v.gety();v return sqrt(dx*dx+dy*dy);vvinline doulble distance(const PointY&u,const PointY&v)vv
20、 double dx=u.getx()-v.getx();v double dy=u.gety()-v.gety();v return sqrt(dx*dx+dy*dy);vvtemplate vvoid Merge(Type Y,Type Z,int l,int m,int r)vv /将有序的Zl.m与有序的Zm+1.r合并到Yl.rv Type*a=&Zl;Type*b=&Zm+1;Type*c=&Yl;v int anum=m-l+1,ap=0;v int bnum=r-m,bp=0;v int cnum=r-l+1,cp=0;v while(ap anum&bp bnum)v v i
21、f(aap=bbp)ccp+=aap+;v else ccp+=bbp+;v v while(ap anum)ccp+=aap+;v while(bp bnum)ccp+=bbp+;vvtemplate vvoid MergeSort(Type a,int n)vv int anum,bnum,i;Type*b,*c;v if(n=1)return;v anum=n/2;v b=a+anum;bnum=n-anum;v MergeSort(a,anum);v MergeSort(b,bnum);v c=new Typen;v Merge(c,a,0,anum-1,n-1);v for(i=0;
22、in;i+)ai=ci;v delete c;vv/*X存放输入的点集，X和Y分别表示按照x坐标和y坐标排序的点，l和r表示点集Y中成员p的范围*/vvoid closest(PointX X,PointY Y,PointY Z,int l,int r,PointX&a,PointX&b,double&d)vv double d1,d2,d3,dp;int f,g,m,i,j,k;double dr;v PointX ar,br;v if(r-l=1)/2点的情况v v a=Xl;b=Xr;d=distance(Xl,Xr);v return;v v if(r-l=2)/3点的情况v v d1
23、=distance(Xl,Xl+1);d2=distance(Xl+1,Xr);v d3=distance(Xl,Xr);v if(d1=d2&d1=d3)v v a=Xl;b=Xl+1;d=d1;v v else if(d2=d3)v v a=Xl+1;b=Xr;d=d2;v v elsev v a=Xl;b=Xr;d=d3;v v return;v v m=(l+r)/2;/m为点集Y中成员p的范围的中位数 v /*将已经按照y坐标排序的点集Yl.r，等分成两个子集复制到Z，其中Zl.(l+r)/2中的每个点的x坐标都小于Z(l+r)/2+1.r中的每个点的x坐标*/v f=l;g=m+1
24、;v for(i=l;i m)Zg+=Yi;v else Zf+=Yi;v v /递归处理这两个子集(注意参数传递时Z与Y位置的变化)v closest(X,Z,Y,l,m,a,b,d);v closest(X,Z,Y,m+1,r,ar,br,dr);v if(dr d)/d表示这两个子集中各自找到的最近点对的距离较小者v v a=ar;b=br;d=dr;v v Merge(Y,Z,l,m,r);/重构数组Yv /将与分割线距离为d的点置如数组Z中v k=l;v for(i=l;i=r;i+)v v if(fabs(Ym.getx()-Yi.getx()d)Zk+=Yi;v v /搜索Zl.
25、k-1，若其中存在两点的距离小于d，则更新dv for(i=l;ik;i+)v v for(j=i+1;jk&Zj.gety()-Zi.gety()d;j+)v v dp=distance(Zi,Zj);v if(dp d)v v d=dp;a=XZi.getp();b=XZj.getp();v v v vvbool Cpair2(PointX X,int n,PointX&a,PointX&b,double&d)vv int i;PointY*Z,*Y;v if(n 2)return false;v MergeSort(X,n);/将各点按照x坐标排序v Y=new PointYn;v fo
26、r(i=0;in;i+)/将数组X内的信息写入数组Yv v Yi.setp(i);/同一点在数组X中的坐标的下标v Yi.setx(Xi.getx();v Yi.sety(Xi.gety();v v MergeSort(Y,n);/将各点按照y坐标排序v Z=new PointYn;v closest(X,Y,Z,0,n-1,a,b,d);v delete Y;delete Z;return true;vvint main()vv PointX XTOTAL,a,b;v int n=TOTAL;v double d;v int i;v for(i=0;in;i+)v v Xi.setx(dou
27、ble)rand()/100);v Xi.sety(double)rand()/100);v v Cpair2(X,n,a,b,d);v printf(%f,%f)(%f,%f)%fn,a.getx(),a.gety(),b.getx(),b.gety(),d);v return 0;v2.11 循环赛日程问题循环赛日程问题v设有n=2k(k为正整数)个运动员进行乒乓球循环赛正赛，现要求设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。v将比赛日程设计为n行和n-1列的一个表，在表中第i行第j列处填写第i
28、个选手在第j天的对手。v按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。v图中所列出的正方形表是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。
29、该算法没有使用递归，这也说明并非所有的分治策略都要使用递归。123456782143658734127856432187655678123465872143785634128765432112345678以k=3，n=8名选手为例。初始状态：填写第0列。之后，进行k=3个阶段，设第s个阶段要循环ns次，则n1=n/2=4，n2=n1/2=2，n3=n2/2=11221344356657887第1阶段（s=1）：填写第1列（j=1）循环4次，循环次数为n1=n/2=4，8个大块，每个大块含m*m=1*1个小块，每次循环复制2个大块，在第t（t=0,1,2,3）次循环时，执行ai+2*t*m-mj
30、=ai+2*t*mj-m和ai+2*t*mj=ai+2*t*m-mj-m，i=1，分别把左下角复制到右上角，把左上角复制到右下角 12342143341243215678658778568765第2阶段（s=2）：填写第2,3列（j=2,3）循环2次，循环次数为n2=n1/2=2，4个大块，每个大块含m*m=2*2个小块，每次循环复制2个大块，在第t（t=0,1）次循环时，执行ai+2*t*m-mj=ai+2*t*mj-m和ai+2*t*mj=ai+2*t*m-mj-m，i=2,3，分别把左下角复制到右上角，把左上角复制到右下角 12345678214365873412785643218765
31、56781234658721437856341287654321第3阶段（s=3）：填写第4,5,6,7列（j=4,5,6,7）循环1次，循环次数为n3=n2/2=2，2个大块，每个大块含m*m=4*4个小块，每次循环复制2个大块，在第t（t=0）次循环时，执行ai+2*t*m-mj=ai+2*t*mj-m和ai+2*t*mj=ai+2*t*m-mj-m，i=4,5,6,7，分别把左下角复制到右上角，把左上角复制到右下角vvoid Table(int k,int aN)vv int n=1,m=1,i,j,t,s;v for(i=1;i=k;i+)n*=2;v for(i=0;in;i+)v
32、v ai0=i+1;v v /k个阶段，从左到右v for(s=1;s=k;s+)v v n/=2;v /*每个阶段有t次循环，即复制n个大块*/v for(t=0;tn;t+)v v /j表示列v for(j=m;j2*m;j+)v v for(i=m;i2*m;i+)v v ai-m+2*t*mj=ai+2*t*mj-m;/右上角=左下角 v ai+2*t*mj=ai-m+2*t*mj-m;/右下角=左上角v v v v m*=2;v vvvoid Table(int k,int aN)vv int n=1,m=1,i,j,t,s;v for(i=1;i=k;i+)n*=2;v for(i
33、=0;in;i+)v v ai0=i+1;v v for(s=1;s=k;s+)/k个阶段，从左到右v v n/=2;v for(t=0;tn;t+)/每个阶段有t次循环，即复制n个大块v v for(j=m;j2*m;j+)/j表示列v v for(i=m;i2*m;i+)v v ai-m+2*t*mj=ai+2*t*mj-m;/右上角=左下角 v ai+2*t*mj=ai-m+2*t*mj-m;/右下角=左上角v v v v m*=2;v vv循环赛日程安排问题也可以写成递归算法，如下：vvoid table(int x,int k,int*a)vv /此函数为从x号球员起的共2的k次方名球员安排日程表v int i,j,y;v if(k=1)/只有两名球员v v ax0=x;ax1=x+1;v ax+10=x+1;ax+11=x;v v elsev v y=pow(2,k-1);v table(x,k-1,a);v table(x+y,k-1,a);v for(i=x;ix+y;i+)v v for(j=y;j2*y;j+)aij=ai+yj-y;v v for(i=x+y;ix+2*y;i+)v v for(j=y;j2*y;j+)aij=ai-yj-y;v v vv本周课程结束，谢谢！
