算法-分治法ppt课件.ppt

1、2022-5-26分治法第第4章章 分治法分治法 4.1 概概 述述 4.2 排序问题中的分治法排序问题中的分治法4.3 组合问题中的分治法组合问题中的分治法4.4 几何问题中的分治法几何问题中的分治法 分治法是最著名的算法设计技术。分治法是最著名的算法设计技术。1/562022-5-26分治法4.1 概概 述述 4.1.1 分治法的设计思想分治法的设计思想 4.1.2 数字旋转方阵数字旋转方阵2/562022-5-26分治法 将一个难以直接解决的大问题，划分成一些规模将一个难以直接解决的大问题，划分成一些规模较小的子问题，分别求解各个子问题，再合并子问较小的子问题，分别求解各个子问题，再合并

2、子问题的解得到原问题的解。题的解得到原问题的解。4.1.1 分治法的设计思想分治法的设计思想 如果子问题的规模仍然不够小，可继续分解下去。如果子问题的规模仍然不够小，可继续分解下去。 3/562022-5-26分治法分治法的求解过程：分分治法的求解过程：分-治治-合合 （1 1）划分划分：把规模为：把规模为n n的原问题划分为的原问题划分为k k个规模较个规模较小的子问题，并尽量使这小的子问题，并尽量使这k k个子问题的规模大致相同。个子问题的规模大致相同。 （2 2）求解子问题求解子问题：各子问题的解法与原问题的解：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题。法

3、通常是相同的，可以用递归的方法求解各个子问题。 （3 3）合并合并：把各个子问题的解合并起来，分治算：把各个子问题的解合并起来，分治算法的有效性很大程度上依赖于合并的实现。法的有效性很大程度上依赖于合并的实现。4/562022-5-26分治法2. 独立子问题独立子问题：各子问题之间相互独立。：各子问题之间相互独立。1. 平衡子问题平衡子问题：最好使子问题的规模大：最好使子问题的规模大致相同。致相同。启发式规则：启发式规则：5/562022-5-26分治法 子问题子问题1的规模是的规模是n/2 子问题子问题1的解的解 子问题子问题2的解的解 子问题子问题2的规模是的规模是n/2 原问题的解原问题

4、的解 原问题原问题的规模是的规模是n分治法的典型情况分治法的典型情况6/562022-5-26分治法例：计算例：计算an，应用分治技术得到如下计算方法：，应用分治技术得到如下计算方法： 34 32 32 81 31 31 9 31 31 9 3 3 3 3分解问题分解问题求解每个子问题求解每个子问题合并子问题的解合并子问题的解v 不是所有的分治法都比简单的蛮力法更有效。不是所有的分治法都比简单的蛮力法更有效。分析时间性能 = = =1122naanaannn如果如果如果如果7/562022-5-26分治法4.1.2 数字旋转方阵数字旋转方阵问题：问题：输出输出N N(1 N 10)数字旋转方阵

5、。数字旋转方阵。120 19 18 17 16221 32 31 30 15322 33 36 29 14423 34 35 28 13524 25 26 27 1267 8 9 10 116 6的旋转方阵的旋转方阵8/562022-5-26分治法4.2 排序问题中的分治法排序问题中的分治法4.2.1 4.2.1 归并排序归并排序4.2.2 4.2.2 快速排序快速排序92022-5-26分治法4.3.1 归并排序归并排序 二路归并排序的分治策略是：二路归并排序的分治策略是：（1）划分划分：将待排序序列：将待排序序列r1, r2, , rn划分为两个划分为两个长度相等的子序列长度相等的子序列r

6、1, , rn/2和和rn/21, , rn；（2）求解子问题求解子问题：分别对这两个子序列进行排：分别对这两个子序列进行排序，得到两个有序子序列；序，得到两个有序子序列；（3）合并合并：将这两个有序子序列合并成一个有：将这两个有序子序列合并成一个有序序列。序序列。10/562022-5-26分治法 r1 rn/2 rn/21 rn 划分划分r1 rn/2 rn/21 rn 递归处理递归处理r1rn/2rn/21 r n 合并解合并解 举例：举例：8 3 2 6 7 1 5 4 11/562022-5-26分治法 算法算法4.3归并排序归并排序 void MergeSort( (int r ,

7、 int s, int t) ) int m, r11000; if ( (s= =t) ) return; else m=( (s+t) )/2; Mergesort( (r, s, m) ); /归并排序前半个子序列归并排序前半个子序列 Mergesort( (r, m+1, t) ); /归并排序后半个子序列归并排序后半个子序列 Merge( (r, r1, s, m, t) ); /合并两个已排序的子序列合并两个已排序的子序列 for (int i=s; i+=1)2(211)(nnnTnnT13/562022-5-26分治法算法算法4.4合并有序子序列合并有序子序列 void Mer

8、ge( (int r , int r1 , int s, int m, int t) ) i=s; j=m+1; k=s; while ( (i=m & j=t) ) if ( (ri=rj) ) r1k+=ri+; /取取ri和和rj中较小者放入中较小者放入r1k else r1k+=rj+; if ( (i=m) ) while ( (i=m) ) /若第一个子序列没处理完，则进行收尾处理若第一个子序列没处理完，则进行收尾处理 r1k+=ri+; else while ( (j=t) ) /若第二个子序列没处理完，则进行收尾处理若第二个子序列没处理完，则进行收尾处理 r1k+=rj+; 1

9、4/562022-5-26分治法4.3.2 快速排序快速排序 （2）求解子问题求解子问题：分别对划分后的每一个子序列：分别对划分后的每一个子序列递归处理；递归处理；（3）合并合并：由于对子序列：由于对子序列r1 ri-1和和ri+1 rn的排序的排序是就地进行的，所以合并不需要执行任何操作。是就地进行的，所以合并不需要执行任何操作。快速排序的分治策略是：快速排序的分治策略是：（1）划分划分：选定一个记录作为轴值，以轴值为基准：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列；将整个序列划分为两个子序列；15/562022-5-26分治法 r1 ri- -1 ri ri+1 rn 均

10、均ri 轴值轴值 均均ri 位于最终位置位于最终位置 v归并排序按照记录在序列中的位置对序列进行划分，归并排序按照记录在序列中的位置对序列进行划分，v快速排序按照记录的值对序列进行划分。快速排序按照记录的值对序列进行划分。16/562022-5-26分治法以第一个记录作为轴值，对待排序序列进行划分的过程为：以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初始化初始化：取第一个记录作为基准，设置两个参数：取第一个记录作为基准，设置两个参数i，j；（2 2）右侧扫描过程右侧扫描过程：（3 3）左侧扫描过程左侧扫描过程：（4 4）重复重复（2 2）（）（3 3）步，直到）步，直到i i与与

11、j j指向同一位置，即基准记指向同一位置，即基准记录最终的位置。录最终的位置。172022-5-26分治法jijjjiiiijjj一次划分示例一次划分示例182022-5-26分治法算法算法4.5一次划分一次划分 int Partition( (int r , int first, int end) ) i=first; j=end; /初始化初始化 while ( (ij) ) while ( (ij & ri= rj) ) j-； /右侧扫描右侧扫描 if ( (ij) ) rirj; /将较小记录交换到前面将较小记录交换到前面 i+; while ( (ij & ri= rj) ) i+

12、； /左侧扫描左侧扫描 if ( (ij) ) rjri; /将较大记录交换到后面将较大记录交换到后面 j-; retutn i; / i为轴值记录的最终位置为轴值记录的最终位置 192022-5-26分治法 以轴值为基准将待排序序列划分为两个子序以轴值为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行排序。列后，对每一个子序列分别递归进行排序。jiij202022-5-26分治法算法算法4.6快速排序快速排序 void QuickSort( (int r , int first, int end) ) if ( (first0) sum=aleft; else sum=0; e

13、lse center=(left+right)/2; /划分划分 leftsum=MaxSum(a, left, center); /对应情况，递归求解对应情况，递归求解 rightsum=MaxSum(a, center+1, right); /对应情况，递归求解对应情况，递归求解302022-5-26分治法 s1=0; lefts=0; /以下对应情况，先求解以下对应情况，先求解s1 for (i=center; i=left; i-) lefts+=ai; if (leftss1) s1=lefts; s2=0; rights=0; /再求解再求解s2 for (j=center+1;

14、js2) s2=rights; sum=s1+s2; /计算情况的最大子段和计算情况的最大子段和 if (sumleftsum) sum=leftsum; /合并，在合并，在sum、leftsum和和rightsum中取较大者中取较大者 if (sum+=1)2(211)(nnnTnnT 从而可得算法从而可得算法4.74.7的时间复杂性为的时间复杂性为O(nlogO(nlog2 2n)n)。322022-5-26分治法4.3.2 棋盘覆盖问题棋盘覆盖问题 在一个在一个2k2k （k0）个方格组成的棋盘中，）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为恰有一个方格与其他方格不同，称

15、该方格为特殊特殊方格方格。棋盘覆盖问题棋盘覆盖问题要求用图（要求用图（b）所示的）所示的4种不种不同形状的同形状的L型骨牌覆盖给定棋盘上除特殊方格以型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何外的所有方格，且任何2个个L型骨牌不得重叠覆盖。型骨牌不得重叠覆盖。(a) k=2时的一种棋盘时的一种棋盘 (b) 4种不同形状的种不同形状的L型骨牌型骨牌332022-5-26分治法 分治法求解棋盘覆盖问题的技巧在于划分棋盘，使划分治法求解棋盘覆盖问题的技巧在于划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分

16、解为规模较小的棋盘覆盖问题。殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。 k0 k0时，可将时，可将2k2k2k2k的棋盘划分为的棋盘划分为4 4个个2k-12k-12k-12k-1的子的子棋盘，这样划分后，由于原棋盘只有一个特殊方格，所以，棋盘，这样划分后，由于原棋盘只有一个特殊方格，所以，这这4 4个子棋盘中只有一个子棋盘包含该特殊方格，其余个子棋盘中只有一个子棋盘包含该特殊方格，其余3 3个个子棋盘中没有特殊方格。子棋盘中没有特殊方格。 为了将这为了将这3 3个没有特殊方格的子棋盘转化为特殊棋盘，个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个以便采用递归方法

17、求解，可以用一个L L型骨牌覆盖这型骨牌覆盖这3 3个较小个较小棋盘的会合处，从而将原问题转化为棋盘的会合处，从而将原问题转化为4 4个较小规模的棋盘覆个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为盖问题。递归地使用这种划分策略，直至将棋盘分割为1 11 1的子棋盘。的子棋盘。342022-5-26分治法2k-12k-12k-12k-12k-12k-12k-12k-1(a)棋盘分割棋盘分割 (b) 构造相同子问题构造相同子问题35/562022-5-26分治法 设设T( (k) )是覆盖一个是覆盖一个2k2k棋盘所需时间，从算棋盘所需时间，从算法的划分策略可知，法的划分策略

18、可知，T( (k) )满足如下递推式：满足如下递推式： =+=00) 1 () 1(4) 1 ()(kkOkTOkT 解此递推式可得解此递推式可得T( (k) )=O( (4k) )。由于覆盖一个。由于覆盖一个2k2k棋盘所需的骨牌个数为棋盘所需的骨牌个数为(4k- -1)/ /3，所以，算，所以，算法法4.8是一个在渐进意义下的最优算法。是一个在渐进意义下的最优算法。 362022-5-26分治法补充：补充： 循环赛日程安排问题循环赛日程安排问题 设有设有n=2k个选手要进行网球循环赛，要求设个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：计一个满足以下要求的比赛日程表：（1）

19、每个选手必须与其他）每个选手必须与其他n- -1个选手各赛一次；个选手各赛一次；（2）每个选手一天只能赛一次。）每个选手一天只能赛一次。 按此要求，可将比赛日程表设计成一个按此要求，可将比赛日程表设计成一个 n n 行行n n-1-1列的二维表，其中，第列的二维表，其中，第 i i 行第行第 j j 列表示和第列表示和第 i i 个选手在第个选手在第 j j 天比赛的选手。天比赛的选手。37/562022-5-26分治法n按照分治的策略，可将所有参赛的选手分为两按照分治的策略，可将所有参赛的选手分为两部分，部分，n2k个选手的比赛日程表就可以通过个选手的比赛日程表就可以通过为为n/22k-1个

20、选手设计的比赛日程表来决定。个选手设计的比赛日程表来决定。n 递归地执行这种分割，直到只剩下递归地执行这种分割，直到只剩下2个选手时，个选手时，比赛日程表的制定就变得很简单：只要让这比赛日程表的制定就变得很简单：只要让这2个选手进行比赛就可以了。个选手进行比赛就可以了。38/562022-5-26分治法 显然，这个求解过程是自底向上的迭代过程。显然，这个求解过程是自底向上的迭代过程。具有多个选手的情况可以依此类推。具有多个选手的情况可以依此类推。 (b) 2k(k=2)个选手比赛个选手比赛 (c) 2k(k=3)个选手比赛个选手比赛加加4加加2(a) 2k(k=1)个选手比赛个选手比赛1221

21、1 22 13 44 33 44 31 22 11 2 3 42 1 4 33 4 1 24 3 2 15 6 7 86 5 8 77 8 5 68 7 6 55 6 7 86 5 8 77 8 5 68 7 6 51 2 3 42 1 4 33 4 1 24 3 2 1392022-5-26分治法4.4 几何问题中的分治法几何问题中的分治法4.4.1 最近对问题最近对问题 4.4.2 凸包问题（略）凸包问题（略）402022-5-26分治法4.4.1 最近对问题最近对问题 设设p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面是平面上上n个点构成的集合个点构

22、成的集合S，最近对问题就是找出集合，最近对问题就是找出集合S中距离最近的点对。中距离最近的点对。 蛮力法求解时间性能为蛮力法求解时间性能为O(n2)。一维情况下排。一维情况下排序后求解，效率可提高到序后求解，效率可提高到O(nlogn)。二维情况？。二维情况？ 最接近点对可能多于一对。为简单起见，只找最接近点对可能多于一对。为简单起见，只找出其中的一对作为问题的解。出其中的一对作为问题的解。41/562022-5-26分治法划分：划分： 将集合将集合S分成两个子集分成两个子集 S1和和 S2，每个子集，每个子集中有中有n/2个点。个点。 在每个子集中递归地求其最接近的点对，在求在每个子集中递归

23、地求其最接近的点对，在求出每个子集的最接近点对后，在合并步分两种情况，出每个子集的最接近点对后，在合并步分两种情况，1 集合集合 S 中最接近的两个点都在子集中最接近的两个点都在子集 S1或或 S2中，中，则问题很容易解决，则问题很容易解决，2 这两个点分别在这两个点分别在 S1和和 S2中，中，问题比较复杂。问题比较复杂。42/562022-5-26分治法求解子问题：求解子问题：先考虑先考虑一维一维的情形。的情形。 S中的点退化为中的点退化为x轴上的轴上的n个点个点x1, x2, , xn。用用x轴上的某个点轴上的某个点m将将S划分为两个集合划分为两个集合S1和和S2，并且，并且S1和和S2

24、含有点的个数相同。含有点的个数相同。432022-5-26分治法S1S2p2p1p3q3q1q2m 递归地在递归地在S1和和S2上求出最接近点对上求出最接近点对 (p1, p2) 和和(q1, q2)，如果集合，如果集合S中的最接近点对都在子集中的最接近点对都在子集S1或或S2中，中，则则d=min(p1, p2), (q1, q2)即为所求即为所求如果集合如果集合S中的最接近点对分别在中的最接近点对分别在S1和和S2中，则一中，则一定是定是(p3, q3)，其中，其中，p3是子集是子集S1中的最大值，中的最大值，q3是是子集子集S2中的最小值。中的最小值。 442022-5-26分治法 按这

25、种分治策略求解最近对问题的算法效率按这种分治策略求解最近对问题的算法效率取决于划分点取决于划分点m的选取，一个基本的要求是要遵的选取，一个基本的要求是要遵循平衡子问题的原则。循平衡子问题的原则。 如果选取如果选取m=(maxS+minS)/2，则有可能因，则有可能因集合集合S中点分布的不均匀而造成子集中点分布的不均匀而造成子集S1和和S2的不平的不平衡，如果用衡，如果用S中各点坐标的中位数（即中各点坐标的中位数（即S的中值）的中值）作为分割点，则会得到一个平衡的分割点作为分割点，则会得到一个平衡的分割点m，使，使得子集得子集S1和和S2中有个数大致相同的点。中有个数大致相同的点。45/5620

26、22-5-26分治法下面考虑下面考虑二维二维的情形，此时的情形，此时S中的点为平面上的点。中的点为平面上的点。 选取垂直线选取垂直线x=m来作为分割线，其中，来作为分割线，其中，m为为S中各点中各点x坐标的中位数。由此将坐标的中位数。由此将S分割为两个子集分割为两个子集S1=pS | xpm和和S2=qS | xqm。此时，。此时，S1和和S2包含点包含点的个数大致相同。的个数大致相同。462022-5-26分治法 递归地在递归地在S1和和S2上求解最近对问题，分别得到上求解最近对问题，分别得到S1中的最近距离中的最近距离d1和和S2中的最近距离中的最近距离d2，令，令d=min(d1, d2

27、)，若，若S的最近对的最近对(p, q)之间的距离小于之间的距离小于d，则则p和和q必分属于必分属于S1和和S2。 不妨设不妨设pS1，qS2，则，则p和和q距直线距直线x=m的距的距离均小于离均小于d，所以，可以将求解限制在以，所以，可以将求解限制在以x=m为中为中心、宽度为心、宽度为2d的垂直带的垂直带P1和和P2中，垂直带之外的任中，垂直带之外的任何点对之间的距离都一定大于何点对之间的距离都一定大于d。 472022-5-26分治法x=mddd2d1S1S2pq 最近对问题的分治思想最近对问题的分治思想P1P2S1=pS | xpmS2=qS | xqm482022-5-26分治法x=m

28、ddp(a) 包含点包含点q的的d2d的矩形区域的矩形区域 (b) 最坏情况下需要检查的最坏情况下需要检查的6个点个点P1P22dx=mddpP1P22d 对于点对于点pP1，需要考察，需要考察P2中的各个点和点中的各个点和点p之间的距之间的距离是否小于离是否小于d，显然，显然，P2中这样点的中这样点的y轴坐标一定位于区间轴坐标一定位于区间y- -d, y+d之间，而且，这样的点不会超过之间，而且，这样的点不会超过6个。个。 492022-5-26分治法 应用分治法求解含有应用分治法求解含有n个点的最近对问题，个点的最近对问题，其时间复杂性可由下面的递推式表示：其时间复杂性可由下面的递推式表示

29、： )()2(2)(nfnTnT+= 分解合并子问题的解的时间分解合并子问题的解的时间f( (n) )O( (n) )，从而可得从而可得T(n)=O(nlog2n)。50/562022-5-26分治法阅读材料阅读材料 递归函数的执行过程递归函数的执行过程 递归的定义递归的定义 递归函数的运行轨迹递归函数的运行轨迹递归函数的内部执行过程递归函数的内部执行过程51/562022-5-26分治法递归的定义递归的定义 递归（递归（RecursionRecursion）就是子程序（或函数）直）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，接调用自己或通过一系列调用语句间接调用自己，是

30、一种描述问题和解决问题的基本方法。是一种描述问题和解决问题的基本方法。 递归的两个基本要素：递归的两个基本要素： 边界条件边界条件：确定递归到何时终止；：确定递归到何时终止； 递归模式递归模式：大问题是如何分解为小问题的。：大问题是如何分解为小问题的。 递归通常用来解决结构自相似的问题。递归通常用来解决结构自相似的问题。52/562022-5-26分治法递归函数的运行轨迹递归函数的运行轨迹 在递归函数中，调用函数和被调用函数是同一在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第把调用递归

31、函数的主函数称为第0 0层，进入函数后，层，进入函数后，首次递归调用自身称为第首次递归调用自身称为第1层调用；从第层调用；从第i层递归调层递归调用自身称为第用自身称为第i+1层。层。 反之，退出第反之，退出第i+1i+1层调用应该返回第层调用应该返回第i i层。采用层。采用图示方法描述递归函数的运行轨迹，从中可较直观图示方法描述递归函数的运行轨迹，从中可较直观地了解到各调用层次及其执行情况。地了解到各调用层次及其执行情况。53/562022-5-26分治法Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move (A,C)Move (A,B)Hanio(1,

32、C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move (C,B)Hanio(1,C,A,B)Move (A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move (B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move (A,C)Hanio(2,B,A,C)Move (B,A)Hanio(1,A,B,C)结束结束 542022-5-26分治法 递归函数的内部执行过程p一个递归函数的调用过程类似于多个函数的一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是嵌套调用，只不过调用函数和被调用函数是同一个函数。同一个函

33、数。p为了保证递归函数的正确执行，系统需设立为了保证递归函数的正确执行，系统需设立一个工作栈。一个工作栈。552022-5-26分治法 u递归算法递归算法结构清晰，可读性强结构清晰，可读性强，而且容易用数，而且容易用数学归纳法来证明算法的正确性，因此，它为设学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。中的一种强有力的工具。u递归算法是一种自身调用自身的算法，随着递递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的归调用时的辅助操作增多，因此，递归算法的运行效率较低运行效率较低。递归算法的特点递归算法的特点56