算法设计与分析回溯.pptx

单击增加标题内容对于许多问题，当需要找出问题的所有解或者找出满足某些约束条件的（最优）解时，往往要使用回溯法。回溯算法应用领域圆排列问题N后问题0-1背包电路板排版问题回溯法有“通用的解题法通用的解题法”之称。5.1回溯法的回溯法的基本思想基本思想5.2回溯法的回溯法的算法框架算法框架5.3n后问题后问题5.4圆排列问题圆排列问题5.5 电路板排版问题n回溯法（回溯法（backtracking）是一种系统地搜）是一种系统地搜索问题解的方法。为实现回溯，首先需要索问题解的方法。为实现回溯，首先需要定义一个解空间（定义一个解空间（solutionspace），然），然后以易于搜索的方式组织解空间，最后用后以易于搜索的方式组织解空间，最后用深度优先的方法搜索解空间，获得问题的深度优先的方法搜索解空间，获得问题的解。解。n说话的方式简单点：说话的方式简单点：从一条路往前走，能从一条路往前走，能进则进，不能进则退回来，换一条路再试。进则进，不能进则退回来，换一条路再试。3为了避免不为了避免不必要的搜索，必要的搜索，算法搜索至算法搜索至解空间树的解空间树的任意一点时，任意一点时，先判断该结先判断该结点是否包含点是否包含问题的解问题的解4如果肯定不如果肯定不包含，则跳包含，则跳过对该结点过对该结点为根的子树为根的子树的搜索，逐的搜索，逐层向其祖先层向其祖先结点回溯结点回溯1通常将问题通常将问题的解空间组的解空间组织成树或图织成树或图的形式，使的形式，使得回溯法能得回溯法能方便地搜索方便地搜索整个解空间整个解空间2在问题的解在问题的解空间树中，空间树中，按深度优先按深度优先策略（或先策略（或先序遍历，根序遍历，根-左左-右顺序），右顺序），从根结点出从根结点出发搜索解空发搜索解空间树间树5否则，进入否则，进入该子树，继该子树，继续按深度优续按深度优先策略搜索先策略搜索搜索方式搜索方式内注意：这棵解空间树不是遍历前预先建立的，而是隐含在遍历过程中。容定义一个解空间，它包含问题的解用易于搜索的方式组织解空间深度优先搜索解空间，获得问题的解。Ps：利用限界函数避免移动到不可能产生解的子空间。回溯法解题的一个显著特征回溯法解题的一个显著特征是在搜索过程中动态产生问是在搜索过程中动态产生问题的解空间。题的解空间。单击增加标题内容解空间设问题的解向量为：X=(x1,x2,xn)，xi的取值范围为有穷集Si。把xi的所有可能取值组合，称为问题的解空间。每一个组合是问题的一个可能解。解空间解空间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,11),(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!种可能的解。货郎担(旅行商)问题子集树解空间大小:2n排列树解空间大小:n!AddtextinheretooAddtextinhere从从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背包问题的最优解。避免无效搜索单击增加标题内容用约束函数在扩展结点出剪去不满足约束的子树用限界函数剪去得不到最优解的子树两类函数通称为剪枝函数两类函数通称为剪枝函数递归回溯递归回溯递归回溯递归回溯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-;迭代回溯迭代回溯在88的棋盘上放置8个皇后，使得这8个皇后不在同一行、同一列及同一斜角线上。如图：N后问题剪枝函数剪枝函数8皇后问题可以表示成8元组(x1,x8),其中xi是放在第i行的皇后所在的列号。于是，解空间由8个8元组组成。约束条件：xixjforalli,j|xi-xj|j-i|约束条件之一为没有两个xi相同(即任意两个皇后不在同一列上)。其二为没有两个皇后在同一斜线上。QQQQQQQQ123456781 2 3 4 5 6 7 8N后问题主要算法部分booleanplace(intk)inti;for(i=1;in)sum+;print(x);elsefor(i=1;in时，算法搜索至叶节点，得时，算法搜索至叶节点，得到新的圆排列方案。此时算法调用到新的圆排列方案。此时算法调用Compute计算当前圆排列计算当前圆排列的长度，适时更新当前最优值。的长度，适时更新当前最优值。当当i0nowj0且且nowjnowj！=totalj=totalj。用这个条件来。用这个条件来计算插槽计算插槽i i和和i+1i+1间的连线密度。间的连线密度。算法效率算法效率在解空间排列树的每个节点处，算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。另外，生成排列树需要O(n!)时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd=0。因此最优解被更新的额次数为O(m)。更新最优解需要O(mn)时间。综上，解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)。谢谢侬谢谢侬编曲：吴瑞峰填词：吴瑞峰演唱：Eason