资源描述：
《天津科技大学算法设计与分析第8章回溯法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第8章回溯法8.1概述8.2图问题中的回溯法8.3组合问题中的回溯法9/2/20211算法设计与分析--回溯法8.1概述8.1.1问题的解空间8.1.2解空间树的动态搜索（1）8.1.3回溯法的求解过程8.1.4回溯法的时间性能9/2/20212算法设计与分析--回溯法复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。8.1.1问题的解空间确定正确的解空间很重要，如果没有确定正确的解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。9/2/20213算法设计与分析--回溯法(a
2、)二维搜索空间无解(b)三维搜索空间的解图8.1错误的解空间将不能搜索到正确答案例如：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。9/2/20214算法设计与分析--回溯法对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。例如，对于有n个物品的0/1背包问题，其可能解的表示方式可以有以下两种：（1）可能解由一个不等长向量组成，当物品i(1≤i≤n)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是：{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}（2）可能解由一个
3、等长向量{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)}9/2/20215算法设计与分析--回溯法为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范围是某个有限集合Si={ai1,ai2,…,airi}，所有可能的解向量构成了问题的解空间。9/2/20
4、216算法设计与分析--回溯法问题的解空间一般用解空间树（SolutionSpaceTrees,也称状态空间树）的方式组织。树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。9/2/20217算法设计与分析--回溯法对于n=3的0/1背包问题，其解空间树如图所示，树中的8个叶子结点分别代表该问题的8个可能解。对物品1的选择对物品3的选择对物品2的选择11111100000001123457811121415
5、310699/2/20218算法设计与分析--回溯法对于n=4的TSP问题，其解空间树如图所示，树中的24个叶子结点分别代表该问题的24个可能解，例如结点5代表一个可能解，路径为1→2→3→4→1，长度为各边代价之和。243422343413142412123312134131312321214241434322434123124134图8.3n=4的TSP问题的解空间树5710121517212326283133373942444749535558606365469111416202225273032363841434648525457596264381319242
6、9354045515661218345011234349/2/20219算法设计与分析--回溯法8.1.2解空间树的动态搜索（1）回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。9/2/202110算法设计与分析--回溯法例如，对于n=3的0/1背包问题，三个物品的重量为{20,
7、15,10}，价值为{20,30,25}，背包容量为25，从图所示的解空间树的根结点开始搜索，搜索过程如下：1不可行解价值=20价值=55价值=30价值=25价值=01111000000112811121415131069不可行解9/2/202111算法设计与分析--回溯法再如，对于n=4的TSP问题，其代价矩阵如下所示，C=∞36712∞2886∞2376∞图8.5TSP问题的代价矩阵9/2/202112算法设计与分析--回溯法2344221231341313123212142414322434123124134图8.6TSP问题的搜索空间5475
