Ta上传的资源 (0)

在算法设计的基本方法中，回溯法是最一般的方法之一。在那些涉及到寻找一组解的问题或者求满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解。

在实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段，而且在任一阶段i后的行为都仅依赖于i阶段的过程状态，而与i阶段之前的过程是如何达到i阶段的状态的方式无关，这样的过程就构成一个多阶段决策过程。在50年代，贝尔曼(RichardBellman)等人根据这类问题的多阶段决策的特性，提出了解

在图的检索方法中，BFS和D-检索这两种方法都是对当前E-结点(正在扩展的结点)检测完毕之后，再检测以队或栈结构形式存放在活结点(已经生成但其子结点尚未全部生成的结点)表中的其它结点。将这两种方法一般化后就成为分枝_限界策略。分枝_限界法是在生成当前E-结点的全部子结点后再生成其它活结点的子结点，与

这一类求取最优解的问题，根据描述约束条件和目标函数的数学模型的特性或求解问题方法的不同，进一步又可划分为线性规划、整数规划、非线性规划、动态规划等问题。尽管各类规划问题都有一些相应的求解方法，但其中的某些问题，还可用一种更直接的方法来求解，这种方法就是贪心方法（贪婪法）。

算法设计是一件非常困难的工作。常用的算法设计技术有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法和动态规划法等。另外，为了以更简洁的形式设计和描述算法，在设计算法时常采用递归技术，用递归描述算法。 本讲中，主要介绍分治法。