Algorithm 版 (精华区)

发信人: Lerry (第一次有失恋的感觉), 信区: Algorithm
标  题: 分治法的几种变形
发信站: 哈工大紫丁香 (2002年03月12日11:04:30 星期二), 站内信件

分治法的几种变形
二分法 dichotomy
一种每次将原问题分解为两个子问题的分治法，是一分为二的哲学思想的应用。这种方
法很常用，由此法产生了许多经典的算法和数据结构。
分解并在解决之前合并法 divide and marriage before conquest
一种分治法的变形，其特点是将分解出的子问题在解决之前合并。
管道传输分治法 pipelined divide and conquer
一种分治法的变形，它利用某种称为“管道”的数据结构在递归调用结束前将其中的某
些结果返回。此方法经常用来减少算法的深度。
注: divide and marriage before conquest和pipelined divide and conquer 方法我
并不太了解，只在某些参考文献上看过其名称。其原文定义如下：
divide and marriage before conquest:A variant of divide and conquer in which
 subproblems created in the "divide" step are merged before the "conquer" st
ep.
pipelined divide and conquer:A divide and conquer paradigm in which partial 
results from recursive calls can be used before the calls complete. The tech
nique is often useful for reducing the depth of an algorithm.

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

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