资源描述：
《《计算机算法设计与分析》PPT第五章 回溯法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章回溯法1学习要点理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架（1）递归回溯（2）迭代回溯（3）子集树算法框架（4）排列树算法框架2通过应用范例学习回溯法的设计策略（1）装载问题（2）批处理作业调度（3）符号三角形问题（4）n后问题（5）0-1背包问题（6）最大团问题（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题3搜索算法介绍（1）穷举搜索（2）盲目搜索—深度优先(DFS)或回溯搜索(Backtracking);—广度优先搜索(B
2、FS);—分支限界法(Branch&Bound)；—博弈树搜索(α-βSearch)（3）启发式搜索—A*算法和最佳优先(Best-FirstSearch)—迭代加深的A*算法—B*,AO*,SSS*等算法—LocalSearch,GA等算法4搜索空间的三种表示表序表示搜索对象用线性表数据结构表示；显示图表示搜索对象在搜索前就用图（树）的数据结构表示；隐式图表示除了初始结点，其他结点在搜索过程中动态生成。缘于搜索空间大，难以全部存储。5回溯法有许多问题，当需要找出它的解集或者要求回答什么解是满足
3、某些约束条件的最优解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法有“通用解题法”之称。6回溯法回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意结点时，先判断该结点是否包含问题的解。若肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先搜索策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树
4、都被搜索遍才结束。在它求问题的一个解时，只要搜索到问题的一个解就结束。回溯法：以深度优先方式系统搜索问题解的算法，它适用于求解组合数较大的问题。7回溯法既有系统性又有跳跃性它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。——系统性算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续深度优先的策略进行搜索。——跳跃性85.1回溯法的算法框架5.1.1问题的解
5、空间复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间应该包括所有的可能解，也就是进行穷举的搜索空间。确定正确的解空间很重要。如果没有确定正确的解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。9例：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。10对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。11例：有n个物品的0-1背包问题，其可能解的表示方式有两种。（1）可能解由一个不等长向量组成当物品i(1≤i≤n)装入背包时，解向
6、量中包含分量i，否则，解向量中不包含分量i。当n=3时，其解空间：{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}（2）可能解由一个等长向量{x1,x2,…,xn}组成xi=1(1≤i≤n)表示物品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)}12为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示
7、为满足某个约束条件的等长向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范围是某个有限集合Si={ai1,ai2,…,airi}。所有可能的解向量构成了问题的解空间。13问题的解空间一般用解空间树（SolutionSpaceTrees,也称状态空间树）的方式组织。树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果。依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。14
8、15两类常见的解空间树①子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有2n个叶子结点，其总结点个数为2n+1-1，遍历子集树时间为Ω(2n)。例：0-1背包问题 叶结点数为2n，总结点数2n+1-1；②排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶子结点，遍历排列树需要Ω(n!)的计算时间。例：TSP问题 叶结点数为n!，遍历时间为Ω(n!)。16对于n=3的0/1背包问题，其解空间
