空间复杂度分析 运行数据 主要由两个因素决定, 已知 算法的输入,输出和运行中的临时数据 nn=8,M=110 占用空间显然为on W=(111212333434555) ■递归过程所用的栈空间, P=(11213133435355,65) 由于递归调用是不断调用和退出的过程,递 归层数不可能超过状态空间树的高度n,而 每一层调用占用的空间为常数,故空间代价 最终结果:11101100 maxvalue 159 运行实例分析 耳 这个问题的状态 有511个结点,其中 256个叶结点(可能解 实际搜索最优解只涉及到27结点,其中4个叶 结点 行,即当某结点的左子树搜结束,转到其右 子结点时 (其中15次展开)。 幽 没有必要两个分支都判断 右分支剪比左分支效果好(仅左,需要330) 理种中 解为结点44bp=159,(11101100) 更大的例子 的 基本回溯小结 回濒适应于求解组合搜索问题(组合优化问题 O, MAX WEIGHT= 解示般用树表示 7160387}73467505}{816577} 解向量,解的过程是不断扩充解向量的过程 320475》1103828 180,1198} 回溯口诀 37973160}22925940》{18351807}{7734208 能进则进,不能进则换,不能换则退 回溯条件 搜索问题--约束条件 增需: 97151个蜡点 ■优化问题一的束条件+限界函数 算法复杂性 適历搜树的时间,最坏情况为指数 空间代价小
回溯算法 31 空间复杂度分析 主要由两个因素决定， 算法的输入，输出和运行中的临时数据 占用空间显然为O(n) 递归过程所用的栈空间， 由于递归调用是不断调用和退出的过程，递 归层数不可能超过状态空间树的高度n，而 每一层调用占用的空间为常数，故空间代价 为O(n) 回溯算法 32 运行数据 已知 n=8, M=110, W=(1,11,21,23,33,43,45,55), P=(11,21,31,33,43,53,55,65) 回溯算法 33 0 0 1 89 139 6 56 96 5 33 63 4 12 32 3 1 11 2 89 139 164.7 14 89 139 163.8 18 89 139 139 20 n=8, M=110 W=(1,11,21,23,33,43,45,55) P=(11,21,31,33,43,53,55,65) 编号为全序DFS周游完全二叉树 紫色值为超重剪左支 蓝色为估计BP值 99 149 162 26 99 149 22 56 96 162.4 21 99 149 149 28 56 96 161.6 29 101 151 30 101 151 151 32 66 106 37 33 63 160.2 36 66 106 159.8 45 109 159 159 44 109 159 42 109 159 38 66 106 158 49 33 63 157.6 52 35 65 68 12 32 159.8 67 68 108 69 68 108 157.6 81 68 108 159.3 77 35 65 157.1 84 12 32 154.9 99 1 11 157.4 130 0 0 155.1 257 最终结果： 11101100 maxValue = 159 56 96 159.8 33 56 96 96 35 132 134 144 144 154 156 111 154 164 111 111 113 回溯算法 34 运行实例分析 这个问题的状态空间树有511个结点，其中 256个叶结点（可能解） 实际搜索最优解只涉及到27结点，其中4个叶 结点 计算限界函数bound()只是在每次回溯时进 行，即当某结点的左子树搜索结束，转到其右 子结点时，计算bound()值，共需计算23次 （其中15次展开）。 没有必要两个分支都判断 右分支剪比左分支效果好（仅左，需要330） 解为结点44, bp=159, (11101100) 回溯算法 35 更大的例子 n =20, MAX_WEIGHT = 20000 WV wv[20] = { {52,7946},{7160,387},{7346,7505},{816,577}, {961,6021},{5262,8278},{4163,931},{1003,9738}, {7914,1683},{320,475},{1103,8280},{6180,1198}, {1334,2791},{5812,2608},{6930,5515},{4451,9602}, {3797,3160}, {2292,5940},{1835,1807},{773,4208} }; 总2097151个结点 剪左：121049 剪右：34 maxValue: 65188, 回溯算法 36 基本回溯小结 回溯适应于求解组合搜索问题(组合优化问题) 解空间一般用树表示 解的表示 解向量，解的过程是不断扩充解向量的过程 回溯口诀 能进则进，不能进则换，不能换则退 回溯条件 搜索问题---约束条件 优化问题---约束条件+限界函数 算法复杂性 遍历搜索树的时间，最坏情况为指数 空间代价小
高级回溯讨论 估计回溯算法的平均效率 确定子结点的排列规则 计数搜索树中平均遍历的结点 子集树和排列树 Monte carlo方法 装载问题(01背包)问厦都是子集树 1.从根开始,随机选择一条路经,直到不能分 皇后问题与旅行售货员问题是排列树 依次对x赋值 估计回溯算法的平均效率 的值是从当时的5中随机选取,直到向量不能 张为止 判断是否满足多米诺性质 2.假定搜索树的其他|5-1个分支与以上随机选 ■搜索策略-深度优先 出的路径一样,计数搜索树的点数。 确定每个结点能够分支的约束条件 3.重复步骤1和2,将结点数进行概率平均 ■确定存储搜索路径的数据结构 算法 计算结点数 Monte carlo m为本次取样结点总数,k为层数,八为本层分支数 n2为上层分支数,为树的层数 2. for i 1 to t do ∥取样次数 m=1;r2=1;k=1 While k<=n do m= Estimate(n)∥m为本次结总数 3 if sk= then return m 5. sum/= t ←随机选择sk的元素 回滴算法 例 Monte Carlo方法估计四后问题的效率 必要条件一多米诺性质 case3.<1,3>:1+4X1+4X2=13 假设4抽样测试:case11次,case21次,cse32次,平均为16 设尺(x1,2,…,)为真表示向量<x1,x2,…,加中个皇 解空间的蝻点败为17 后放量在彼此不能攻击的位 M+1)→尺Ⅺ,…,冰)0<k<n
回溯算法 37 高级回溯讨论 确定子结点的排列规则 子集树和排列树 装载问题(0-1背包)问题都是子集树 皇后问题与旅行售货员问题是排列树 估计回溯算法的平均效率 判断是否满足多米诺性质 搜索策略----深度优先 确定每个结点能够分支的约束条件 确定存储搜索路径的数据结构 回溯算法 38 估计回溯算法的平均效率 计数搜索树中平均遍历的结点 Monte Carlo方法： 1．从根开始，随机选择一条路经，直到不能分 支为止, 即从x1,x2,…, 依次对xi赋值，每个xi 的值是从当时的Si中随机选取，直到向量不能 扩张为止 2．假定搜索树的其他|Si|-1个分支与以上随机选 出的路径一样，计数搜索树的点数。 3．重复步骤1和2，将结点数进行概率平均。 回溯算法 39 算法 Monte Carlo 1.sum = 0 2.for i = 1 to t do //取样次数 t 3. m = Estimate(n) //m为本次结总数 4. sum+= m 5.sum /= t 回溯算法 40 计算结点数 m为本次取样结点总数，k 为层数，r1为本层分支数, r2为上层分支数，n为树的层数 Estimate(n) 1. m=1;r2=1;k=1 2. While k<=n do 3. if Sk = then return m 4. r1 = |Sk|*r2 5. m = m + r1 6. 随机选择Sk的元素 7. r2 = r1 8. k++ ∅ xk ← 回溯算法 41 例 Monte Carlo方法估计四后问题的效率 case1．<1,4,2>：1+4+4×2+4×2 = 21 case2．<2,4,1,3>:：4×3+1=17 case3．<1,3>：1+4×1+4×2=13 假设4次抽样测试：case1 1次，case2 1次，case3 2次，平均为16 解空间的结点数为17 回溯算法 42 必要条件—多米诺性质 n皇后问题 设P(x1, x2, …, xi) 为真, 表示向量<x1,x2, …,xi>中i个皇 后放置在彼此不能攻击的位置 P(x1 , x2 ,..., xk+1 ) → P(x1 , x2 ,..., xk ) 0 < k < n