《算法设计与分析》回溯ppt课件.ppt

回溯算法,单击增加标题内容,回溯法有“通用的解题法”之称。,5.1 回溯法的基本思想,5.2 回溯法的算法框架,5.3 n后问题,5.4 圆排列问题,5.5 电路板排版问题,回溯法（backtracking）是一种系统地搜索问题解的方法。为实现回溯，首先需要定义一个解空间（solution space），然后以易于搜索的方式组织解空间，最后用深度优先的方法搜索解空间，获得问题的解。说话的方式简单点：从一条路往前走，能进则进，不能进则退回来，换一条路再试。,搜索方式,内注意：这棵解空间树不是遍历前预先建立的，而是隐含在遍历过程中。容,定义一个解空间，它包含问题的解,用易于搜索的方式组织解空间,深度优先搜索解空间，获得问题的解。,Ps：利用限界函数避免移动到不可能产生解的子空间。,回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。,单击增加标题内容,解空间,从n个元素的集合S中找出满足某种性质的子集时,确定n个元素满足某种性质的排列时,可行解,最优解,可行解和最优解,活结点,扩展结点,死结点,不满足约束条件、目标函数、或其儿子结点已全部搜索完毕的结点、或者叶结点。以死结点作为根的子树，可以在搜索过程中删除,所搜索到的结点不是叶结点，且满足约束条件和目标函数的界，其儿子结点还未全部搜索完毕,正在搜索其儿子结点的结点，它也是一个活结点,当前扩展结点成为死结点时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点,回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解，或解空间中已无活结点时终止,从其解空间树的根结点开始搜索其解空间。开始时，根结点A是唯一的活结点，也是当前扩展结点。在当前扩展结点A处，可纵深移至B或C。,n=3,w=16,15,15,p=45,25,25,c=30。,在当前扩展结点A处，可纵深移至B或C。选择先移至B，即选取物品w1，此时，A、B均为活结点，B成为当前扩展结点。在B处剩余背包容量是r=30-16=14，获取价值45。从B可纵深移至D或E，先考虑移至D，但现仅有的背包容量容不下物品w2，故移至D导致一个不可行解。而从B移至E不占用背包容量，因而可行。从而我们选择移至E。此时E成为新的扩展结点。此时，A、B和E是活结点。在E处容量仍为14，所得价值仍为45。从E可以移至J和K。移至J会导致一个不可行解，而移向K是可行的，于是移至K，K成为新的扩展结点。由于K是一个叶结点，所以我们得到一个可行解(1,0,0),v=45。,由于从K已无法纵深扩展，故K成为一个死结点，所以返回（回溯）至E（离K最近的一个活结点）。而E也没有可扩展的结点，也成为了死结点。接下来，再继续回溯，返回至B处，同样B也成为死结点。再返回A，从A可扩展移至C。从A移至C，r=30,获取价值0。从C可移至F或G，令先移至F，则F成为新的扩展结点，此时有活结点A,C,F。在F有r=30-w2=15,获取价值25。从F向纵深移至L处，有r=0,获取价值25+25=50。L是叶结点，即获得一可行解，又获取了至今最高价值，因此记录该可行解。L不可扩展，返回F处。按此方式继续搜索，可搜索遍整个解空间。搜索结束后找到的最好解是相应0-1背包问题的最优解。,单击增加标题内容,用约束函数在扩展结点出剪去不满足约束的子树,用限界函数剪去得不到最优解的子树,两类函数通称为剪枝函数,递归回溯,Void backTrace (int t)If(tn) output(x);elsefor(i=f(n,t);i=g(n,t);i+)xt=hi;if(constraint(t),Void iterativeBacktrack(int t)t=1;While(t0) if(f(n,t)=g(n,t)for(i=f(n,t);i=g(n,t);i+)xt=hi;if(constraint(t),迭代回溯,在88的棋盘上放置8个皇后，使得这8个皇后不在同一行、同一列及同一斜角线上。如图：,N后问题,剪枝函数,8皇后问题可以表示成8元组(x1,x8),其中xi是放在第i行的皇后所在的列号。于是，解空间由8个8元组组成。约束条件：xixj for all i, j |xi-xj| j-i |约束条件之一为没有两个xi相同(即任意两个皇后不在同一列上)。其二为没有两个皇后在同一斜线上。,12345678,1 2 3 4 5 6 7 8,N后问题主要算法部分,boolean place(int k) int i; for (i=1;ik;i+) if(xi=xk)|(abs(xi-xk)=abs(i-k) return false; return true;,void backTrack(int t)if (tn) sum+; print(x);elsefor(i=1;i=n;i+) xt=i; if (place(t) backtrack(t+1);,圆排列问题,给定n个大小不等的圆c1,c2,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为,圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时a=r1,r2,rn是所给的n个元的半径，则相应的排列树由a1:n的所有排列构成。 解圆排列问题的回溯算法中，CirclePerm(n,a)返回找到的最小的圆排列长度。初始时，数组a是输入的n个圆的半径，计算结束后返回相应于最优解的圆排列。center计算圆在当前圆排列中的横坐标，由x2 = sqrt(r1+r2)2-(r1-r2)2)推导出x = 2*sqrt(r1*r2)。Compoute计算当前圆排列的长度。变量min记录当前最小圆排列长度。数组r表示当前圆排列。数组x则记录当前圆排列中各圆的圆心横坐标。在递归算法Backtrack中，当in时，算法搜索至叶节点，得到新的圆排列方案。此时算法调用Compute计算当前圆排列的长度，适时更新当前最优值。 当in时，当前扩展节点位于排列树的i-1层。此时算法选择下一个要排列的圆，并计算相应的下界函数。,算法设计,如果不考虑计算当前圆排列中各圆的圆心横坐标和计算当前圆排列长度所需的计算时间按，则 Backtrack需要O(n!)计算时间。由于算法Backtrack在最坏情况下需要计算O(n!)次圆排列长度，每次计算需要O(n)计算时间，从而整个算法的计算时间复杂性为O(n+1)!) 上述算法尚有许多改进的余地。例如，像1,2,n-1,n和n,n-1, ,2,1这种互为镜像的排列具有相同的圆排列长度，只计算一个就够了，可减少约一半的计算量。另一方面，如果所给的n个圆中有k个圆有相同的半径，则这k个圆产生的k!个完全相同的圆排列，只计算一个就够了。,算法效率,电路板排列问题,将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B=1, 2, , n是n块电路板的集合，L=N1, N2, , Nm是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是xi。x所确定的电路板排列Density (x)密度定义为跨越相邻电路板插槽的最大连线数。,问题描述,电路板排列问题,左下图中，跨越插槽2和3,4和5，以及插槽5和6的连线数均为2。插槽6和7之间无跨越连线。其余插槽之间只有1条跨越连线。,算法分析,电路板排列问题是NP难问题，因此不大可能找到解此问题的多项式时间算法。考虑采用回溯法系统的搜索问题解空间的排列树，找出电路板的最佳排列。设用数组B表示输入。Bij的值为1当且仅当电路板i在连接块Nj中。设totalj是连接块Nj中的电路板数。对于电路板的部分排列x1:i，设nowj是x1:i中所包含的Nj中的电路板数。由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当nowj0且nowj！=totalj。用这个条件来计算插槽i和i+1间的连线密度。,算法效率,在解空间排列树的每个节点处，算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。另外，生成排列树需要O(n!)时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd=0。因此最优解被更新的额次数为O(m)。更新最优解需要O(mn)时间。综上，解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)。,编曲：吴瑞峰填词：吴瑞峰演唱：Eason,