**回溯法**

**9近似算法**

（1）主要内容

l 基本定义：差界、相对性能界

l 多项式近似方案

（1）主要内容

l 3着色问题、8皇后问题

l 一般回溯方法

l 分支限界法



l 重点：回溯法的一般算法框架

l 难点：动态生成搜索树方法

 主要内容

l P类、NP类

l NP完全问题                                                                                                                                                                                                                                        





l 深刻理解剪枝在搜索求解中的重要作用；

l 掌握常见的几类剪枝技巧；

l 熟练应用深度优先搜索并了解其他相关搜索算法。