空间复杂度分析 运行数据 主要由两个因素决定, 已知 算法的输入,输出和运行中的临时数据 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 基本回溯小结 „ 回溯适应于求解组合搜索问题(组合优化问题) „ 解空间一般用树表示 „ 解的表示 „ 解向量，解的过程是不断扩充解向量的过程 „ 回溯口诀 „ 能进则进，不能进则换，不能换则退 „ 回溯条件 „ 搜索问题---约束条件 „ 优化问题---约束条件+限界函数 „ 算法复杂性 „ 遍历搜索树的时间，最坏情况为指数 „ 空间代价小