第5章 算法设计基本方法2.ppt

2019/10/30南京信息工程大学,计算机与软件学院 闫雷鸣,第5 章算法设计基本方法2,南京信息工程大学,2019/10/30,例：0-1背包问题,设有3种物品，背包容量40公斤。物品1的重量30公斤，价值150元；物品2的重量20公斤，价值80元；物品3的重量10公斤，价值70元。,南京信息工程大学,2019/10/30,0-1背包问题的解空间（状态树）,能优化吗？,南京信息工程大学,2019/10/30,5.2 回溯法,“通用解题法”，是带优化的穷举法。 按深度优先策略，从根结点出发搜索解空间树。 对任意结点，先判断该结点是否包含问题的解。 若肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯； 否则，进入该子树，继续按深度优先搜索策略搜索。 解为叶子结点 这种以深度优先方式系统搜索问题解的算法称为回溯法，它适用于求解组合数较大的问题,南京信息工程大学,2019/10/30,回溯法,在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造； 回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都被搜索遍才结束。 在它求问题的一个解时，只要搜索到问题的一个解就结束。,南京信息工程大学,2019/10/30,回溯法,回溯法的使用 1、确定问题状态结构； 2、分析问题状态空间树； 3、确定深度搜索与回溯规则； 4、确定解状态判别规则；,南京信息工程大学,2019/10/30,回溯法的算法框架,5.2.1 问题的解空间,5.2.2 回溯法的基本思想,5.2.3 递归回溯,5.2.4 迭代回溯,5.2.5 示例,南京信息工程大学,2019/10/30,复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。确定正确的解空间很重要，如果没有确定正确的解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。,5.2.1 问题的解空间,南京信息工程大学,2019/10/30,对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。 例如，对于有n个物品的0/1背包问题，其可能解的表示方式可以有以下两种： （1）可能解由一个不等长向量组成，当物品i(1in)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是： ( ), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) （2）可能解由一个等长向量x1, x2, , xn组成，其中xi=1(1in)表示物品i装入背包，xi=0表示物品i没有装入背包，当n=3时，其解空间是： (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) ,南京信息工程大学,2019/10/30,为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量x=(x1, x2, , xn)，其中分量xi (1in)的取值范围是某个有限集合si=ai1, ai2, , airi，所有可能的解向量构成了问题的解空间。,南京信息工程大学,2019/10/30,问题的解空间一般用解空间树（solution space trees,也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。,南京信息工程大学,2019/10/30,对于n=3的0/1背包问题，其解空间树如下图所示，树中的8个叶子结点分别代表该问题的8个可能解。 （依编号顺序搜索）,南京信息工程大学,2019/10/30,5.2.2 回溯法的基本思想,从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。 先判断结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，即判断该结点是否包含问题的（最优）解。 如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（pruning）； 否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,南京信息工程大学,2019/10/30,例如，对于n=3的0/1背包问题，三个物品的重量为20, 15, 10，价值为20, 30, 25，背包容量为25，从下图所示的解空间树的根结点开始搜索，搜索过程如下（依编号顺序）：,不可行解,南京信息工程大学,2019/10/30,回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索： （1）用约束条件剪去得不到可行解的子树； （2）用目标函数剪去得不到最优解的子树。 这两类函数统称为剪枝函数（pruning function）。 需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。,南京信息工程大学,2019/10/30,回溯法的求解过程,由于问题的解向量x=(x1, x2, , xn)中的每个分量xi(1in)都属于一个有限集合si=ai1, ai2, , airi，因此，回溯法可以按某种顺序（例如字典序）依次考察。 初始时，令解向量x为空，从根结点出发，选择s1的第一个元素作为解向量x的第一个分量，即x1= a11; 如果x=(x1)是问题的部分解，则继续扩展解向量x，选择s2的第一个元素作为解向量x的第2个分量; 否则，选择s1的下一个元素作为解向量x的第一个分量，即x1= a12。 依此类推，一般情况下，如果x=(x1, x2, , xi)是问题的部分解，则选择si+1的第一个元素作为解向量x的第i+1个分量时，有下面三种情况：,南京信息工程大学,2019/10/30,（1）如果是最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解； （2）如果是问题的部分解，则继续构造解向量的下一个分量； （3）如果既不是问题的部分解也不是问题的最终解，则存在下面两种情况： 如果xi+1= ai1,k不是集合si1的最后一个元素，则令xi+1= ai1,k1，即选择si+1的下一个元素作为解向量x的第i+1个分量； 如果xi+1= ai1,k是集合si1的最后一个元素，就回溯到x=(x1, x2, , xi)，选择si的下一个元素作为解向量x的第i个分量，假设xi= aik，如果aik不是集合si的最后一个元素，则令xi= ai,k1；否则，就继续回溯到x=(x1, x2, , xi1)；,南京信息工程大学,2019/10/30,回溯法的三个基本步骤 1）定义问题的解空间 2）确定易于搜索的解空间结构 3）深度优先搜索解空间，并在搜索过程中用剪枝函数避免无效搜索,南京信息工程大学,2019/10/30,5.2.3 递归回溯,回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。,void backtrack (int t) if (tn) output(x); else for (int i=f(n, t); i=g(n, t); i+) xt=h(i); if (constraint(t) ,t，当前结点在解空间树中的深度，控制递归深度； n，解空间树的高度； f(n, t)和g(n, t)是未搜索过的子树起始编号和终止编号。,南京信息工程大学,2019/10/30,5.2.4 迭代回溯,采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。,void iterativebacktrack () int t=1; while (t0) if (f(n, t)=g(n, t) for (int i=f(n, t); i=g(n, t); i+) xt=h(i); if (constraint(t) /回溯 ,南京信息工程大学,2019/10/30,5.2.5 回溯法示例1,子集和数问题 问题 给定由n个不同正数组成的集合w=wi，和正数m，求w中所有和等于m的子集的集合； 问题状态 可以设想，w中的每个数有选取和不选取两种可能，w的一个子集即为一个问题状态，可以表述为对每个元素选取或不选取的一个组合。 问题状态空间树 由空集开始，依次对每个元素进行选取和不选取两种选择，就可以得到w的全部子集，选取过程即可构成一棵状态空间树；,南京信息工程大学,2019/10/30,如：设w=1,5,12,14，则状态空间树如下：,南京信息工程大学,2019/10/30,子集和数问题,按照回溯法思想，从状态树的根结点出发，做深度优先搜索； 为便于计算，将w中的正数按从小到大排序； 当在某一状态a下，依次尝试加入和不加入正数wi， 若a+wim，则可停止对该结点的搜索； 若a+ (wiwn)m，则也可停止对该结点的搜索；,南京信息工程大学,2019/10/30,子集和数问题,算法如下： 设置辅助向量ai，记录wi是否被选入； sw表示w的剩余和，sa表示选入项的总和； 初始化ai = -1，表示未被处理过， sw= wi， sa=0； 从w0开始，进行深度优先搜索： 检查是否得解以及是否需要继续对该结点进行搜索，如果需要，则 如果ai为-1（未被处理过），则尝试不选入wi： 置ai = 0，即：不选入wi； sw -= wi; a+i = -1; 如果ai为0（未被选入），则尝试选入wi： 置ai = 1，即： 选入wi； sa += wi; a+i = -1; 如果ai为1（已被选入），则退回上一项： ai = -1; sw += wi; sa -= wi; -i;,南京信息工程大学,2019/10/30,回溯法分析,约束集d性质：若 (x1xi)满足d中所有约束(条件)，则其子集(x1xj) jj也不能满足d中，不必再继续搜索问题的解。 回溯求解的效率在很大程度上依赖于：产生局部解(x1xk)的时间；计算约束所需的时间；满足局部约束的解的个数； 通常可以应用重排原理，先搜索分支较少的局部解，在约束不满足时，可以裁剪去较多的搜索分支，从而提高搜索效率。,南京信息工程大学,2019/10/30,示例2：0-1背包问题,给定n个物品和一个背包。设物品i（1in）的重量为wi，其价值为vi，背包最大承重量为max。问，应该如何选择物品装入背包，才能使背包内物品的总价值最大？选择物品i时，要么全部装入，要么不装入，不能只装入物品i的一部分。,南京信息工程大学,2019/10/30,算法基本思想,如果到达叶子，返回最优解opt；否则， 试探左子树：选取物品i，计算tw，tv；递归，取下一个物品； 回溯，舍去物品i，重新计算tw，tv； 试探右子树：递归，取下一个物品；,南京信息工程大学,2019/10/30,剪枝,约束条件 目标函数 设当前结点i，取该物品，则扩展左子树；舍去该物品，则扩展其右子树 若当前重量tw+wimax，剪枝，跳过左子树 若当前价值+剩余物品的总价值当前最优价值bestv，则剪枝，跳过右子树,南京信息工程大学,2019/10/30,bestv=tv,in 如果已到达叶子,t,f,tw+wimax不超重,tvbestv,t,t,f,f,xi=1; 选取i,扩展左子树, 计算tw，tv,递归backknap，试探下一物品i+1,回溯，xi=0舍去i，计算tw，tv,剩余价值+tvbestv,扩展右子树：,递归backknap，试探下一物品,return bestv;,opt=x;,舍去,t,f,左子树,右子树,回溯,算法backknap,南京信息工程大学,2019/10/30,bestv=tv,in 如果已到达叶子,t,f,tw+wimax不超重,tvbestv,t,t,f,f,xi=1; 选取i,扩展左子树, 计算tw，tv,递归backknap，试探下一物品i+1,回溯，xi=0舍去i，计算tw，tv,剩余价值+tvbestv,扩展右子树：,递归backknap，试探下一物品,return bestv;,opt=x;,舍去,t,f,左子树,右子树,回溯,算法backknap(x, opt, tw, tv, i),tv=tv+vi; tw=tw+wi;,backknap(x, opt, tw, tv, i+1);,xi=0; tw=tw-wi; tv=tv-vi;,backknap(x, opt, tw, tv, i+1);,南京信息工程大学,2019/10/30,bestv=tv,in,t,f,tw+wimax,tvbestv,t,t,f,f,xi=1;,tv=tv+vi; tw=tw+wi;,backknap(x, opt, tw, tv, i+1);,xi=0; tw=tw-wi; tv=tv-vi;,bound(i+1)bestv,xi=0;/可不写,backknap(x, opt, tw, tv, i+1);,return bestv;,opt=x;,xi=0;,t,f,左子树,右子树,算法backknap(x, opt, tw, tv, i),回溯,南京信息工程大学,2019/10/30,0-1背包问题,解空间：子集树 约束条件： 上界函数： bound（）将剩余物品的价值依次相加，得到右子树最大价值的上界。,int bound(int i, int tv) / 计算子树价值上界 int vleft = tv; / 依次计算剩余价值之和 for (int j=i; jn; j+) vleft +=vj; return vleft ; ,思考： 能优化吗？,南京信息工程大学,2019/10/30,0-1背包问题,解空间：子集树 约束条件： 上界函数： 更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中价值的上界。,int bound(int i, int tw, int tv) / 计算子树价值上界 int wleft = max - tw; / 剩余容量 int vleft = tv; / 以物品单位重量价值递减序装入物品 while (i n ,南京信息工程大学,2019/10/30,0-1背包问题,int backtrack ( int x, int opt, int tw, int tv,int i ) if (i n) / 到达叶结点 if ( tvbestv )/ 若当前方案的价值更高 bestv = tv; for (int j=0; j bestv) backtrack(x, opt, tw, tv, i + 1); / 进入右子树 return bestv ; ,复杂度分析 计算上界需要o(n)时间，在最坏情况下有o(2n)个右子女结点需要计算上界，故解0-1背包问题的回溯算法backtrack所需的计算时间为o(n2n)。 注：回溯法最坏时间复杂度仍然与穷举法相同。,南京信息工程大学,2019/10/30,例如：n=3,背包容量c=30, w=16, 15, 15, v=45, 25, 25，当前价值v,南京信息工程大学,2019/10/30,思考：怎样化递归为迭代算法,设标志数组flagn： 扩展左子树后，令flagi=1；（进栈） 扩展右子树后，令flagi=2； 左、右子树的情况都处理过，令flagi=3； 回溯时，令flagi=0。（退栈） 当i=n-1时回溯； flagi=3时回溯；i-,南京信息工程大学,2019/10/30,迭代回溯,回溯法的一个非递归迭代过程。,void iterativebacktrack () int t=1; while (t0) if (f(n, t)=g(n, t) for (int i=f(n, t); i=g(n, t); i+) xt=h(i); if (constraint(t) /回溯 ,南京信息工程大学,2019/10/30,while (i=0) if ( constraint(i) /end while,部分迭代代码,南京信息工程大学,2019/10/30,课堂练习,（教材p98 例4.4） 输出n个自然数1n的全排列 （教材p99 例4.5） 不重复且无遗漏地产生集合s=1,2,n的全部r子集（s的r个互不相同的元素构成的子集）,南京信息工程大学,2019/10/30,例如：输出1n的全排列，递归表达如下,void f(int k) /已经具备x0xk-1, 函数目的：求解xk int i; if(k-1=n) /找到问题的一个解 for(i=0;in;i+) coutxi“ ”; /输出解向量 else for(i=1;in+1;i+) /候选集为1n中没有用过的数 if(!usedi) /usedi=0表示i没有使用过 xk=i; usedi=1; /i已经使用过 f(k+1); /递归求xk+1 uesei=0; /f(k+1)结束表示树中第k层子树遍历完 /*即x1xk确定为某种组合的所有可能排列结果都已出，例如1,2,3,4,1,2,4,3即为x1,x2确定为1,2的所有可能排列结果，所以f(k+1)结束后，会在x1xk-1不变的情况下，看看除了i以外xk还有没有其它可用的值*/,南京信息工程大学,2019/10/30,非递归的算法过程如下,void f1( void ) k=1;from=1; i=1; while(k0) for( ;in+1;i+) if(!usedi /*回溯的处理，让第xk的取值范围变为in，实际上就是xk+1n */ ,南京信息工程大学,2019/10/30,提醒,13周开始，逢单周（13、15、17） 周二78节继续在z304上课 补课：5月25日（14周周三）34节，zn203 上机调整：,南京信息工程大学,2019/10/30,复习 回溯法,回溯法的构成要素 1）解空间树 2）深度优先搜索 3）设法避免搜索无用的分支： 剪枝函数,南京信息工程大学,2019/10/30,走不通，退回去，换条路重走回溯 关键是，设法提前知道走不通,南京信息工程大学,2019/10/30,复习 回溯法的基本思想,从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。 先判断结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，即判断该结点是否包含问题的（最优）解。 如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（pruning）； 否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,南京信息工程大学,2019/10/30,复习 回溯法,两种策略避免无效搜索： （1）用约束条件剪去得不到可行解的子树； （2）用目标函数剪去得不到最优解的子树。 这两类函数统称为剪枝函数（pruning function）。,南京信息工程大学,2019/10/30,例如，背包问题,约束条件：不能大于包的载重量 若选中该物品超重， 剪枝（舍弃左子树） 目标函数：价值最大 若剩下的物品价值（边界）与当前选中的物品价值总和目前方案的最大价值， 剪枝（舍弃右子树）（剪枝是什么？） 剪枝就是啥也不干,南京信息工程大学,2019/10/30,应用回溯法的三个基本步骤,1）定义问题的解空间 2）确定易于搜索的解空间结构 3）找到剪枝函数（约束、边界），深度优先搜索解空间,南京信息工程大学,2019/10/30,递归回溯,一般情况下用递归方法实现回溯法。,void backtrack (int t) if (tn) output(x); /递归结束条件 else for (int i=f(n, t); i=g(n, t); i+) xt=h(i); if (constraint(t) ,t，当前结点在解空间树中的深度，控制递归深度； n，解空间树的高度； f(n, t)和g(n, t)是未搜索过的子树起始编号和终止编号。,南京信息工程大学,2019/10/30,n后问题,在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。,南京信息工程大学,2019/10/30,为了简化问题，下面讨论四皇后问题。 四皇后问题的解空间树是一棵完全4叉树，树的根结点表示搜索的初始状态，从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置，从第2层结点到第3层结点对应皇后2在棋盘中第2行的可能摆放位置，依此类推。,南京信息工程大学,2019/10/30,4-皇后问题解空间的树结构中，皇后1放在第1列上，若皇后2在第2列上，则皇后2立即被杀死。,南京信息工程大学,2019/10/30,南京信息工程大学,2019/10/30,南京信息工程大学,2019/10/30,再回溯到结点1, 找到了一个4-皇后问题的可行解。,南京信息工程大学,2019/10/30,回溯法求解4皇后问题的搜索过程,南京信息工程大学,2019/10/30,8-皇后问题,8-皇后问题实际上很容易一般化为n-皇后问题，即要求找出一个n*n棋盘上放置n个皇后并使其不能互相攻击的所有方案。 令(x1,x2,xn)表示一个解，由于没有两个皇后可以放入同一列，因此所有的xi将是互不相同的。 那么关键是应如何去测试两个皇后是否在同一条斜角线上,南京信息工程大学,2019/10/30,1 2 3 4 5 6 7 8,1 2 3 4 5 6 7 8,由于解向量之间不能相同，所以解空间的大小由88个元组减少到8!个元组。上图中的解表示为一个8-元组即（4，6，8，2，7，1，3，5）。,南京信息工程大学,2019/10/30,8-皇后问题,如果用二维数组a(1:n,1:n)的下标来标记每个皇后的位置. 同一条斜角线上由左上方到右下方每个元素有相同的“行-列”值 由右上方到左下方的有相同的“行+列”值。,南京信息工程大学,2019/10/30,8-皇后问题,假设有两个皇后被放置在(i，j)和(k，l)位置上，那么根据以上所述，仅当 i j = k - l 或 i + j = k + l 时，它们才在同一条斜角线上。,南京信息工程大学,2019/10/30,将这两个等式分别变换成 j - l = i - k 或 j - l = k - i 因此，当且仅当 |j- l| = |i-k| 时（即两个皇后所在位置的行差距等于列差距时），两个皇后在同一条斜角线上。,南京信息工程大学,2019/10/30,假设有两个皇后被放置在(i，j)和(k，l)位置上 约束条件1：不能放在同一列 jl 约束条件2：不能放在同一斜角线 |j- l| |i-k|,南京信息工程大学,2019/10/30,算法：可以放置一个新皇后吗？,procedure place(k) /如果一个皇后能放在第k行和x(k)列，则返回true，否则返回false。x是一个全局数组，进入此过程时已置入了k个值。abs(r)过程返回r的绝对值/ 数组 xk; integer i,k; i1 while ( ik ) if ( xi=xk or abs(xi-xk)=abs(i-k) ) return (false) ii+1 return (true) end place,判断是否有其它的皇后与之在同一列或同一斜对角线上,南京信息工程大学,2019/10/30,递归回溯：,n后问题,bool queen:place(int k) for (int i=1;ik;i+) if ( (abs(i-k)=abs(xi-xk) | (xi=xk) ) return false; return true; ,南京信息工程大学,2019/10/30,递归回溯：,n后问题,void queen:backtrack(int t) if (tn) sum+; else for (int i=1;i=n;i+) xt=i; if (place(t) backtrack(t+1); ,南京信息工程大学,2019/10/30,迭代回溯：,n后问题,void queen:backtrack(int t) x1=0; int k=1; while (k0) xk+=1; while ( (xk=n) ,南京信息工程大学,2019/10/30,马跳棋盘（骑士游历）,nn的棋盘，马（骑士）从棋盘某格开始，按照“马走日”规则走过每格恰好一次，走完棋盘所有的格，求移动路线。 “日