算法设计与分析教学课件

1、 第2部分 算法设计策略第8章 回溯法 8.1 一般方法 8.2 n-皇后 8.3 子集和数 8.4 图的着色 8.5 哈密顿环 8.6 0/1背包 8.7 批处理作业调度8.1 一般方法 问题的所有可能的解可以用树形结构来表示，通过在树中遍历搜索找到可行解或最优解 8.1.1 基本概念 问题解可以用向量形式表示：(x0,x2,xn-1) 问题中规定了每个xi取值的约束条件称为显式约束（explicit constraint）。 对给定的一个问题实例，显式约束规定了所有可能的元组(候选解)，它们组成问题的候选解集，被称为该问题实例的解空间（solution space）。判定一个候选解是否为可

2、行解的条件为问题的隐式约束（implicit constraint）。 目标函数，也称代价函数（cost function），用来衡量每个可行解的优劣。使目标函数取最大（或最小）值的可行解为问题的最优解。状态空间树（state space）是描述问题解空间的树形结构。树中每个结点称为一个问题状态（problem state）。如果从根到树中某个状态的路径代表了一个作为候选解的元组，则称该状态为解状态（solution state）。若这个候选解可行，则称该解状态为答案状态(answer state)。 例 0/1背包问题M，n；wi, pi(x0,x1,x2,x3)显示约束：xi0，1隐式约束

3、： xiwiM目标函数： xipi当n=3时对应的状态空间树 树中总结点数2n+1-1树中叶子结点数2n01010101010101第1层第2层第3层第4层 例 排序问题元素a0,a1,an-1排序问题解向量（x0,x1,xn-1), xi表示元素ai在排列中的位置显示约束：xi0,1,n-1且xixj (ij)隐式约束： aiaj (xixj)无目标函数(13,24,09) 树中总结点数：1+n+n(n-1)+n(n-1)(n-2)+n!树中叶子结点数n!ai012n-1 8.1.2剪枝函数和回溯法 为了提高搜索效率，在搜索过程中使用约束函数（constraint function），可以避

4、免搜索那些已知不含答案状态的子树。如果是最优化问题，还可使用限界函数（bound function）剪去那些不可能包含最优答案结点的子树。约束函数和限界函数的目的都是为了剪去不必要搜索的子树，减少问题求解过程中实际生成的状态结点数，它们统称为剪枝函数（pruning function）。 使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法（backtracking）；广度优先生成结点，并使用剪枝函数的方法称为分枝限界法（branch-and-bound）。 【程序81】递归回溯法Void RBacktrack(int k) /应以Rbacktrack(0)调用本函数 for (每个

5、xk,使得 xkT(x0,xk-1) &(Bk(x0,xk) if ( (x0,x1,xk)是一个可行解) 输出 (x0,x1,xk); RBacktrack(k+1); T(x0,xk-1) 代表xk所有可能取值约束函数 Bk(x0,xk)部分向量(x0,xk-1) 代表从根到一个中间状态Y的路径 【程序8-2】 迭代回溯法Void IBacktrack(int n) int k=0; while (k=0) if (还剩下尚未检测的xk，使得xk T(x0,xk-1) & Bk(x0,xk) if ( (x0,x1,xk)是一个可行解) 输出(x0,x1,xk); k+; else k-;

6、 8.1.3回溯法的效率分析 状态空间树种总结点数为：2n,n!, nnp(n)是n的多项式，是生成一个结点所需的时间回溯算法的最坏情况时间复杂度可达O(p(n)n!)（或O(p(n)2n)或O(p(n)nn)）。 蒙特卡罗方法（Monte Carlo）基本思想是在状态空间树中随机选择一条路径(x0, x1, xn1)。设X是这条随机路径上第k+1层的结点，代表部分向量(x0, x1, xk1) ，如果在X不受限制的孩子数目是mk，则认为与X同层的其他结点不受限制的孩子数目也都是mk。推测整个状态空间树上将实际生成的结点数估计为 m = 1+m0+m0m1+m0m1m2+ 这种方法一般重复进行

7、几次，取平均值 【程序8-3】 蒙特卡罗算法int Estimate(SType* x) int k=0, m=1, r=1; do SetType S= xk| xkT(x1,xk1) & Bk(x1,xk=true)； if (!Size(S) return m; r=r*Size(S); m=m+r; xk=Choose(S);k+; while(1);函数size返回集合S的大小；函数Choose从集合S中随机选择一个 8.2 n-皇后 8.2.1 问题描述 n-皇后问题要求在一个nn的棋盘上放置n个皇后，使得它们彼此不受“攻击”。n-皇后问题要求寻找在棋盘上放置这n个皇后的方案，使得

8、它们中任何两个都不在同一行、同一列或同一斜线上。 8.2.2 回溯法求解 皇后问题可用n-元组（x0, x1, xn1）表示n-皇后问题的解，其中xi表示第i行的皇后所处的列号(0 xin)。显式约束的一种观点是：Si=0, 1, , n1，0in。相应的隐式约束为：对任意0i, jn，当ij时，xixj且|xi-xj|i-j|。此时的解空间大小为nn。另一种显式约束的观点是：Si=0, 1, , n1，0in，且xi xj(0i, jn, ij)。相应的隐式约束为：对任意0i, jn，当ij时，。与此相对应的解空间大小为n!。 如排序问题相同，皇后问题的状态空间树是一棵排列树。排列树有n!个

9、叶结点，遍历排列树的时间为(n!)。 4皇后问题对应的排列图 8.2.3 n-皇后算法 【程序8-4】 n-皇后问题的回溯算法bool Place(int k, int i,int* x) /xk=i是否可行/判定两个皇后是否在同一列或在同一斜线上 for (int j=0;jk;j+) if (xj=i) | (abs(xj-i)=abs(j-k) return false; return true; void NQueens(int n,int *x) NQueens(0,n,x); void NQueens(int k,int n,int *x) for (int i=0; in;i+)

10、 if (Place(k,i,x) xk=i; if (k=n-1) for(i=0;in;i+) coutxi ; coutendl; else NQueens(k+1,n,x); 4皇后问题的两个可行解 其中一个可行解的回溯过程 实际生成的树结点XXXXXX 8.2.4 时间分析可通过蒙特卡罗法计算5次试验中实际需要生成的结点数的平均值为1625。8-皇后问题状态空间树的结点总数是： 因此，需要实际生成的结点数目大约占总结点数的1.55%。 8.3 子集和数 8.3.1 问题描述已知n个不同正数wi，0in-1，的集合，求该集合的所有满足条件的子集，使得每个子集中的正数之和等于另一个给定的

11、正数M。例82 设有n=4个正数的集合W=w0,w1,w2,w3=(11,13,24,7)和整数M=31，求W的所有满足条件的子集，使得子集中的正数之和等于M。 8.3.2 回溯法求解 解结构形式：可变长度元组和固定长度元组。可变长度元组（x0,xk1,xk），0kn。元组的每个分量的取值可以是元素值，也可以是选入子集的正数的下标。固定长度n-元组（x0,x1,xn1），xi0,1, 0in。xi=0，表示wi未选入子集，xi=1，表示wi入选子集。 如同0/1背包问题，称这种从n个元素的集合中找出满足某些性质的子集的状态空间树为子集树。子集树有2n个解状态，遍历子集树的时间为(2n)。 约定

12、wi为正数按升序排列，分析xk应满足的约束条件：w0,w1,wk-1,wk,wk+1,wn-1x0,x1,xk-1,xk,xk+1,xn-1s部分和 r剩余和xk=1xk=0s+r-wkMs+rM & s+wkM 8.3.3子集和数算法 【程序85】子集和数的回溯算法 void SumOfSub (float s, int k, float r, int* x, float m, float* w) /s部分和 r剩余和 xk=1; if (s+wk=m) /得到一个可行解 for (int j=0;j=k;j+) coutxj ; coutendl; else if (s+wk=m) ) /

13、搜索右子树 xk=0; SumOfSub(s, k+1, r-wk, x, m, w); void SumOfSub (int* x, int n, float m, float* w) float r=0; for(int i=0;i=m & w0=m) SumOfSub(0, 0, r, x, m, w); 例83 设有n=6个正数的集合W=(5,10,12,13,15,18)和整数M=30，求W的所有元素之和为M的子集。 8.4 图的着色 8.4.1 问题描述已知无向图G=(V,E)和m种不同的颜色，如果只允许使用这m种颜色对图G的结点着色，每个结点着一种颜色。问是否存在一种着色方案，使

14、得图中任意相邻的两个结点都有不同的颜色。这就是m-着色判定问题（m-colorability decision problem）如：地图着色问题 、四色猜想 8.4.2回溯法求解 设无向图G=(V,E)采用如下定义的邻接矩阵a表示： 解的形式：n-元组(x0,x1,xn1), xi1，m, 0in，表示结点i的颜色，这就是显式约束。xi=0表示没有可用的颜色。因此解空间的大小为mn。隐式约束可描述为：如果边(i,j)E，则 xixj。 约束函数：对所有i和j，0i,jk，ij，若aij=1，则xixj。 8.4.3 图着色算法 【程序86】 图的m着色算法 template void MGra

15、ph:NextValue(int k,int m,int *x) /确定分量xk的取值。1,m。xk初始值=0 do xk=(xk+1) % (m+1);/尝试下一种颜色 if (!xk) return;/没有可用颜色 for (int j=0; jk; j+) /可行判定 if (akj & xk = xj) break; if (j=k) return; /成功 while (1); template void MGraph: mColoring(int k, int m, int *x) do NextValue(k,m,x); /为xk分配颜色 if (!xk) break; if (

16、k = n-1) /得到图G的一种m-着色方案 for (int i=0; in; i+) cout xi ; cout endl; else mColoring(k+1,m,x); /继续深入下一个分量 while(1); template void MGraph: mColoring(int m,int *x) mColoring(0,m,x); 8.4.4 时间分析算法的计算时间上界可由状态空间树的结点数确定。每个结点的处理时间即NextValue的执行时间，为O(mn)。因此总时间为 8. 5 哈密顿环 8.5.1 问题描述已知图G=(V,E)是一个n个结点的连通图。连通图G的一个哈密

17、顿环(Hamiltonlan cycle)是图G的一个回路，它经过图中每个结点，且只经过一次。一个哈密顿环是从某个结点v0V开始，沿着图G的n条边环行的一条路径（v0,v1,vn1,vn），其中，(vi,vi+1)E,0in，它访问图中每个结点且只访问一次，最后返回开始结点，即除v0=vn，路径上其余结点各不相同。 8.5.2 哈密顿环算法对于n个结点的图G=(V,E)的哈密顿环问题，采用n-元组表示问题的解 (x0,x1,xn1)。显式约束：每个xi0,1,n-1, 0in，代表路径上一个结点的编号。因此解空间的大小为nn。隐式约束：可描述为：xixj,0i,jn，ij，且（xi,xi+1）

18、E，xi,xi+1V，i=0,1,n2，又（xn1，x0）E。哈密顿环问题的分析和求解方法与图的m-着色问题非常相似 【程序87】哈密顿环算法 template void MGraph:NextValue(int k,int *x) /求第k个分量的取值，结点从1开始编号 do xk=(xk+1)% n; /循环去下一个结点编号 if (!xk) return; /为0值，表示无可取值 if (axk-1xk) /可行性判定 for (int j=0;jk;j+) if (xj=xk) break; if (j=k) if (kn-1)|(k=n-1) & axn-1x0) return; w

19、hile(1); template void ExtMGraph:Hamiltonian(int k,int *x) /第k个分量的递归处理 do NextValue(k,x); /返回下一个可取值 if (!xk) return; /无可取值，剪枝处理 if (k=n-1) for (int i=0; in; i+) coutxi ; cout 0n; else Hamiltonian(k+1,x); /深度优先进入下一层 while (1); template void ExtMGraph: Hamiltonian(int *x) Hamiltonian(1,x); /结点从1开始编号 8

20、.6 0/1背包问题问题：给定M0, wi0, pi0 (0=in), 求一个n元组(x0,x1,xn-1), xi 0,1, 使得wixi=M且pixi 最大。解空间中构成一颗子集树，共有2n解状态。约束条件： xi 0,1wixi=M求最优解目标函数： pixi 8.6 0/1背包问题n=4的状态空间树 8.6 0/1背包问题记cw表示当前考虑k-1个物品后，已选入物品的重量记cp表示当前考虑k-1个物品后，已选入物品的收益设计约束函数Bk(x0,x1,xk)：第k个物品要选入（xk=1）必须满足：cw+wkM设计限界函数：剪去不含最优解的分枝 8.6 0/1背包问题设计限界函数：中间状态

21、X：剩余物品k+1,k+2,n-1剩余载重为M=M-cw记Y、rp分别表示对应一般背包问题的最优解和最优解值Z表示对应0/1背包问题的任意可行解Y=yk+1,yk+2,yn-1Z=xk+1,xk+2,xn-1则有：因此以bp=cp+rp作为X结点的上界值 8.6 0/1背包问题限界函数的实现通过发现的可行解确定当前最优解值L，后续的可行解收益fp，必须不小于L，也就是以L为下界任一中间状态X：若其上界值bpL，代表其下不含最优解，应剪去以X为根的子树。 限界函数作用示例M=110, n=8, W=(1,11,21,23,33,43,45,55), P=(11,21,31,33,43,53,55

22、,65) 关键程序上界函数值templateT Knapsack: Bound(int k,T cp, T cw) /cp是当前收益，cw是当前背包重量，k是当前待考察的物品编号 T b=cp, c=cw; for (int i=k+1;in; i+) c+=wi; if (cm) b+=pi; else return (b+(1- (c-m)/wi)*pi); return b; 8.7 批处理作业调度(最小平均完成时间) 8.7.1 问题描述设有n个作业的集合0,1,n-1，每个作业有两项任务要求分别在2台设备P1和P2上完成。每个作业必须先在P1上加工，然后在P2上加工。P1和P2加工作

23、业i所需的时间分别为ai和bi。作业i的完成时间fi(S)是指在调度方案S下，该作业的所有任务得以完成的时间，则是采用调度方案S的平均完成时间。 批处理作业调度(batch job schedule)问题要求确定这n个作业的最优作业调度方案使其MFT最小。这等价于求使得所有作业的完成时间之和最小的调度方案。 例85 设有三个作业和两台设备，作业任务的处理时间为（a0,a1,a2）=(2,3,2)和（b0,b1,b2）=(1,1,3)。这三个作业有6种可能的调度方案：(0,1,2),(0,2,1),(1,0,2), (1,2,0),(2,0,1),(2,1,0)它们相应的完成时间之和分别是19,18,20,21,19,19其中，最佳调度方案S=(0,2,1)。在这一调度方案下，f0(S)=3，f1(S)=7，f2(S)=8，FT=3+7+8=18。 8.7.2 回溯法求解对于双机批处理作业调度问题，其可行解是n个作业所有可能的排列，每一种排列代表一种作业调度方案S，批处理作业调度问题