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

《第5章 算法设计基本方法2.ppt》由会员分享，可在线阅读，更多相关《第5章 算法设计基本方法2.ppt（80页珍藏版）》请在课桌文档上搜索。

1、2023/11/6,第5 章算法设计基本方法2,2023/11/6,例：0-1背包问题,设有3种物品，背包容量40公斤。物品1的重量30公斤，价值150元；物品2的重量20公斤，价值80元；物品3的重量10公斤，价值70元。,2023/11/6,0-1背包问题的解空间（状态树）,能优化吗？,2023/11/6,5.2 回溯法,“通用解题法”，是带优化的穷举法。按深度优先策略，从根结点出发搜索解空间树。对任意结点，先判断该结点是否包含问题的解。若肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先搜索策略搜索。解为叶子结点这种以深度优先方式系统搜索

2、问题解的算法称为回溯法，它适用于求解组合数较大的问题,2023/11/6,回溯法,在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造；回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都被搜索遍才结束。在它求问题的一个解时，只要搜索到问题的一个解就结束。,2023/11/6,回溯法,回溯法的使用1、确定问题状态结构；2、分析问题状态空间树；3、确定深度搜索与回溯规则；4、确定解状态判别规则；,2023/11/6,回溯法的算法框架,5.2.1 问题的解空间,5.2.2 回溯法的基本思想,5.2.3 递归回溯,5.2.4 迭代回溯,5.

3、2.5 示例,2023/11/6,复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。确定正确的解空间很重要，如果没有确定正确的解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。,5.2.1 问题的解空间,2023/11/6,对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。例如，对于有n个物品的0/1背包问题，其可能解的表示方式可以有以下两种：（1）可能解由一个不等长向量组成，当物品i(1in)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是：()

4、,(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),2023/11/6,为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1,x2,xn)，其中分量xi(1in)的取值范围是某个有限集合Si=ai1,ai2,airi，所有可能的解向量构成了问题的解空

5、间。,2023/11/6,问题的解空间一般用解空间树（Solution Space Trees,也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。,2023/11/6,对于n=3的0/1背包问题，其解空间树如下图所示，树中的8个叶子结点分别代表该问题的8个可能解。（依编号顺序搜索）,2023/11/6,5.2.2 回溯法的基本思想,从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。先判断结

6、点对应的部分解是否满足约束条件，或者是否超出目标函数的界，即判断该结点是否包含问题的（最优）解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,2023/11/6,例如，对于n=3的0/1背包问题，三个物品的重量为20,15,10，价值为20,30,25，背包容量为25，从下图所示的解空间树的根结点开始搜索，搜索过程如下（依编号顺序）：,不可行解,2023/11/6,回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：（1）用约束条件剪去得不到可

7、行解的子树；（2）用目标函数剪去得不到最优解的子树。这两类函数统称为剪枝函数（Pruning Function）。需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。,2023/11/6,回溯法的求解过程,由于问题的解向量X=(x1,x2,xn)中的每个分量xi(1in)都属于一个有限集合Si=ai1,ai2,airi，因此，回溯法可以按某种顺序（例如字典序）依次考察。初始时，令解向量X为空，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1=a11;如果X=(x1)是问题的部分解，则继续扩展解向量X，选择S2的第

8、一个元素作为解向量X的第2个分量;否则，选择S1的下一个元素作为解向量X的第一个分量，即x1=a12。依此类推，一般情况下，如果X=(x1,x2,xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：,2023/11/6,（1）如果是最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解；（2）如果是问题的部分解，则继续构造解向量的下一个分量；（3）如果既不是问题的部分解也不是问题的最终解，则存在下面两种情况：如果xi+1=ai1,k不是集合Si1的最后一个元素，则令xi+1=ai1,k1，即选择Si+1的下一个元素作为解向量X

9、的第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)；,2023/11/6,回溯法的三个基本步骤1）定义问题的解空间2）确定易于搜索的解空间结构3）深度优先搜索解空间，并在搜索过程中用剪枝函数避免无效搜索,2023/11/6,5.2.3 递归回溯,回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。,void backtrack(int t)if(tn)out

10、put(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)是未搜索过的子树起始编号和终止编号。,2023/11/6,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)/回

11、溯,2023/11/6,5.2.5 回溯法示例1,子集和数问题问题给定由n个不同正数组成的集合W=wi，和正数M，求W中所有和等于M的子集的集合；问题状态可以设想，W中的每个数有选取和不选取两种可能，W的一个子集即为一个问题状态，可以表述为对每个元素选取或不选取的一个组合。问题状态空间树由空集开始，依次对每个元素进行选取和不选取两种选择，就可以得到W的全部子集，选取过程即可构成一棵状态空间树；,2023/11/6,如：设W=1,5,12,14，则状态空间树如下：,2023/11/6,子集和数问题,按照回溯法思想，从状态树的根结点出发，做深度优先搜索；为便于计算，将W中的正数按从小到大排序；当在

12、某一状态A下，依次尝试加入和不加入正数wi，若A+wiM，则可停止对该结点的搜索；若A+(wiwn)M，则也可停止对该结点的搜索；,2023/11/6,子集和数问题,算法如下：设置辅助向量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

13、;如果Ai为1（已被选入），则退回上一项：Ai=-1;SW+=wi;SA-=wi;-i;,2023/11/6,回溯法分析,约束集D性质：若(x1xi)满足D中所有约束(条件)，则其子集(x1xj)jj也不能满足D中，不必再继续搜索问题的解。回溯求解的效率在很大程度上依赖于：产生局部解(x1xk)的时间；计算约束所需的时间；满足局部约束的解的个数；通常可以应用重排原理，先搜索分支较少的局部解，在约束不满足时，可以裁剪去较多的搜索分支，从而提高搜索效率。,2023/11/6,示例2：0-1背包问题,给定n个物品和一个背包。设物品i（1in）的重量为wi，其价值为vi，背包最大承重量为Max。问，应

14、该如何选择物品装入背包，才能使背包内物品的总价值最大？选择物品i时，要么全部装入，要么不装入，不能只装入物品i的一部分。,2023/11/6,算法基本思想,如果到达叶子，返回最优解opt；否则，试探左子树：选取物品i，计算tw，tv；递归，取下一个物品；回溯，舍去物品i，重新计算tw，tv；试探右子树：递归，取下一个物品；,2023/11/6,剪枝,约束条件目标函数设当前结点i，取该物品，则扩展左子树；舍去该物品，则扩展其右子树若当前重量tw+wiMax，剪枝，跳过左子树若当前价值+剩余物品的总价值当前最优价值bestv，则剪枝，跳过右子树,2023/11/6,bestv=tv,iN 如果已到

15、达叶子,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,2023/11/6,bestv=tv,iN 如果已到达叶子,T,F,tw+wiMax不超重,tvbestv,T,T,F,F,xi=1;选取i,扩展左子树,计算tw，tv,递归BackKnap，试探下一物品i+1,回溯，xi=0

16、舍去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);,2023/11/6,bestv=tv,iN,T,F,tw+wiMax,tvbestv,T,T,F,F,xi=1;,tv=tv+vi;tw=tw+wi;,BackKnap(x,o

17、pt,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),回溯,2023/11/6,0-1背包问题,解空间：子集树约束条件：上界函数：Bound（）将剩余物品的价值依次相加，得到右子树最大价值的上界。,int Bound(int i,int tv)/计算子树价值上界 int vleft=tv;/依次计算剩余价值之和 for(int j=i;j

18、N;j+)vleft+=vj;return vleft;,思考：能优化吗？,2023/11/6,0-1背包问题,解空间：子集树约束条件：上界函数：更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中价值的上界。,int Bound(int i,int tw,int tv)/计算子树价值上界 int wleft=Max-tw;/剩余容量 int vleft=tv;/以物品单位重量价值递减序装入物品 while(i N,2023/11/6,0-1背包问题,int Backtrack(int x,int opt,int t

19、w,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)。注：回溯法最坏时间复杂度仍然与穷举法相同。,2023/11/6,例如：n=3,背包容量C=30,w=16,15,15,v=45,25,25，当前价值V,2023/11/6,思考：怎

20、样化递归为迭代算法,设标志数组flagN：扩展左子树后，令flagi=1；（进栈）扩展右子树后，令flagi=2；左、右子树的情况都处理过，令flagi=3；回溯时，令flagi=0。（退栈）当i=N-1时回溯；flagi=3时回溯；i-,2023/11/6,迭代回溯,回溯法的一个非递归迭代过程。,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)/回溯,2023/11/6,while(i=0)if(Constraint(i

21、)/end while,部分迭代代码,2023/11/6,课堂练习,（教材P98 例4.4）输出n个自然数1n的全排列（教材P99 例4.5）不重复且无遗漏地产生集合s=1,2,n的全部r子集（s的r个互不相同的元素构成的子集）,2023/11/6,例如：输出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=

22、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还有没有其它可用的值*/,2023/11/6,非递归的算法过程如下,void f1(void)k=1;from=1;i=1;while(k0)for(;in+1;i+)if(!usedi/*回溯的处理，让第Xk的取值范围变为in，实际上就是Xk+1n*/,2023/1

23、1/6,提醒,13周开始，逢单周（13、15、17）周二78节继续在Z304上课补课：5月25日（14周周三）34节，ZN203上机调整：,2023/11/6,复习 回溯法,回溯法的构成要素1）解空间树2）深度优先搜索3）设法避免搜索无用的分支：剪枝函数,2023/11/6,走不通，退回去，换条路重走回溯 关键是，设法提前知道走不通,2023/11/6,复习 回溯法的基本思想,从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。先判断结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，即判断该结点是否包含问题的（最优）解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，

24、即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,2023/11/6,复习 回溯法,两种策略避免无效搜索：（1）用约束条件剪去得不到可行解的子树；（2）用目标函数剪去得不到最优解的子树。这两类函数统称为剪枝函数（Pruning Function）。,2023/11/6,例如，背包问题,约束条件：不能大于包的载重量若选中该物品超重，剪枝（舍弃左子树）目标函数：价值最大若剩下的物品价值（边界）与当前选中的物品价值总和目前方案的最大价值，剪枝（舍弃右子树）（剪枝是什么？）剪枝就是啥也不干,2023/11/6,应用回溯法的三个基本步骤,1）定义问题的解空间2）确定

25、易于搜索的解空间结构3）找到剪枝函数（约束、边界），深度优先搜索解空间,2023/11/6,递归回溯,一般情况下用递归方法实现回溯法。,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)是未搜索过的子树起始编号和终止编号。,2023/11/6,n后问题,在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一

26、列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。,2023/11/6,为了简化问题，下面讨论四皇后问题。四皇后问题的解空间树是一棵完全4叉树，树的根结点表示搜索的初始状态，从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置，从第2层结点到第3层结点对应皇后2在棋盘中第2行的可能摆放位置，依此类推。,2023/11/6,4-皇后问题解空间的树结构中，皇后1放在第1列上，若皇后2在第2列上，则皇后2立即被杀死。,2023/11/6,2023/11/6,2023/11/6,再回溯到结点1,找到了一个4-皇后问题的可行解。,202

27、3/11/6,回溯法求解4皇后问题的搜索过程,2023/11/6,8-皇后问题,8-皇后问题实际上很容易一般化为n-皇后问题，即要求找出一个n*n棋盘上放置n个皇后并使其不能互相攻击的所有方案。令(x1,x2,xn)表示一个解，由于没有两个皇后可以放入同一列，因此所有的xi将是互不相同的。那么关键是应如何去测试两个皇后是否在同一条斜角线上,2023/11/6,1 2 3 4 5 6 7 8,12345678,由于解向量之间不能相同，所以解空间的大小由88个元组减少到8!个元组。上图中的解表示为一个8-元组即（4，6，8，2，7，1，3，5）。,2023/11/6,8-皇后问题,如果用二维数组A

28、(1:n,1:n)的下标来标记每个皇后的位置.同一条斜角线上由左上方到右下方每个元素有相同的“行-列”值由右上方到左下方的有相同的“行+列”值。,2023/11/6,8-皇后问题,假设有两个皇后被放置在(i，j)和(k，l)位置上，那么根据以上所述，仅当i j=k-l 或 i+j=k+l时，它们才在同一条斜角线上。,2023/11/6,将这两个等式分别变换成 j-l=i-k 或 j-l=k-i因此，当且仅当|j-l|=|i-k|时（即两个皇后所在位置的行差距等于列差距时），两个皇后在同一条斜角线上。,2023/11/6,假设有两个皇后被放置在(i，j)和(k，l)位置上约束条件1：不能放在同一

29、列jl约束条件2：不能放在同一斜角线|j-l|i-k|,2023/11/6,算法：可以放置一个新皇后吗？,Procedure PLACE(k)/如果一个皇后能放在第k行和X(k)列，则返回true，否则返回false。X是一个全局数组，进入此过程时已置入了k个值。ABS(r)过程返回r的绝对值/数组 Xk;integer i,k;i1while(ik)if(Xi=Xk or ABS(Xi-Xk)=ABS(i-k)return(false)ii+1return(true)End PLACE,判断是否有其它的皇后与之在同一列或同一斜对角线上,2023/11/6,递归回溯：,n后问题,bool Qu

30、een:Place(int k)for(int i=1;ik;i+)if(abs(i-k)=abs(xi-xk)|(xi=xk)return false;return true;,2023/11/6,递归回溯：,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);,2023/11/6,迭代回溯：,n后问题,void Queen:Backtrack(int t)x1=0;int k=1;while(k0)xk+=1;while(xk=n),2023/11

31、/6,马跳棋盘（骑士游历）,nn的棋盘，马（骑士）从棋盘某格开始，按照“马走日”规则走过每格恰好一次，走完棋盘所有的格，求移动路线。“日字”：先垂直或水平移动2格，再水平（垂直）走一格。,2023/11/6,2023/11/6,讨论,怎么解决？,2023/11/6,首先，怎样描述？1.坐标骑士位置（x，y）棋盘范围1,N或者0,N-1,2023/11/6,2.“马走日”的表示8个位置(x+2,y+1)(x+1,y+2)(x-1,y+2)(x-2,y+1)(x-2,y-1)(x-1,y-2)(x+1,y-2)(x+2,y-1),2023/11/6,3.怎样知道某位置已经“走过了”？设标志位若没走

32、过，flagxy=0；若走过了，flagxy0；,2023/11/6,4.怎样描述一个可行的路线？用一个数组记录，与棋盘位置对应若在第i步走到位置(x,y)flagxy=i,2023/11/6,第二，从哪个位置开始走？(1,1)按什么顺序走？怎样取“下一个”位置深度优先遍历简单的，穷举8个位置,2023/11/6,接下来干什么？第三，穷举如果某一步可继续走下去，就试探着走下去且考虑下一步的走法，若走不通则返回，考虑另选一个位置,2023/11/6,第四，怎样避免无效的搜索？约束函数棋盘nn，数组下标范围0,N-10 xN，并且0yN并且，没走过，flagxy=0,2023/11/6,应用回溯法

33、的三个基本步骤,1）定义问题的解空间2）确定易于搜索的解空间结构3）找到剪枝函数（约束、边界），深度优先搜索解空间,2023/11/6,解的形式二维数组flag,2023/11/6,procedure trynextstep(i)begin 选择准备；repeat 个位置中选一个；if 选择可接受 then begin 记录移动情况；if 棋盘未遍历完 then begin trynextstep(i+1)；if 试探不成功 then 删去以前的记录 回溯 end end until(移动成功)or(再无别的选择)end；,2023/11/6,小结,子集和数与0-1背包问题的解都是子集树n皇后问题的解是排列树回溯还可解决迷宫问题、旅行商问题等,