算法设计与分析讲义-中科院-陈玉福ch7

《算法设计与分析讲义-中科院-陈玉福ch7》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、126第七章回溯法§1.回溯法的基本思想回溯法有“通用的解题法”之称。应用回溯法解问题时，首先应该明确问题的解空间。一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来，解任何问题都有一个目标，在约束条件下使目标值达到最大（或最小）的可行解称为该问题的最优解。在解空间中，前k项决策已经取定的所有决策序列之集称为k定子解空间。0定子解空间即是该问题的解空间。例1．旅行商问题:某售货员要到若干个

2、城市去推销商品。已知各个城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到原驻地的路线，使得总的路程（或总旅费）最小。用一个赋权图G(V,E)来表示，节点代表城市，边表示城市之间的道路。图中各边所带的权即是城市间的路程（或城市间的旅费）。30125求赋权图G的6具有最小权的410Hamilton圈3204图7-1-1一个赋权图则旅行商问题归结为：在带权图G中找到一条路程最短的周游路线，即权值之和最小的Hamilton圈。注：连通图G的一条Hamilton圈(或叫Hamilton回路)是指通过G的每个顶点恰好一次的圈。如果假定城市A

3、是驻地。则推销员从A地出发，第一站有3种选择：城市B、C或城市D；第一站选定后，第二站有两种选择：如第一站选定B，则第二站只能选C、D两者之一。当第一、第二两站都选定时，第三站只有一种选择：比如，当第一、第二两站先后选择了B和C时，第三站只能选择D。最后推销员由城市D返回驻地A。推销员所有可能的周游路线共有3!=6条，它们构成该旅行商问题实例的解空间，见图7-1-2。127ABCDCDBDBCDCDBBC图7-1-2旅行商问题6种可能解例2．定和子集问题：已知一个正实数的集合A={w,w,?,w}和另一12n个正实数M．试求A的所有子集S，使得S中的数之和

4、等于M。这个问题的解可以表示成0/1数组(x,x,?,x)，依据w是否属于S，x分别取值1或0。故解空间12n11n中共有2个元素。它的树结构是一棵完整二叉树。1x1=1x1=0217x2=1x2=0x2=1x2=03101825x3=1x3=0x3=1x3=0x3=1x3=0x3=1x3=047111419222629x4=0x41010101=1010101015689121315162021232427283031图7-1-3定和子集问题的解空间树例3．4皇后问题:在4×4棋盘上放置4个皇后，要使得每两个皇后之间都不能互相攻击，即任意两个皇后都不能放

5、在同一行、同一列及同一对角线上。将4个皇后分别给以1到4的编号，这个问题的解决就是要安排4个皇后的位置。因而，每个决策序列由4个决策组成：P1，P2，P3，P4，这里Pk代表安排4第k个皇后的位置，每个皇后都有16种可能。该问题的解空间有16个决策序列。128这时的约束条件是:任意两个皇后均不能位于同一行、同一列及同一个对角线上注意到这个解空间比较大，从中搜索可行解较为困难。现在把约束条件中的“任意两个皇后均不在同一行”也放在问题中考虑，即：将4个皇后放在4×4棋盘的不同行上，约束条件是：任意两个皇后均不能位于同一列、同一对角线上4这时的解空间中共有4个决

6、策序列，因为此时每个皇后只有4个可能的位置可选（可以假定第k个皇后处于第k行上）。事实上，我们还可以用另一种方法描述，使得解空间进一步缩小。将问题陈述为：将4个皇后放在4×4棋盘的不同行、不同列上，使得任意两个皇后均不能处在同一对角线上这时的解空间应当由4！个决策序列构成。因为此时每个决策序列实际上对应于{1,2,3,4}的一个排列。我们可以用一棵排列树来描述解空间。1x1=1x1=4x1=2x1=32183450234134124123381319242935404551566134242334141324141223131246911141620222

7、52730323638414346485254575962644342324341314242213231215710121517212326283133373942444749535558606365图7-1-4四皇后问题的解空间树从例3来看，解空间的确定与我们对问题的描述有关。如何组织解空间的结构会直接影响对问题的求解效率。这是因为回溯方法的基本思想是通过搜索解空间来找到问题所要求的解。一般地，可以用一棵树来描述解空间，称为解空间树。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空nn间树称为子集合树。此时，解空间有2个元素，遍历

8、子集树的任何算法均需Ω2()的计算时间。如例2。当所给的问题是确定