数据结构、算法与应用(C++语言描述)》习题参考答案doc

第10章 算法设计策略及应用实例

1. 具有什么特征的问题适合用分治策略求解

三个特征：

（1） 原问题可以分解成规模较小、相互独立和类型相同的子问题；

（2） 子问题的规模缩小到一定的程度，就不需要再分解，可以容易地求解； （3） 所有子问题的解能够合并成原问题的解。 2. 递归算法和迭代算法的区别是什么

递归算法是利用函数直接或者间接调用自身来完成某个计算过程。为了求解规模为n的问题，设法将它分解成规模较小的问题，并能从规模较小的解构造出原问题的解。迭代法根据问题规模为i-1的解，由问题的迭代性质，构造问题规模为i的解，最后得到规模为n的原问题的解。所以，递归算法是从大到小、从上到下地构造问题的解，而迭代算法是从小到大、从下到上地构造或者逼近问题的解。 3. 具有什么性质的问题适合贪心策略求解

具有如下性质：第一、最优子结构性质；第二、贪心选择性质。 4. 具有什么性质的问题适合动态规划策略求解

具有如下性质：第一、最优子结构性质；第二、子问题重叠性质。 5. 贪心策略和动态规划策略之间的差别有哪些

两种策略的不同之处在于，贪心策略做出的每步贪心选择都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步的最优解无需保留。动态规划策略的全局最优解一定包括某个局部最优解，但是不一定包括前一个局部最优解，因此动态规划策略需要保存之前的所有局部最优解。

6. 回溯策略和分支限界策略之间的差别有哪些

回溯策略和分支限界策略的差别体现在以下方面：第一、分支限界策略没有限制树的搜索方法，可以是广度优先搜索，也可以是最小成本搜索，而回溯策略采用的是深度优先搜索；第二、分支限界策略只能用于优化问题，而回溯策略可以用于非优化问题，例如求问题的可行解。