《算法设计与分析》PPT课件

1、回溯法算法设计与分析信息工程学院王甜甜0 0 - - 1 1背背 包包 问问 题题1使得 解空间树有 2n 个叶子节点的子集树 解空间第 j 层的成员由 xj 的值进行分割。 0-1 背包问题可以被形式地描述成如下形式：j wi xi Wi14jm ax vi xii10-1 背包问题23子集树子集树: : n=4n=410010 x1x3x4x214i 约束函数令 cw(i) 表示目前到第 i 层的总重量，记为cw(i) wj x jj 1则约束函数为C(i) cw(i 1) wi 剪枝若C(i) W，则停止搜索第 i 层及其下面的层，否则， 继续搜索。5 限限界函数界函数在这里， cv(i

2、) 表示目前到第i 层的价值， r(i) 表示剩 余物品的总价值，记为，B( (i) ) = = cv( (i) ) + + r( (i) )nir(i) v jj i 1cv(i) v j x j ,j 1 剪枝若B(i) bestv，则停止搜索第 i 层和下面的层，否则， 继续搜索。在此， bestv表示目前所得到的最好价值6r(i) 越大，搜索的分支越多。我们是否可以剪掉更多的分支 呢? 答案是可以。具体地说，我们可以构造如下的更好的界 限函数:kwvkw )()jk 1j i 1k 1j i 1v j (W cw(i) r(i) 首先，提前将物品以单位重量价值递减的顺序进行排列，记为v

3、1 v2 vn w1w2wn 考虑第 i 层，背包的剩余空间为 W-cw(i)， 用贪心策略把剩余 的物品放进背包，直到第 k 件物品放不进去。则，7 r(i) 计算得越精确，则 r(i) 的值比原始 r(i)的值越小，因此 可以剪掉更多的枝。 例如，给定一个例子：n=4, c=7, v=9, 10, 7, 4, w=3, 5, 2, 1,t则 v/w=3, 2, 3.5, 4.依据 v/w对物品进行排序， 则得到一个新的例子：n=4, c=7, v=4, 7, 9, 10, w=1, 2, 3, 5.则 v/w=4, 3.5, 3, 2.8n=4,n=4, W=7,W=7, v=4,7,9,

4、10,v=4,7,9,10, w=1,2,3,5 w=1,2,3,5 v/w=4,v/w=4, 3.5,3.5, 3,3, 2.2.1x110 x2x3C(i)/B(i)0/ 221/ 2220 1,1,1,03/22101/ 1900/ 203/ 196/ 20 6/ 22x4 09BacktrackKnapsack(i)1if in then2if cvbestv then3bestv cv4for j 1 to n do5bestxj xj6else7if C(i) W thenxi 18cw cw+wi; cv cv+ vi9BacktrackKnapsack(i+1)10cw cw-

5、wi; cv cv- vi11if B(i)bestv then xi 012BacktrackKnapsack(i+1)10r(i)1 rw W- cw2 b cv3 while i +1n and wi+1 rw do4rw rw- wi+15b b+ vi+16i i+17 if i +1n then b b+ vi+1/wi+1 rw8 return b11图的图的 m 着着 色色 问问 题题12 你希望用不超过四种颜色你希望用不超过四种颜色 对地图进行着色对地图进行着色 红，黄，绿，蓝红，黄，绿，蓝 相邻的国家必须用不同的颜色相邻的国家必须用不同的颜色 你没有足够的信息来选择颜色你没

6、有足够的信息来选择颜色 每个选择会得到新的选择子集每个选择会得到新的选择子集 一个或多个选择序列可以得到一个解一个或多个选择序列可以得到一个解 ( (或者得不到或者得不到) ) 许多着色问题可以用回溯算法来解决许多着色问题可以用回溯算法来解决着色问题着色问题13 四色定理四色定理：表述表述任任何一个平面何一个平面地地图可以用图可以用不不超过四种颜超过四种颜色色进进 行着色，行着色， 使得拥有使得拥有同同一边界线一边界线的的国家着不同国家着不同的的颜色颜色 对大多数地对大多数地图图，找到合，找到合法法的着色方案的着色方案是是很容易的很容易的 对某些地图对某些地图，要找到合要找到合法法的着色方案的

7、着色方案却却是很困难的是很困难的 更一般的问更一般的问题题：你可你可以以把地图着色把地图着色问问题转化为题转化为图图的的m m着色问题着色问题着色问题着色问题14 世界近代世界近代三三大数大数学学难题之一难题之一( (另另外外两两个个是是费费马马定理和哥定理和哥德德巴赫猜想巴赫猜想) )。 这是一个这是一个拓拓扑学扑学问问题，即找题，即找出出给球面（给球面（或或平面）地平面）地图图着色时所着色时所需需用的不同用的不同颜颜色的色的 最小数目最小数目。着色着色时时要使得没要使得没有有两个相邻两个相邻（即有公共即有公共边边界线段）界线段）的的区域有相区域有相同同的颜的颜 色色。18521852年年英

8、英国国的的格思格思里里推测：四推测：四种种颜色是充颜色是充分分必要的必要的。18781878年年英国数学英国数学家家凯利凯利 在一次数在一次数学学家会家会议议上呼吁大上呼吁大家家注意解决注意解决这这个问题。个问题。直直到到1971976 6年年，美国数学美国数学家家阿佩阿佩 哈尔、哈哈尔、哈肯肯和考和考西西利用高速利用高速电电子计算机子计算机运运算了算了1201200 0个个小时，才小时，才证证明了格思明了格思里里的推的推 测。四色测。四色问问题的题的解解决在数学决在数学研研究方法上究方法上的的突破，开突破，开辟辟了机器证了机器证明明的美好前的美好前景景。 四色定理四色定理是是第一第一个个主要

9、由计主要由计算算机证明的机证明的理理论论 ，证证明明方方法将法将地地图上的无图上的无限限种可能种可能情情 况减少况减少为为1,9361,936种种状状态（稍后态（稍后减减少少为为1,4761,476种种），），这这些状些状态态由计算机由计算机一一个挨一个个挨一个的的 进行检查。进行检查。四色原理四色原理15 问题问题给定一个无向图给定一个无向图 G=(=(V, ,E),), 需要对图需要对图 V 中的每个点中的每个点用用 m 种颜色种颜色 中的一种进行着色，记为中的一种进行着色，记为 1,2,1,2, m, , 使得使得相邻的顶点不同色。相邻的顶点不同色。图的图的m着色问题着色问题16 需要一

10、种容需要一种容易易操作的数操作的数据据结构结构: : 表示表示每每个个节节点的点的颜颜色色 对每对每个个点点, , 找找到到所所有有相相邻邻节节点点 我们可以使我们可以使用用两个数组两个数组 一个为一个为 “颜色颜色”数数组组, , x i 为为第第i i 个个节节点点的的颜色颜色 一个一个数数组组为为相邻相邻国国家数组家数组, , w i, ,j 表表示示i节节点点和和j节点节点是是否否相相邻邻 约束条件为约束条件为 w i, ,j, 没有其没有其它它约束函数和约束函数和限限界函数界函数数据结构数据结构17子集树: n=4, m=333x3x4x112x2123122323232318192021复杂度分析复杂度分析图m可着色问题的解空间树中内结点个数是对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是1