University of Science and Technology of China 主讲人： 吕敏 Email: Spring 2012 ，USTC 算法基础University of Science and Technology of China * 2 第十一讲 回溯法 内容提要： p 理解回溯法的深度优先搜索策略 p 掌握用回溯法解题的算法框架 子集树算法框架 排列树算法框架 p 通过应用范例学习回溯法的设计策略University of Science and Technology of China 3 l 搜索算法介绍 （1）穷举搜索 （2）盲目搜索 深度优先(DFS)或回溯搜索( Backtracking); 广度优先搜索( BFS ); 分支限界法 (Branch /叶子结点是可行解 else while( all Xt) do /Xt为当前扩展结点的所有可能取值集合 xt = Xt中的第i个值； if( Constraint(t) and Bound(t) ) Backtrack( t+1 ); 执行时，从Backtrack(1)开始。 11-2 算法框架Uni
