第六讲-回溯法.ppt

1、算法设计与分析,第六讲 回溯法,主要内容 回溯法基本要素 回溯算法的设计思想 回溯算法的设计过程 回溯算法的设计实例 重点 回溯算法的设计思想和设计过程 难点 针对具体问题的回溯算法,6.1 回溯法（back tracking）基础,一、适用范围,需要搜索一个或一组解,满足约束条件的最优解,求一个或一组满足约束条件的解向量 X=(x1, x2, xn),隐式约束条件 B(x1, x2, xn),显式约束条件 xi Si, |Si| =mi，1in,二、基本动机,1) 逐级扩展解向量,2) 动态测试部分解,用 Bi (x1 ， x2 ， ，xi-1 ，xi=a) 动态测试， 判定路径 x1 x2

2、 xi-1 xi = a 是否可行。,三、问题举例,例6.1 8皇后问题 。,解的表示：X=(x1,x2,x8),显式约束: xiSi ，1i8， Si=1,2,3,4,5,6,7,8,隐式约束： 任何两个皇后不能相互攻击,解空间大小： 穷举法 88，回溯法 8!,例6.2 子集和数问题 。已知 n 个正数，即W=(w1,w2, , wn)，求 wi 的和数为 M 的所有子集。,例如，W=(w1, w2, w3, w4)=(11, 13, 24, 7), M=31,满足条件的子集：(11, 13, 7), (24, 7),向量表示：(1, 2, 4), (3, 4),解向量的k元组变长表示：

3、(x1,x2, , xk)，要求 xi xi+1,解向量的n元组定长表示： (x1, x2, , xn)，xi0,1,6.2 回溯算法设计,解向量：由根节点到叶节点的路径所定义,例6.3 4皇后问题的解空间树结构。,一、解空间的树结构表示,树中的节点：求解过程的一个状态,树中的边：标示 xi 的一个可能的值,解向量： 由根节点到任意叶节点的路径定义,解空间：由根节点到所有叶节点的路径定义,特点,例6.4 n=4的子集和数问题的解空间树结构。,1) 解向量长度可变的树结构,解向量，解空间的定义？,2) 解向量长度固定的树结构,解向量，解空间的定义？,二、解空间树的状态描述,问题状态,状态空间,解

4、状态,答案状态,状态空间树,三、回溯法的抽象描述,1) 根据问题特点设计状态空间树,基本任务,2) 逐个地生成问题状态,3) 确定问题状态是否是解状态,4) 确定解状态是否是答案状态,1) 活节点,1) 回溯法: 使用规范函数杀死活节点的深度优先生成法,状态空间树的三类节点,状态空间树的生成方法,2) E节点,3) 死节点,2) 分支限界法: E节点一直保持到死的生成方法 (宽度优先, D检索),皇后问题的回溯法求解过程,1,killed,killed,killed, back,killed, back,killed, back,killed,killed,output, back,kille

5、d, back,算法的抽象描述,( x1, x2, xi-1 )：由根节点到某个节点的一条子路径 Si :xi的值的集合,Bi( x1,x2,xi )：动态规范函数, 如果路径 ( x1,x2,xi ) 不可能 延伸至一个答案节点, 取假值, 否则, 取真值,非递归算法,BackTracking1(int n) int i=1; while(i0) for(xiSi ) if (Bi(x1,x2,xi)=TRUE) if(x1,x2,xi)已抵达答案节点) printf(x1,x2,xi); else i=i+1; i=i-1; ,递归算法,BackTracking2(int i) for(x

6、iSi ) if (Bi(x1,x2,xi)=TRUE) if(x1,x2,xi)已抵达答案节点) printf(x1,x2,xi); else BackTracking2(i+1); ,影响算法计算复杂度的因素,1) 满足显式约束条件的xi的数目,2) 生成下一个xi的时间,3) Bi(x1,x2,xi)的计算时间,4) 满足Bi(x1,x2,xi)的xi的数目,内容回顾,回溯法的适用范围,解空间的树结构表示,状态空间树的扩展方法,回溯算法的抽象描述,影响回溯算法效率的因素,6.3 n皇后问题,一、规范函数,设棋盘上任意两个皇后的位置为：(i, j), (k, l),i - k = j -

7、l,i + j = k + l,斜线上的皇后，其位置关系可统一表示为： | i k | = | j l |,设皇后位置的列值用 xn 表示，规范函数 Bk(x1:k) 可设计为:,/ Place判断在第 k 行的当前列是否可放置一个皇后 int Place(int k) int i; extern int xn; for(i=0; ik-1; i+) if( (xi=xk-1) | (abs(xi-xk-1)=abs(i-k+1) ) return false=0; return true=1; ,NQueens1(int n) int k, n; extern int xn; k=0; xk

8、=-1; while(k=0) xk=xk+1; while(xkn) ,二、回溯算法,非递归算法,NQueens2(int k) extern int xn; xk=-1; while(1) xk=xk+1; while(xkn) ,递归算法,6.4 子集和数问题,一、解向量定长表示下的问题描述,已知 w1:n, wi0, 0in, 求 x1:n, 使,二、规范函数,Bk(x1:k)=,为求 xk,可令规范函数 Bk(X1:k)为:,三、回溯算法,几个变量：,规范函数：,Subset1(float s, float r, int k) extern float wn; extern int

9、xn; xk-1=1; if(s+wk-1=M) printf(x0:k-1); else if( (s+r)=M) ,递归算法,思考：初始调用入口？,Subset2(int n) float s=0, r=sum of w0:n-1; x0:n-1=2; k=1; while(k0) -xk-1; if(xk-1=0) if( (s+r-wk-1=M) ,非递归算法,6.5 图着色问题,一、问题描述,1) m着色判定问题 2) m着色优化问题 3) 图着色问题的起源,二、求所有m着色方案的递归算法,颜色表示： 1, 2, , m 节点颜色： xn, 初值为0 图的表示： gnn, gij0，

10、1,MColoring(int k) / x0=1, k从2开始 extern int xn; extern int gnn; int j; while(1) while(1) xk-1=(xk-1+1)%(m+1); if(xk-1=0) return; for(j=0; j=k-2; j+) if(gk-1j=1) ,递归回溯算法:,6.6 哈密顿环,一、问题描述,n个节点的连通图G=(V, E)，一个哈密顿环是一条沿着图G的n条边的环形路径，它访问每个节点一次并返回到它的起始位置。,二、解的表示与规范函数,三、求哈密顿环的递归算法,Hamiltonian(int k) / x0=1, k

11、从2开始 while(1) while(1) xk-1=(xk-1+1)%(N+1); if(xk-1 = 0) break; if(edge(k-2,k-1) for(int j=0; (jk-1) ,1) edge函数 2) xN 的定义与初始化 3) 初始调用接口 4) 哈密顿环与TSP问题的关系,补充说明,6.7 0/1背包问题,一、问题描述,已知一个容量为M的包和n件物品, 每件物品的重量为wi, 效益值为pi. 若将物品i装入包中, 背包可得到pi的效益值增量. 要求找到一种装入物品的方案, 在不超过包的总容量前提下, 使包获得最大效益值, 即求使目标函数,最大化, 且满足约束条件

12、,的向量X, xi0, 1, pi0, wi0, 1in.,二、回溯算法,规范函数设计,1) 有助于杀死某些不再需要扩展的节点,2) 可用于判断任意子孙所导致的最好可行解效益值的上界,float Bound1(W, P, k) / extern float pn, wn; for( i=k; in; i+) W=W+wi; if (W=M) P=P+pi; else return P+(1-(W-M)/wi)*pi; return P; ,确定背包可容纳物品数的上界函数,非递归回溯算法,BKnap1(int n) / extern float wn, pn, extern int xn. int yn, k=0; float W=0, P=0, ow, op=-1; while(1) while (k=0) ,改进的回溯算法,BKnap2(int n) /extern wn, pn, xn, yn int k=0; float W=0, P=0, ow, op=-1, ub; while(1) while(1) while(k=0) ,三、求解最优化问题的一般步骤,本讲小结,1) 回溯法的应用特点 2) 回溯法的主要原理 3) 应用时需解决的关键问题