常用算法——分治法

1、分治法的基本思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序 问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直 接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题（1 2、分治法的适用条件
分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可 以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第 三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问 题，此时虽然可用分治法，但一般用动态规划法较好。
3、分治法的基本步骤
分治法在每一层递归上都有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide_and_Conquer（P）
if |P|≤n0
then return（ADHOC（P））
将P分解为较小的子问题P1、P2、…、Pk
for i←1 to k
do
yi ← Divide-and-Conquer（Pi）        △ 递归解决Pi
T ← MERGE（y1，y2，…，yk）          △ 合并子问题
Return（T）
其中 |P| 表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC（P）是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC（P）求解。
算法MERGE（y1，y2，…，yk）是该分治法中的合并子算法，用于将P的子问题P1、P2、…、Pk的相应的解y1、y2、…、yk合并为P的解。
根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现， 在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种 使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。
【问题】    大整数乘法
问题描述：
通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而，在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围 内进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位 数上的数字，就必须用软件的方法来实现大整数的算术运算。
请设计一个有效的算法，可以进行两个n位大整数的乘法运算。
设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较 低。如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算 法。

图6-3 大整数X和Y的分段
我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位（为简单起见，假设n是2的幂），如图6-3所示。
由此，X=A2n/2+B，Y=C2n/2+D。这样，X和Y的乘积为：
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD    （1）
如果按式（1）计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法（分别对应于式（1）中的加 号），此外还要做2次移位（分别对应于式（1）中乘2n和乘2n/2）。所有这些加法和移位共用O（n）步运算。设T（n）是2个n位整数相乘所需的运算 总数，则由式（1），我们有：
             （2）
由此可得T（n）=O（n2）。因此，用（1）式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式：
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD        （3）
虽然，式（3）看起来比式（1）复杂些，但它仅需做3次n/2位整数的乘法（AC，BD和（A-B）（D-C）），6次加、减法和2次移位。由此可得：
               （4）
用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式（3），并考虑到X和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下：
function MULT(X，Y，n); {X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}
begin
S=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}
X=ABS(X);
Y=ABS(Y); {X和Y分别取绝对值}
if n=1 then
if (X=1)and(Y=1) then return(S)
else return(0)
else begin
A=X的左边n/2位;
B=X的右边n/2位;
C=Y的左边n/2位;
D=Y的右边n/2位;
ml=MULT(A,C,n/2);
m2=MULT(A-B,D-C,n/2);
m3=MULT(B,D,n/2);
S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;
上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。
【问题】    最接近点对问题
问题描述：
在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通 控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问 题之一。下面我们着重考虑平面上的最接近点对问题。
最接近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。
严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。
这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n2)的计算时间。我们能否找到问题的一个O (nlogn)算法。
这个问题显然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个 子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因 为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在 S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。因此， 依此思路，合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足：
T(n)=2T(n/2)+O(n2)
它的解为T(n)=O(n2)，即与合并步骤的耗时同阶，显示不出比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。
为了使问题易于理解和分析，我们先来考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x1、x2、…、xn。最接近点对即为这n个实数中相差最小 的2个实数。我们显然可以先将x1、x2、…、xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，因此如在排序算 法中所证明的，耗时为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广 到二维的情形。
假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S | x≤m}；S2={x∈S | x>m}。这样一来，对于所有p∈S1和q∈S2有p 递归地在S1和S2上找出其最接近点对{p1，p2}和{q1，q2}，并设δ=min{|p1-p2|，|q1-q2|}，S中的最接近点对或者是{p1，p2}，或者是{q1，q2}，或者是某个{p3，q3}，其中p3∈S1且q3∈S2。如图1所示。

图1 一维情形的分治法
我们注意到，如果S的最接近点对是{p3，q3}，即 | p3-q3 | < δ，则p3和q3两者与m的距离不超过δ，即 | p3-m | < δ，| q3-m | < δ，也就是说，p3∈(m-δ，m)，q3∈(m，m+δ)。由于在S1中，每个长度为δ的半闭区间至多包含一个点（否则必有两点距离小于δ），并且m是 S1和S2的分割点，因此(m-δ，m)中至多包含S中的一个点。同理，(m，m+δ)中也至多包含S中的一个点。由图1可以看出，如果(m-δ，m)中 有S中的点，则此点就是S1中最大点。同理，如果(m，m+δ)中有S中的点，则此点就是S2中最小点。因此，我们用线性时间就能找到区间(m-δ，m) 和(m，m+δ)中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。也就是说，按这种分治策略，合并步可在O(n) 时间内完成。这样是否就可以得到一个有效的算法了呢？
还有一个问题需要认真考虑，即分割点m的选取，及S1和S2的划分。选取分割点m的一个基本要求是由此导出集合S的一个线性分割，即S=S1∪S2 ，S1∩S2=Φ，且S1 {x | x≤m}；S2 {x | x>m}。容易看出，如果选取m=[max（S）+min（S）]/2，可以满足线性分割的要求。选取分割点后，再用O(n)时间即可将S划分成 S1={x∈S | x≤m}和S2={x∈S | x>m}。然而，这样选取分割点m，有可能造成划分出的子集S1和S2的不平衡。例如在最坏情况下，|S1|=1，|S2|=n-1，由此产生的分 治法在最坏情况下所需的计算时间T（n）应满足递归方程：
T（n）=T（n-1）+O（n）
它的解是T（n）=O（n2）。这种效率降低的现象可以通过分治法中“平衡子问题”的方法加以解决。也就是说，我们可以通过适当选择分割点m，使S1和 S2中有大致相等个数的点。自然地，我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O（n） 时间内确定一个平衡的分割点m。
至此，我们可以设计出一个求一维点集S中最接近点对的距离的算法pair如下。
Float pair（S）;
{    if | S | =2    δ= | x[2]－x[1] |      /*x[1..n]存放的是S中n个点的坐标*/
else
{    if ( | S | =1)    δ=∞
     else
{    m=S中各点的坐标值的中位数;
       构造S1和S2，使S1={x∈S | x≤m}，S2={x∈S | x＞m};
δ1=pair(S1);
         δ2=pair(S2);
         p=max(S1);
         q=min(S2);
         δ=min(δ1，δ2，q-p);
}
return(δ);
}
由以上的分析可知，该算法的分割步骤和合并步骤总共耗时O(n)。因此，算法耗费的计算时间T(n)满足递归方程：

解此递归方程可得T(n)=O(nlogn)。

【问题】循环赛日程表
问题描述：设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能参赛一次；
（3）循环赛在n-1天内结束。
请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。
按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。

                           1    2    3    4    5    6    7
                         1    2    3    4    5    6    7    8
                         2    1    4    3    6    7    8    5
                         3    4    1    2    7    8    5    6
             1    2    3          4    3    2    1    8    5    6    7
           1    2    3    4          5    6    7    8    1    4    3    2
   1          2    1    4    3          6    5    8    7    2    1    4    3
1    2          3    4    1    2          7    8    5    6    3    2    1    4
2    1          4    3    2    1          8    7    6    5    4    3    2    1
（1）            （2）                    （3）
图1 2个、4个和8个选手的比赛日程表
图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角 小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在 后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。