算法设计与分析回溯.pptx

《算法设计与分析回溯.pptx》由会员分享，可在线阅读，更多相关《算法设计与分析回溯.pptx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、其祖先结点回溯1通常将问题的解空间组织成树或图的形式，使得回溯法能方便地搜索整个解空间2在问题的解空间树中，按深度优先策略（或先序遍历，根-左-右顺序），从根结点出发搜索解空间树5否则，进入该子树，继续按深度优先策略搜索搜索方式内注意：这棵解空间树不是遍历前预先建立的，而是隐含在遍历过程中。容第3页/共28页定义一个解空间，它包含问题的解用易于搜索的方式组织解空间深度优先搜索解空间，获得问题的解。Ps：利用限界函数避免移动到不可能产生解的子空间。回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。第4页/共28页单击增加标题内容解空间设问题的解向量为：X=(x1,x2,xn)，xi的取

3、值范围为有穷集Si。把xi的所有可能取值组合，称为问题的解空间。每一个组合是问题的一个可能解。第5页/共28页解空间解空间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时，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种可能的解。考虑到

4、约束方程xixj。因此，货郎担问题的解空间压缩为：(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)当输入规模为n时，它有n!种可能的解。货郎担(旅行商)问题第6页/共28页子集树解空间大小:2n排列树解空间大小:n!AddtextinheretooAddtextinhere从n个元素的集合S中找出满足某种性质的子集时确定n个元素满足某种性质的排列时第7页/共28页使目标函数取极值（极大或极小）的可行解，一个或少数几个满足约束条件的解，解空间中的一个子集可行解最优解可行解和最优解第8页/共28页不满足约束条件、目标函数、或其儿子结点已全部搜索完毕的结

5、点、或者叶结点。以死结点作为根的子树，可以在搜索过程中删除所搜索到的结点不是叶结点，且满足约束条件和目标函数的界，其儿子结点还未全部搜索完毕正在搜索其儿子结点的结点，它也是一个活结点当前扩展结点成为死结点时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解，或解空间中已无活结点时终止第9页/共28页从其解空间树的根结点开始搜索其解空间。开始时，根结点A是唯一的活结点，也是当前扩展结点。在当前扩展结点A处，可纵深移至B或C。n=3,w=16,15,15,p=45,25,25,c=30。第10页/共28页在当前扩

6、展结点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。第11页/共28页由于从K已无法纵

7、深扩展，故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背包问题的最优解。第12页/共28页

8、避免无效搜索单击增加标题内容用约束函数在扩展结点出剪去不满足约束的子树用限界函数剪去得不到最优解的子树两类函数通称为剪枝函数第13页/共28页递归回溯递归回溯VoidbackTrace(intt)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);elset+;elset-;迭代回溯第15页/共28页在88的棋盘上放置8个皇后，使得这8个皇后不在同一行、同一列及同一斜角线上。如图：N后

9、问题第16页/共28页剪枝函数剪枝函数8皇后问题可以表示成8元组(x1,x8),其中xi是放在第i行的皇后所在的列号。于是，解空间由8个8元组组成。约束条件：xixjforalli,j|xi-xj|j-i|约束条件之一为没有两个xi相同(即任意两个皇后不在同一列上)。其二为没有两个皇后在同一斜线上。QQQQQQQQ123456781 2 3 4 5 6 7 8第17页/共28页N后问题主要算法部分booleanplace(intk)inti;for(i=1;in)sum+;print(x);elsefor(i=1;in时，算法搜索至叶节点，得到新的圆排列方案。此时算法调用Compute计算当前

10、圆排列的长度，适时更新当前最优值。当i0nowj0且且nowjnowj！=totalj=totalj。用这个条件来。用这个条件来计算插槽计算插槽i i和和i+1i+1间的连线密度。间的连线密度。第25页/共28页算法效率算法效率在解空间排列树的每个节点处，算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。另外，生成排列树需要O(n!)时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd=0。因此最优解被更新的额次数为O(m)。更新最优解需要O(mn)时间。综上，解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)。第26页/共28页谢谢侬谢谢侬编曲：吴瑞峰填词：吴瑞峰演唱：Eason第27页/共28页感谢您的观看！第28页/共28页