资源描述：
《回溯搜索算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、补充22回溯法ò理解回溯法的深度优先搜索策略。ò掌握用回溯法解题的算法框架（1）递归回溯（2）迭代回溯（3）子集树算法框架（4）排列树算法框架ò通过应用范例学习回溯法的设计策略。1算法导论Sch2-1方法概述ò搜索算法介绍（1）穷举搜索（2）盲目搜索—深度优先(DFS)或回溯搜索(Backtracking);—广度优先搜索(BFS);—分支限界法(Branch&Bound)(Branch&Bound)；—博弈树搜索(α-βSearch)（3）启发式搜索—A*算法和最佳优先(Best-FirstSearch)—迭代加深的A*算法—B*,AO*
2、,SSS*等算法—LocalSearch,GA等算法2算法导论Sch2-1方法概述ò搜索空间的三种表示：—表序表示：搜索对象用线性表数据结构表示；—显示图表示：搜索对象在搜索前就用图（树）的数据结构表示；—隐式图表示：除了初始结点，其他结点在搜索过程中动态生成。缘于搜索空间大，难以全部存储。ò搜索效率的思考：随机搜索—上世纪70年代中期开始，国外一些学者致力于研究随机搜索求解困难的组合问题，将随机过程引入搜索；—选择规则是随机地从可选结点中取一个，从而可以从统计角度分析搜索的平均性能；—随机搜索的一个成功例子是：判定一个很大的数是不是素数，
3、获得了第个多式时第一个多项式时间的算法算法。3算法导论Sch2-1方法概述ò回溯法：—回溯法是一个既带有系统性又带有跳跃性的搜索算法；—它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。——系统性—算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续深度优先的策略进行搜索。——跳跃性—这种以深度优先的方式系统地搜索问题的解得算法称为回溯法，它适用于解一些组合数较大的问题。4算法导论Sch2-1方法概述ò
4、问题的解空间—问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x,x,…,x)12n的形式。—显约束：对分量x的取值限定。i—隐约束：为满足问题的解而对不同分量之间施加的约束。—解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。n=3时的0-1背包问题用完全二叉树表示的解空间5算法导论Sch2-1方法概述6算法导论Sch2-1方法概述ò基本思想：—搜索从开始结点（根结点）出发，以深度优先搜索
5、整个解空间。—这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索索移向纵深方向移至一个新新结点。这这新个新结点就成成新为新的活结点，并成为当前扩展结点。—如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。—此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直到找到一个解或全部解。7算法导论Sch2-1方法概述ò基本步骤：①针对所给问题，定义问题的解空间；②确定易于搜索的解空间结构；③以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数：①用约
6、束函数在扩展结点处剪去不满足约束的子树；②用限界函数剪去得不到最优解的子树。8算法导论Sch2-1方法概述ò二类常见的解空间树：①子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有2n个叶子结点，其总结点个数为2n+1-1，遍历子集树时间为Ω(2n)。如0-1背包问题，叶结点数为2n，总结点数2n+1；②排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶子结点，因此，遍历排列树需要Ω(n!)的计算时间。如TSP问题，叶结点数为n!，遍历
7、时间为Ω(n!)。9算法导论Sch2-1方法概述例1[0-1背包]：n=3,w=(16,15,15),v=(45,25,25),c=30(1)定义解空间：X={(0,0,0),(0,0,1),(0,1,0),…,(1,1,0),(1,1,1)}(2)构造解空间树：10算法导论Sch2-1方法概述11算法导论Sch2-1方法概述ò例2[TSP问题]:（1）定义解空间：X={12341,12431,13241,13421,14231,14321}（2）构造解空间树：（3）从A出发按DFS搜索整棵树：最优解：13241，14231成本：2512算
8、法导论Sch2-1方法概述ò用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长
