可能达到最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是问题的解。 基本步骤
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状
态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。 回溯法
基本思想：按照深度优先策略，从根结点出发搜索解空间。算法搜索至解空间的任一结点时总是先判断该结点是否问题的约束条件。如果满足进入该子树，继续按深度优先的策略搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法
基本步骤：
1、 确定问题的解空间：应用回溯法时，首先应明确
6
定义问题的解的空间。问题的解空间应至少包含问题的一个解。
2、 确定结点的扩展规则 3、 搜索解空间：从开始结点出发，以深度优先的方式搜索整个解空间。 【问题】 n皇后问题 分支限界法
基本思想： 分支限界法是由“分支”和“限界”两部分组成。“分支”策略体现在对问题空间是按广度优先的策略进行搜索“限界”策略是为了加速搜索速度面采用启发信息剪枝策略。
可能会让画出“子集树斩图”235页例题及图好好看一下。
7