资源描述：
《《算法设计与分析》第8章1 回溯.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第八章回溯法8.1一般方法8.2n-皇后问题8.3子集和数问题8.4图的着色问题8.5哈密顿环8.60/1背包问题8.7批处理作业调度什么是回溯回溯回溯入口出口回溯迷宫游戏什么是回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法回溯法是以深度优先的方式系统地搜索问题的解,它适用于解一些组合数较大的问题。回溯为什么回溯？回溯(Trackback)是什么？怎样回溯？WhatWhyHow应用回溯法解问题时,首先应该明确问题的解空间一个复杂问题的解决方案可以看作是由若干个小的决策组成的,这些决策构成一个决
2、策序列。解决一个问题的所有可能的决策序列就构成了该问题的解空间。解空间中满足约束条件的决策序列称为可行解。在约束条件下使目标达到最优的可行解称为该问题的最优解。通常将解空间画成树的形状,称为解空间树回溯法的基本概念回溯算法求解问题的类型同贪心算法和动态规划算法求解的问题类型相似，问题的解可以表示成一个n维向量，一般地，每个分量有两个或有限多个取值，而且它的取值要满足某个事先给定的约束条件。所有可能的取值的组合构成问题的解向量空间，简称解空间。由于一个解向量往往对应问题的某个状态，所以解空间又称为问题的
3、状态空间。一般情况下，问题的解仅是问题解空间的一个子集，要求此子集对应的解必须满足问题的约束条件，满足约束条件的一组取值称为问题的一个可行解，使目标函数取最大或最小值的可行解称为最优解。回溯法在求问题的所有解时,要回溯到根结点,且根结点的所有子树都已被搜索过才结束。回溯法在求问题的任一解时,只要搜索到问题的一个解就可以结束。回溯法在包含问题所有解的解空间树中,按深度优先的策略,从根结点出发搜索解空间树。回溯法搜索至解空间树的任一结点时,先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过以该结点
4、为根的子树,逐层向其祖先结点回溯。否则就进入该子树,继续按深度优先的策略进行搜索。回溯法的基本概念问题的解可以用一个n元组(x1,…,xn)来表示，其中的xi取自于某个有穷集Si,并且这些解必须使得某一限界函数B(x1,…,xn)取极值。不断地用修改过的限界函数Bi(x1,…,xn)去测试正在构造的n元组的部分向量,看是否可能导致最优解,如果不能,就将可能要测试的mi+1…mn个向量略去。回溯法的解需要满足一组综合的约束条件,通常分为:显式约束和隐式约束显式约束条件:限定每个x只从一个给定的集合上取值
5、,满足显式约束的所有元组确定一个可能的解空间例:xi>=0,si={所有非负实数}隐式约束条件:描述了xi必须彼此相关的情况回溯法的基本概念回溯法的基本思想通过部分解向量逐步增加可行分量来求出解向量。对于一个解向量，假设已经构造得到问题的部分解向量(x1,x2,…,xk)，在部分解向量的基础上，考虑第k+1个分量xk+1的一个取值，可能遇到下面的两种情况：(1)部分解向量加入xk+1仍满足约束条件，那么以为基础继续添加新的分量；(2)否则，那么就要考察xk+1的另外一个取值，如果对xk+1的所有取值，
6、都不满足约束条件，那么就回溯到xk，即选取xk的另一个取值，同上考察部分解向量。从k=1开始，逐步扩展部分解(x1,x2,…,xk)，就是回溯求解的过程。如何表示解空间？树结构已有成熟的搜索算法，因此可以利用树结构表示问题的解空间。例:4-皇后问题在一个4*4棋盘上放4个皇后,使每两个皇后之间都不能互相“攻击”,即使得每两个皇后都不能在同一行、同一列及同一条斜线上。4皇后问题可以表示为4-元组(x1,…,x4)，其中xi是放置皇后i所在的列号。显式约束条件:si={1,2,3,4},1≤i≤4隐式约束
7、条件:没有两个xi可以相同,且没有两个皇后可以在同一条斜线上Q1Q2Q3Q4145674334101112942421415161732322021222343432526272841143031323331133813341924291342183450342………4-皇后问题的解空间树x1=1x2=2问题描述:已知n+1个正数:wi(1≤i≤n)和M,要求找出wi的和数是M的所有子集。例:n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31满足要求的子集是(11,13,7)和(2
8、4,7)用wi的下标来表示解向量更为方便,因此这两个解向量可以表示为:(1,2,4)和(3,4)显式约束条件:xi∈{j
9、j是wi的下标值,1≤j≤n}隐式约束条件:要求没有两个xi是相同的,且相应的wi的和数等于M为避免产生同一个子集的重复情况(如(1,2,4)和(1,4,2)),附加一个隐式约束条件:xi≤xi+1,1≤j≤n例:子集和数问题12345678910111213141516x2=2x2=3x2=4x2=3x2=4x2=4x1=1x1=2
