计算机算法设计与分析第5章课件

《计算机算法设计与分析第5章课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析第5章回溯法5.1概述5.2图问题中的回溯法5.3组合问题中的回溯法5.4回溯法的时间性能算法设计与分析5.1概述回溯法（backtrackmethod）就是一种有组织的系统化搜索技术，可以看作是穷举搜索的改进。穷举搜索首先生成问题的可能解，然后再去评估可能解是否满足约束条件。而回溯法每次只构造可能解的一部分，然后评估这个部分解，如果这个部分解有可能导致一个完整解，则对其进一步构造，否则就不必继续构造这个部分解了。回溯法常常可以避免搜索所有的可能解，所以，它适用于求解组合数量较大的问题。算法设计与分析5.1概述5.1.1问题的解空间5

2、.1.2解空间树的动态搜索（1）5.1.3回溯法的求解过程算法设计与分析5.1.1问题的解空间复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。确定正确的解空间很重要，如果没有确定正确的解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。算法设计与分析5.1.1问题的解空间例如：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。(a)二维搜索空间无解(b)三维搜索空间的解算法设计与分析5.1.1问题的解空间几个概念：►问题的解向量：回溯法将一个问

3、题的解表示成一个n元式(x,x,…,x)的形式。12n►显约束：对分量x的取值限定，即x(1≤i≤n)的ii取值范围是某个有限集合S={a,a,…,a}。ii1i2iri►解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，即所有可能的解向量构成了问题的解空间。►隐约束：为满足问题的解而对不同分量之间施加的约束。(比如0-1背包问题中各物品重量之和不超过背包容量c)算法设计与分析5.1.1问题的解空间对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。例如，对于有n个物品的0/1背包问题，设计其解的表示方式（1）可能解

4、由一个不等长向量组成当物品i(1≤i≤n)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是：{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}（2）可能解由一个等长向量{x,x,…,x}组成12n其中x=1(1≤i≤n)表示物品i装入背包，x=0表示物品i没有ii装入背包，当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)}算法设计与分析5.1.1问题的解空间例如：n个城市的TSP

5、问题，将其可能解表示为向量X=(x,x,…,x)，其中分量x（1≤i≤n）的12ni取值范围S={1，2，…，n}，并且解向量必须满足约束条件x≠x（1≤i，j≤n）。ij当n=3时，TSP问题的解空间为：{(1，2，3)，(1，3，2)，(2，1，3)，(2，3，1)，(3，1，2)，(3，2，1)}算法设计与分析5.1.1问题的解空间►解空间树问题的解空间一般用解空间树（SolutionSpaceTrees,也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第

6、2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。算法设计与分析5.1.1问题的解空间对于n=3的0/1背包问题，解向量为(x,x,x)。123其解空间树如下图所示，树中的8个叶子结点分别代表该问题的8个可能解。110对物品1的选择291010对物品2的选择36101310101010对物品3的选择4578111214150/1背包问题的解空间树算法设计与分析5.1.1问题的解空间对于n=4的TSP问题，解向量为(x,x,x,x)，表示路径1234为x→x→x→x→x的一个可能解。12341其解

7、空间树如下图所示，树中的24个叶子结点分别代表该问题的24个可能解，例如结点5代表一个可能解，路径为1→2→3→4→1，长度为各边代价之和。TSP问题的114解空间树23218342423413412412338131924293540455055603424323414132414123213124691114162022252730323638414346485153565861634342234341314241212331215710121517212326283133373942444749525457596264算法设计与分析5.1.2

8、解空间树的动态搜索（1）★回溯法的基本思想回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至