《算法设计与分析 减治策略和变治策略》由会员分享，可在线阅读，更多相关《算法设计与分析 减治策略和变治策略（6页珍藏版）》请在金锄头文库上搜索。
1、减治策略及变治策略减治策略利用一个问题给定实例的解与该问题较小实例的解之间的关系，使原问题求解过程简化的方法称之为减治策略。可利用递归或者非递归的方法进行问题的求解。一般分为三类：（1）减去一个常量。也就是在求解过程中将原来的求解规模减小一个固定的常数，比如原来有n个元素，通过减治之后，编程n-1个元素，并且建立n个元素的求解过程与n个元素求解过程的联系，使问题的求解直接通过表达式来求解，从而简化问题的求解难度。一般采用自顶向下的分析方法，但求解时往往采用自底向上的求解过程。这也是递归的方法。（2）减去一个常量因子在规模中减去一个常量因子，使求解的规模成倍的缩小，从而提高问题求解的效率。 （3
2、）减去的规模可变。根据求解过程的变化来确定每次规模减少的程度。具体实例：1、直接插入排序2、拓扑排序3、全排列问题4、子集问题变治策略变治策略也就是将原始问题变换成更容易求解的实例，然后对变化后的实例进行求解。主要有如下类型：（1）变换为同样问题的更简单的实例，也就是实例化简。（2）变换为同样问题实例的不同形式，也成为改变表现。（3）变换为不同问题的实例，使问题更易求解，成为问题简化。实例将原始序列先转化成另一种存储形式，然后再进行排序以简化排序算法，比如：1、堆以及堆排序2、平衡二叉树此外，复杂问题简化以降低求解难度：1、多项式求解：霍纳法则2、进制之间的转换问题。此外，还有一些具体问题的求解方法均可采用变治策略。
