北京大学：《数据结构与算法》课程教学资源（实习课件PPT）回溯（Backtracking）基本原理

效率分析一时间 回溯算法的效率很大程度上依赖于以下 因素 产生一个x[k的时间 满足显约束xk]的个数 计算约束函数 constraint的时间代价 计算限界函数 bound的时间代价 n满足约束函数和限界函数约束的所有x[K]的 个数 回溯算法 16

回溯算法 16 效率分析—时间 „ 回溯算法的效率很大程度上依赖于以下 因素 „ 产生一个x[k]的时间 „ 满足显约束x[k]的个数 „ 计算约束函数constraint()的时间代价 „ 计算限界函数bound()的时间代价 „ 满足约束函数和限界函数约束的所有x[k]的 个数

提高时间效率的策略 ■约束函数 好的约束函数能显著的减少所生成的结点数 往往计算量大—折衷问题 ■搜索树的结构 “重排原理”可提高效率 结点少的分支优先 ■搜索策略 根据树分支设计优先策略 结点少的分支优先 解多的分支优先 利用搜索树的对称性剪裁子树 分解为子问题 回溯算法

回溯算法 17 提高时间效率的策略 „ 约束函数 „ 好的约束函数能显著的减少所生成的结点数 „ 往往计算量大——折衷问题 „ 搜索树的结构 „ “重排原理”可提高效率 „ 结点少的分支优先 „ 搜索策略 „ 根据树分支设计优先策略 „ 结点少的分支优先 „ 解多的分支优先 „ 利用搜索树的对称性剪裁子树 „ 分解为子问题

效率分析一空间 空间代价 如果要把整个树存储下来的话,那空间代价 是惊人的 用回溯算法解的问题的可能解空间一般都很大, 即相应的可能解空间树非常巨大 在回溯算法中,并不需要真正创建一个空间 树 ■树的深度优先搜索策略的空间代价一般为最 长路径的长度 回溯算法 18

回溯算法 18 效率分析—空间 „ 空间代价 „ 如果要把整个树存储下来的话，那空间代价 是惊人的 „ 用回溯算法解的问题的可能解空间一般都很大， 即相应的可能解空间树非常巨大。 „ 在回溯算法中，并不需要真正创建一个空间 树 „ 树的深度优先搜索策略的空间代价一般为最 长路径的长度

实战训练:背包问题 从n个物品中选取若干物品装载容量为M 的背包;已知:第i个物品的重量是Wm价 值是p(i=0.n-1),且每个物品是无 法分割的。求:最优装载方案,即总重 量小于M,总价值最大。 0-1背包问题,物品不允许切割 回溯算法 19

回溯算法 19 实战训练：背包问题 „ 从n个物品中选取若干物品装载容量为M 的背包；已知：第i个物品的重量是wi,价 值是 pi,(i=0...n-1) ，且每个物品是无 法分割的。求：最优装载方案，即总重 量小于M，总价值最大。 „ 0-1背包问题，物品不允许切割

构造解空间树 0-背包问题的一个解可以表示为一个n维向量 (x0x1…xn-1),X1=0或着1i=01…n-1) 全部可能解有2n个 可以用下图所示的状态空间树 X1=0 X2=0 3⑤d⑨④d⑩如⑦②以②s

回溯算法 20 构造解空间树 „ 0-1背包问题的一个解可以表示为一个n维向量 (x0,x1,...,xn-1), xi=0或着1,(i=0,1,...,n-1) „ 全部可能解有2n个 „ 可以采用下图所示的状态空间树 1 X0=0 2 3 4 5 6 8 1 1 X1=0 13 7 9 0 0 12 15 0 1 10 11 16 1 14 20 0 0 1 1 17 18 19 21 0 1 22 24 1 1 0 23 27 0 0 26 28 0 1 25 29 30 1 0 31 1 1 X2=0 X3=0 1 1