5分治思想与递归(上)
我们可以下一个不太严谨的论断，枚举是算法思想的最本源，任何算法问题不是都可以认为是寻找解吗?对枚举进行精化和特化的回溯和分支限界思想，在操作上表现为对解空间的搜索；分治思想(Divide and Conquer)与后面要讨论的贪心、动态规划等等则可以认为是对解的构造。当然这其实也可以称之为启发式搜索，我们认为，分治策略的思想起源于对问题解的特性所做出的这样的观察和判断：原问题可以被划分成k个子问题，然后用一种方法将这些子问题的解合并，合并的结果就是原问题的解。既然我们知道了解可以以某种方式构造出来，就没有必要（使用枚举回溯）进行大批量的搜索了。枚举、回溯、分支限界利用了计算机工作的第一个特点：高速，不怕数据量大。分治和多种的各种算法思想利用了计算机工作的第二个特点：重复。
|
Divide_and_Conquer(P) { if(BasicCase(P)) return BasicDealing(P); else{ divide P into smaller instances P1,P2,…,Pk; for(int i=1;i<=k;i++) Yi= Divide_and_Conquer(Pi); return merge(P1,P2,…,Pk); } } |
分治思想可以做如下的形式化描述：对于一个给定的有n个输入的函数，分治思想建议将输入分为k个不同的子集，1＜k≤n，从而产生k个子问题。解决这些子问题，然后用一种方法将这些子问题的解合并得到元问题的解。如果子问题仍然相对较大，就使用同样的方法再次分解成更小的子问题。这种思维的轨迹是如此之简明和直接，以至于完全可以写成很直观的代码设计模式，如右图。
由分治方案产生的子问题经常与原问题属同一类型，这种思想的本身决定了其与递归策略天生的关联性。于是递归技术就成了理解分治算法思想和技术不得不提的东西。然而，递归这般强大而有趣的东西，其丰富的内涵又岂止分治一项？
分治策略的一个极端是每次Divide and Conquer之后，子问题只剩下一个，这时候也就不存在合并(Merge,Combine)问题了，比如二分查找，这种情况下分治策略有一个更贴近的名字：Drease and Conquer，在实际的算法设计中，要能设计Drease and Conquer，效果更好。
分治思想源远流长。根据Wikipedia[1]：
Binary search, a divide and conquer algorithm in which the original problem is successively broken down into single subproblems of roughly half the original size, has a long history. The idea of using a sorted list of items to fa cilitate searching dates back as far as Babylonia in 200BC,while a clear description of the algorithm on computers appeared in 1946 in an article by John Mauchly.Another divide and conquer algorithm with a single subproblem is the Euclidean algorithm to compute the greatest common divisor of two numbers (by reducing the numbers to smaller and smaller equivalent subproblems), which dates to several centuries BC.
原来，欧几里德算法也是分治的思想，不过欧几里德算法[2]中也没有所谓的“合并(Merge,Combine)”，这点和二分查找是一样的，所以上述模型也不是绝对的，模型是辅助的分析工具，但不是实践武器。
下面根据《算法导论》和王晓东《计算机算法设计与分析》对分治的论述，做一全面的总结：
Ø 分治法的基本思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，……而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题，1＜k≤n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
Ø 分治法的适用条件
分治法所能解决的问题一般具有以下几个特征：
l 该问题的规模缩小到一定的程度就可以容易地解决；
l 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
l 利用该问题分解出的子问题的解可以合并为该问题的解；
l 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
Ø 分治法的基本步骤
分治法在每一层递归上都有三个步骤：
l 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
l 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
l 合并：将各个子问题的解合并为原问题的解。
其实用一种轻松的语言去描述这种思想和策略或许更好。爱因斯坦说，“简单，尽可能简单，但不要太简单”，对于分治思想而言，既道出了分治的思想根源，也说明了分治要注意的东西。哲学的结论告诉我们，世界是复杂的，所以你拿到的问题往往不会是很简单的事情，哲学也告诉我们，复杂的事情总是简单的东西交错在一起或相互牵制或混淆你视听的，所以而再复杂再难的问题都可以分解成一些有限的简单问题的和，这就是分治法的原理。所以，一个很感性化、但又不一定不合理的结论就是：当问题很复杂很复杂，以至于枚举和回溯这样的方法都解不出来，或者说，实在无法接受时，想想分治；假设问题缩小一半后，再放大一倍，你发现了什么的时候，想想分治。我们在第6、7章讨论完贪心和动态规划之后，会说这样一句话：从算法的实际操作上看，分治更多表现为对问题本身的（拆分）分解，如n元数组分解为n/k个子数组，侧重于状态分解，本章前面一个切蛋糕的插图即是此意；贪心和动态规划则是对求解过程的分解，侧重于过程分步。分治更多要发现问题本身等分后得出的子问题具有最优子结构性，它们通过合并的方式得出解；贪心和动态规划则是对构造解的步骤进行分解后，每一步得出的部分解可以通过某种方式继续构造出整体解。
下面我们就先揭秘这个所谓的状态分解（问题拆分）和合并吧。
|
XY = (A×10n/2+B)×(C×10n/2+D) =AC×10n/2 + (AD+BC) × 10n/2+ BD ······(1) |
状态分解很经典也非常适合的例子就是大数乘法[3]。设X和Y都是n位的整数，现在要计算它们的乘积XY。如果利用小学所学的方法，将每两个一位数都进行相乘[4]，最后再相加，效率比较低下，乘法需要n2次。我们看看分治是否可行，只要看问题的条件能否满足分治必须的四个使用条件即可。分治法建议将X等分成两部分A和B，即X=A×10n/2+B，Y也同样处理，即Y=C×10n/2+D，那么：
进一步，AD和BC可以利用AC和BD来表示：
|
AD+BC=(A-B)×(D-C) + AC + BD ······ (2) |
这样(1)的乘法次数由4次减少到3次，最后的运算效率会有所提高。如果我们听过Donald Knuth所引用的Hoare的名言，“不成熟的优化是万恶之源”，但是又难以分辨究竟何种场合下的优化才是不成熟的优化时，此处从(1)到(2)优化算是一个很好的例子。
实际上，本例的结论可以推广开，而这个结论又是极有价值的。分治法在求解两个n位大整数u和v的乘积时，将其分割为n/m的m段，可以使用2m-1次n/m位整数的乘法求出uv的值。
设a=2n/m，则可以将u、v及其乘积w表示为：
且有w=w0+w1x+w2x2+…+w2m-2x2m-2