第8章 回溯法.ppt
《第8章 回溯法.ppt》由会员分享,可在线阅读,更多相关《第8章 回溯法.ppt(40页珍藏版)》请在麦多课文档分享上搜索。
1、第8章 回溯法,回溯法概述,回溯法可以系统的搜索一个问题的所有解或任一个解 它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索到某一结点时,如果断定该结点肯定不包含问题的解,则跳过以该结点为根的子树的搜索,逐层向其祖先结点回溯 这种以深度优先方式搜索问题的解的方法称为回溯法,可用回溯法求解的问题,问题的解可以用一个n元组(x1,xn)来表示,其中的xi取自于某个有穷集Si,并且这些解必须使得某一规范函数P(x1,xn)(也称限界函数)取极值或满足该规范函数条件。 例子:A(1:n)个元素的分类问题 问题的解为n元组; xi取自有穷集; 规范函数P:A(xi
2、)=A(xi+1),问题求解的方法,硬性处理法 列出所有候选解,逐个检查是否为所需要的解 理论上,候选解数量有限,并且通过检查所有或部分候选解能够得到所需解时,上述方法可行 实际中则很少使用,因为候选解的数量通常都非常大(比如指数级,甚至是大数阶乘),即便采用最快的计算机也只能解决规模较小的问题。 回溯或分枝限界法 避免对很大的候选解集合进行完全检查 大大减少问题的求解时间 通常用来求解规模较大的问题,回溯法思想,第一步:为问题定义一个状态空间(state space),这个空间必须至少包含问题的一个解 第二步:组织状态空间以便它能被容易地搜索。典型的组织方法是图或树 第三步:按深度优先的方法
3、从开始结点进行搜索 开始结点是一个活结点(也是 E-结点:expansion node) 如果能从当前的E-结点移动到一个新结点,那么这个新结点将变成一个活结点和新的E-结点,旧的E-结点仍是一个活结点。 如果不能移到一个新结点,当前的E-结点就“死”了(即不再是一个活结点),那么便只能返回到最近被考察的活结点(回溯),这个活结点变成了新的E-结点。 当我们已经找到了答案或者回溯尽了所有的活结点时,搜索过程结束。,回溯法如何提高效率?,由开始结点到当前E-结点构成解向量(x1,xi) 如果判定(x1,xi)不能导致最优解,那么就将可能要测试的mi+1mn个向量略去。 因此回溯法的测试次数比硬性
4、处理作的测试次数要少得多。如何判定(x1,xi)能否导致最优解?,约束条件,回溯法的解需要满足一组综合的约束条件,通常分为:显式约束和隐式约束 显式约束条件限定每个xi只从一个给定的集合上取值,例如: xi=0 即si=所有非负实数 xi=0或xi=1 即 si=0,1 l=xi=u 即si=a:l=a=u 满足显式约束的所有元组确定一个可能的解空间 隐式约束描述了xi必须彼此相关的情况,如0/1背包问题中的背包重量M,回溯法求解的经典问题(1) 8-皇后问题,在一个8*8棋盘上放置8个皇后,且使得每两个之间都不能互相“攻击”,也就是使得每两个都不能在同一行、同一列及同一条斜角线上。 8皇后问
5、题的解可以表示为8-元组(x1,x8) ,其中其中xi是第i行皇后所在的列号。 显式约束条件是xi=1,2,3,4,5,6,7,8, 1i8 隐式约束条件是,没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。,1 2 3 4 5 6 7 8,1 2 3 4 5 6 7 8,由于解向量之间不能相同,所以解空间的大小由88个元组减少到8!个元组。上图中的解表示为一个8-元组即(4,6,8,2,7,1,3,5)。,回溯法求解的经典问题(2) 子集和数问题,已知(w1, w2, , wn)和M,均为正数。要求找出wi的和数等于M的所有子集。例如:若n=4,(w1,w2,w3,w4)=(11,13
6、,24,7),M=31,则满足要求的子集是(11,13,7)和(24,7). 子集和数问题解的一种表示方法 若用Wi的下标表示解向量,这两个解向量为(1,2,4)和(3,4)。 子集和数问题的解可以表示为k-元组(x1, x2, , xk), 1kn并且不同的解可以是大小不同的元组。 显式约束条件是xij|j为整数且1jn。 隐式约束条件是 1)没有两个xi是相同的; 2)wxi的和为M; 3)xixi1,1in(避免产生同一个子集的重复情况),子集和数问题解的另一种表达,解由n-元组(x1, x2, , xn)表示; 显式约束条件xi0,1 ,1in,如果没有选择Wi,则xi=0;如果选择了
7、Wi,则xi=1。于是上面的解可以表示为(1,1,0,1)和(0,0,1,1); 隐式约束条件(xi wi)的和数为M解空间的大小为2n个元组,解空间的树结构,回溯算法通过系统地检索给定问题的解空间来确定问题的解。这检索可以用这个解空间的树结构来简化。 为了便于讨论,引进一些关于解空间树结构的术语。 问题状态(problem state):树中的每一个结点确定所求解问题的一个问题状态。 状态空间(state space):由根结点到其它节点的所有路径则确定了这个问题的状态空间。 解状态(solution states):解状态是这样一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这解
8、空间中的一个元组。 答案状态(answer states):对于这些解状态而言,由根到S的这条路径确定了这问题的一个解(即,它满足隐式约束条件)。 状态空间树(state space tree):解空间的树结构。,静态树:树结构与所求问题的实例无关,结构不变的解空间树动态树: 树结构是动态变化的,与所求问题有关。即,具体问题的数据发生变化,空间树的结构也会发生变化。 组织空间树就是根据元组的特点构造解空间,组织解空间(1),4-皇后问题解空间的树结构(解空间由从根结点到叶结点的所有路径所定义),n-皇后问题的状态空间树?,组织解空间(2),子集和数问题,解空间由树中的根结点到任何结点的所有路径
9、所确定,这些可能的路径是( )(这对应于由根结点到他自身的那条路径);(1);(1,2);(1,2,3);(1,2,3,4);(1,2,4);(1,3,4);(1,4);(2);(2,3)等等,组织解空间(3),子集和数问题,解空间由根结点到叶结点的所有路径确定,状态空间树,对于任何一个问题,一旦设想出一种状态空间树,那么就可以先系统地生成问题状态,接着确定这些问题状态中的哪些是解状态,最后确定哪些解状态是答案状态从而将问题解出 生成问题状态的两种方法便于问题的描述,给出以下概念: 活结点:自己已经生成而其所有的儿子结点还没有全部生成的结点。 E-结点(正在扩展的结点):当前正在生成其儿子结点
10、的活结点。 死结点:不再进一步扩展或者其儿子结点已全部生成的生成结点。,生成问题状态的两种方法,在第一种方法中,当前的E-结点R一旦生成一个新的儿子C,这个儿子结点就变成一个新的E-结点,当完全检测了子树C之后,R结点就再次成为E-结点。这相当于问题状态的深度优先生成。在第二种状态生成方法中,一个E-结点一直保持到变成死结点为止。在这两种方法中,将用限界函数去杀死还没有全部生成其儿子结点的那些活结点。回溯法:使用限界函数的深度优先结点生成方法。 分枝-限界方法:E-结点一直保持到死为止的状态生成方法。,4-皇后问题-回溯解,1 2 3 4,1234,4-皇后问题回溯期间生成的树,上图显示了在4
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章回 PPT
