算法设计与分析回溯实用教案

1、5.1 回溯法的基本思想5.2 回溯法的算法框架5.3 n后问题5.4 圆排列问题5.5 电路板排版问题第1页/共28页第一页，共28页。n 回溯法（backtracking）是一种系统地搜索问题解的方法。为实现回溯，首先(shuxin)需要定义一个解空间（solution space），然后以易于搜索的方式组织解空间，最后用深度优先的方法搜索解空间，获得问题的解。n 说话的方式简单点：从一条路往前走，能进则进，不能进则退回来，换一条路再试。第2页/共28页第二页，共28页。3为了避免不必要的搜索，算法搜索至解空间树的任意一点时，先判断先判断该结点是否包该结点是否包含问题的解含问题的解4如果肯

2、定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯1通常将问题的解空间组织成树或图的形式，使得回溯法能方便地搜索整个解空间2在问题的解空间树中，按深度优先策略（或先序遍历，根-左-右顺序），从根结点出发搜索解空间树5否则，进入该子树，继续按深度优先策略搜索搜索(su su)方式内注意：这棵解空间树不是(b shi)遍历前预先建立的，而是隐含在遍历过程中。容第3页/共28页第三页，共28页。定义一个解空间(kngjin)，它包含问题的解用易于搜索的方式组织(zzh)解空间深度优先搜索解空间(kngjin)，获得问题的解。 Ps：利用限界函数避免移动到不可能产生解的子空间。回溯法解题的

3、一个显著特征是在搜索过程中动态产生问题的解空间。第4页/共28页第四页，共28页。单击增加(zngji)标题内容解空间设问题的解向量为：X=(x1,x2,xn) ，xi的取值范围为有穷集Si 。把xi的所有可能取值组合，称为问题的解空间。每一个组合是问题的一个可能解。第5页/共28页第五页，共28页。解空间解空间(kngjin)(kngjin)S=0,1，当n=3时，0/1背包问题的解空间是：(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)当输入规模为n时，有2n种可能的解。0/1背包问题S=1,2,n，当n=3时，

4、 S=1,2,3 ，货郎担问题的解空间是：(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),(3,3,1),(3,3,2),(3,3,3) 当输入规模为n时，它有nn种可能的解。考虑到约束方程xixj。因此，货郎担问题的解空间压缩为：(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)当输入规模为n时，它有n!种可能的解。货郎担(旅行商)问题第6页/共28页第六页，共28页。子集树解空间大小: 2n 排列树解空间大小: n!Add text in here too Add text in here从n个元素

5、的集合S中找出满足某种性质(xngzh)的子集时确定n个元素满足(mnz)某种性质的排列时第7页/共28页第七页，共28页。使目标函数取极值（极大或极小）的可行解，一个或少数几个满足约束条件的解，解空间中的一个子集可行(kxng)解最优解可行(kxng)解和最优解第8页/共28页第八页，共28页。不满足约束条件、目标函数、或其儿子结点已全部搜索完毕的结点、或者叶结点。以死结点作为根的子树，可以在搜索过程中删除所搜索到的结点不是叶结点，且满足约束条件和目标函数的界，其儿子结点还未全部搜索完毕正在搜索其儿子结点的结点，它也是一个活结点当前扩展结点成为死结点时，应往回移动（回溯）至最近的一个活结点处

6、，并使这个活结点成为当前的扩展结点回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解，或解空间中已无活结点时终止第9页/共28页第九页，共28页。从其解空间(kngjin)树的根结点开始搜索其解空间(kngjin)。开始时，根结点A是唯一的活结点，也是当前扩展结点。在当前扩展结点A处，可纵深移至B或C。n=3,w=16,15,15,p=45,25,25,c=30。第10页/共28页第十页，共28页。在当前扩展结点(ji din)A处，可纵深移至B或C。选择先移至B，即选取物品w1，此时，A、B均为活结点(ji din)，B成为当前扩展结点(ji din)。在B处剩余背包容量是r=3

7、0-16=14，获取价值45。从B可纵深移至D或E，先考虑移至D，但现仅有的背包容量容不下物品w2，故移至D导致一个不可行解。而从B移至E不占用背包容量，因而可行。从而我们选择移至E。此时E成为新的扩展结点(ji din)。此时，A、B和E是活结点(ji din)。在E处容量仍为14，所得价值仍为45。从E可以移至J和K。移至J会导致一个不可行解，而移向K是可行的，于是移至K，K成为新的扩展结点(ji din)。由于K是一个叶结点(ji din)，所以我们得到一个可行解(1,0,0),v=45。第11页/共28页第十一页，共28页。由于从K已无法纵深扩展，故K成为一个死结点，所以返回（回溯）至

8、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是叶结点，即获得一可行解，又获取了至今最高价值，因此记录(jl)该可行解。L不可扩展，返回F处。按此方式继续搜索，可搜索遍整个解空间。搜索结束后找到的最好解是相应0-1背包问题的最优解。第12页/共28页第十二页，共28页。避免无效搜索单击增

9、加标题(biot)内容用约束函数在扩展(kuzhn)结点出剪去不满足约束的子树用限界(xinji)函数剪去得不到最优解的子树两类函数通称为剪枝函数第13页/共28页第十三页，共28页。递归回溯(hu s)Void backTrace (int t)If(tn) output(x);elsefor(i=f(n,t);i0) if(f(n,t)=g(n,t)for(i=f(n,t);i=g(n,t);i+)xt=hi;if(constraint(t)&bound(t) if(solution(t)output(x);else t+;else t-;迭代(di di)回溯第15页/共28页第

10、十五页，共28页。在88的棋盘(qpn)上放置8个皇后，使得这8个皇后不在同一行、同一列及同一斜角线上。如图：N后问题(wnt)第16页/共28页第十六页，共28页。剪枝剪枝(jin zh)函数函数8皇后问题可以表示成8元组(x1,x8),其中xi是放在第i行的皇后所在的列号。于是，解空间由8个8元组组成。约束条件：xixj for all i, j |xi-xj| j-i |约束条件之一为没有两个xi相同(即任意(rny)两个皇后不在同一列上)。其二为没有两个皇后在同一斜线上。QQQQQQQQ123456781 2 3 4 5 6 7 8第17页/共28页第十七页，共28页。N后问题主要(z

11、hyo)算法部分boolean place(int k) int i; for (i=1;in) sum+; print(x);elsefor(i=1;in时，算法搜索至叶节点，得到新的圆排列方案。此时算法调用Compute计算(j sun)当前圆排列的长度，适时更新当前最优值。 当i0nowj0且且nowjnowj！=totalj=totalj。用这个条件来。用这个条件来计算插槽计算插槽i i和和i+1i+1间的连线密度。间的连线密度。第25页/共28页第二十五页，共28页。算法算法(sun f)效率效率在解空间排列树的每个节点处，算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。另外，生成排列树需要O(n!)时间。每次更新当前最优解至少(zhsho)使bestd减少1，而算法运行结束时bestd=0。因此最