分治算法——从概念到实例.doc

分治算法——从概念到实例 分治算法是一种常用的算法设计策略，它将一个难以直接解决的大问题分割成一些规模较小的相同问题，以便各个击破，分而治之。这种算法设计策略的基本思想是，将一个规模为 n 的问题，若该问题可以容易地解决（比如说规模 n 较小）则直接解决，否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 分治法的适用条件包括： 1. 该问题的规模缩小到一定的程度就可以容易地解决； 2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 3. 利用该问题分解出的子问题的解可以合并为该问题的解； 4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 分治法的基本步骤包括： 1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； 2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 3. 合并：将各个子问题的解合并为原问题的解。 分治法的一般的算法设计模式如下： 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 的解。 在使用分治法时，需要注意的问题包括： * 如何选择合适的阈值 n0 ？ * 如何确定子问题的规模？ * 如何合并子问题的解？ 根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同，这样可以使算法的效率提高。 分治法的优点包括： * 可以解决一些难以解决的大问题 * 可以提高算法的效率 * 可以简化问题的解决过程 分治法的缺点包括： * 需要选择合适的阈值 n0 * 需要确定子问题的规模 * 需要合并子问题的解 分治法是一种常用的算法设计策略，它可以解决一些难以解决的大问题，并提高算法的效率。但是，需要注意选择合适的阈值 n0、确定子问题的规模和合并子问题的解等问题。