内蒙古大学《算法与数据结构》讲义14分而治之算法

下载第1 4章分而治之算法君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。本章将首先介绍怎样在算法设计领域应用这一古老的策略，然后将利用这一策略解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和一个计算几何问题找出二维空间中距离最近的两个点。本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排序问题的复杂性下限来证明分而治之算法对于求解这两种问题是最优的（因为算法的复杂性与下限一致） 。14.1 算法思想分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题；3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。例14-1 找出伪币 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币 3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。另外一种方法就是利用分而治之方法。假如把 1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择 8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个 8硬币的问题来解决。第二步，判断 A和B组中是否有伪币。可以利用仪器来比较 A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先 1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论 A组还是B组中有伪币，都可以推断这 1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有 4个硬币。称其中一组为 B1，另一组为B2。比较这两组，肯定有一组轻一些。如果 B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为 B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。例14-2 金块问题 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。假设袋中有n 个金块。可以用函数M a x（程序1 - 3 1）通过n-1次比较找到最重的金块 。找到最重的金块后，可以从余下的 n-1个金块中用类似的方法通过 n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。程序2 - 2 6和2 - 2 7是另外两种方法，前者需要进行2n-2次比较，后者最多需要进行2n-2次比较。下面用分而治之方法对这个问题进行求解。当 n很小时，比如说，n2，识别出最重和最轻的金块，一次比较就足够了。当n 较大时（n2） ，第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在 A和B中最重和最轻的金块。设 A中最重和最轻的金块分别为 HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若 n2，则递归地应用分而治之方法。假设n= 8。这个袋子被平分为各有4个金块的两个袋子A和B。为了在A中找出最重和最轻的金块，A中的4个金块被分成两组A1和A2。每一组有两个金块，可以用一次比较在A中找出较重的金块HA1和较轻的金块LA1。经过另外一次比较，又能找出 HA2和LA2。现在通过比较HA1和HA2，能找出HA；通过LA 1和LA2的比较找出LA。这样，通过4次比较可以找到HA 和LA。同样需要另外4次比较来确定HB 和LB。通过比较HA 和HB（LA 和LB） ，就能找出所有金块中最重和最轻的。因此，当n= 8时，这种分而治之的方法需要 1 0次比较。如果使用程序1 - 3 1，则需要1 3次比较。如果使用程序2 - 2 6和2 - 2 7，则最多需要1 4次比较。设c(n)为使用分而治之方法所需要的比较次数。为了简便，假设n是2的幂。当 n= 2时，c(n) = 1。对于较大的 n，c(n) = 2c(n/ 2 ) + 2。当n是2的幂时，使用迭代方法（见例 2 - 2 0）可知c(n) = 3n/ 2 - 2。在本例中，使用分而治之方法比逐个比较的方法少用了2 5的比较次数。例14-3 矩阵乘法 两个nn 阶的矩阵A与B的乘积是另一个nn 阶矩阵C，C可表示为假如每一个C(i, j) 都用此公式计算，则计算C所需要的操作次数为n3 m+n2(n- 1)a，其中m表示一次乘法，a 表示一次加法或减法。为了得到两个矩阵相乘的分而治之算法，需要：1) 定义一个小问题，并指明小问题是如何进行乘法运算的；2) 确定如何把一个大的问题划分成较小的问题，并指明如何对这些较小的问题进行乘法运算；3) 最后指出如何根据小问题的结果得到大问题的结果。为了使讨论简便，假设n 是2的幂（也就是说，n是1，2，4，8，1 6，） 。首先，假设n= 1时是一个小问题，n 1时为一个大问题。后面将根据需要随时修改这个假设。对于11阶的小矩阵，可以通过将两矩阵中的两个元素直接相乘而得到结果。考察一个n 1的大问题。可以将这样的矩阵分成4个n/ 2n/ 2阶的矩阵A1，A2，A3，和A4，如第1 4章分而治之算法4 3 5下载（1 4 - 1）图14-1a 所示。当n 大于1且n 是2的幂时，n/ 2也是2的幂。因此较小矩阵也满足前面对矩阵大小的假设。矩阵Bi和Ci的定义与此类似，1i4。矩阵乘积的结果见图1 4 - 1 b。图14-1 把一个矩阵划分成几个小矩阵a) 把A分为4个小矩阵b) A*BC可以利用公式（1 4 - 1）来证明以下公式：（1 4 - 2）（1 4 - 3）（1 4 - 4）（1 4 - 5）根据上述公式，经过8次n/ 2n/ 2阶矩阵乘法和4次n/ 2n/ 2阶矩阵的加法，就可以计算出A与B的乘积。因此，这些公式能帮助我们实现分而治之算法。在算法的第二步，将递归使用分而治之算法把8个小矩阵再细分（见程序2 - 1 9） 。算法的复杂性为(n3 )，此复杂性与程序2 - 2 4直接使用公式（1 4 - 1）所得到的复杂性是一样的。事实上，由于矩阵分割和再组合所花费的额外开销，使用分而治之算法得出结果的时间将比用程序 2 - 2 4还要长。为了得到更快的算法，需要简化矩阵分割和再组合这两个步骤。一种方案是使用 S t r a s s e n方法得到7个小矩阵。这7个小矩阵为矩阵D, E, , J，它们分别定义为：矩阵D到J可以通过7次矩阵乘法，6次矩阵加法，和4次矩阵减法计算得出。前述的 4个小矩阵可以由矩阵D到J通过6次矩阵加法和两次矩阵减法得出，方法如下：用上述方案来解决n= 2的矩阵乘法。将某矩阵A和B相乘得结果C，如下所示：4 3 6第三部分算法设计方法a)b)下载因为n 1，所以将A、B两矩阵分别划分为4个小矩阵，如图14-1a 所示。每个矩阵为11阶，仅包含一个元素。 11阶矩阵的乘法为小问题，因此可以直接进行运算。利用计算 DJ的公式，得：D= 1（6-8）=-2E= 4（7-5）= 8F=（3 + 4）5 = 3 5G=（1 + 2）8 = 2 4H=（3-1） （5 + 6）= 2 2I=（2-4） （7 + 8）=-3 0J=（1 + 4） （5 + 8）= 6 5根据以上结果可得：对于上面这个22的例子，使用分而治之算法需要7次乘法和1 8次加/减法运算。而直接使用公式（1 4 - 1） ，则需要8次乘法和7次加/减法。要想使分而治之算法更快一些，则一次乘法所花费的时间必须比11次加/减法的时间要长。假定S t r a s s e n矩阵分割方案仅用于n8的矩阵乘法，而对于n8的矩阵乘法则直接利用公式（1 4 - 1）进行计算。则n= 8时，88矩阵相乘需要7次44矩阵乘法和1 8次44矩阵加/减法。每次矩阵乘法需花费6 4m+ 4 8a次操作，每次矩阵加法或减法需花费 1 6a次操作。因此总的操作次数为7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4 8m+ 6 2 4a。而使用直接计算方法，则需要5 1 2m+ 4 4 8a次操作。要使S t r a s s e n方法比直接计算方法快，至少要求5 1 2-4 4 8次乘法的开销比6 2 4-4 4 8次加/减法的开销大。或者说一次乘法的开销应该大于近似2 . 7 5次加/减法的开销。假定n1 6的矩阵是一个“小”问题，S t r a s s e n的分解方案仅仅用于n1 6的情况，对于n1 6的矩阵相乘，直接利用公式（ 1 4 - 1） 。则当n= 1 6时使用分而治之算法需要 7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m+ 4 2 8 8a次操作。直接计算时需要4 0 9 6m+ 3 8 4 0a次操作。若一次乘法的开销与一次加/减法的开销相同，则S t r a s s e n方法需要7 8 7 2次操作及用于问题分解的额外时间，而直接计算方法则需要7 9 3 6次操作加上程序中执行 f o r循环以及其他语句所花费的时间。即使直接计算方法所需要的操作次数比 St r a s s e n方法少，但由于直接计算方法需要更多的额外开销，因此它也不见得会比S t r a s s e n方法快。n 的值越大，Strassen 方法与直接计算方法所用的操作次数的差异就越大，因此对于足够大的n，Strassen 方法将更快。设t(n) 表示使用Strassen 分而治之方法所需的时间。因为大的矩阵会被递归地分割成小矩阵直到每个矩阵的大小小于或等于 k（k至少为8，也许更大，具体值由计算机的性能决定） ，t 的递归表达式如下：这里c n2表示完成1 8次n/2n/2阶矩阵加/减法以及把大小为n 的矩阵分割成小矩阵所需要第1 4章分而治之算法4 3 7下载（1 4 - 6）的时间。用迭代方法计算，可得t(n) =(nl og27)。因为l og272 . 8 1，所以与直接计算方法的复杂性(n3 )相比，分而治之矩阵乘法算法有较大的改进。注意事项分而治之方法很自然地导致了递归算法的使用。在许多例子里，这些递归算法在递归程序中得到了很好的运用。实际上，在许多情况下，所有为了得到一个非递归程序的企图都会导致采用一个模拟递归栈。不过在有些情况