Algorithm 版 (精华区)

发信人: Lerry (第一次有失恋的感觉), 信区: Algorithm
标  题: 分治法的基本步骤
发信站: 哈工大紫丁香 (2002年03月12日11:03:53 星期二), 站内信件

分治法的基本步骤
分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide-and-Conquer(P)
1.  if |P|≤n0
2.    then return(ADHOC(P))
3.  将P分解为较小的子问题 P1 ,P2 ,...,Pk
4.  for i←1 to k
5.    do yi ← Divide-and-Conquer(Pi)    △ 递归解决Pi
6.  T ← MERGE(y1,y2,...,yk)             △ 合并子问题
7.  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。这种使子问题规模大致相等
的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法
要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，如下面的例1，例
2；有些问题合并方法比较复杂，或者是有多种合并方案，如例3，例4；或者是合并方案
不明显，如例5。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]