2011算法第十二十三讲回朔法ppt课件.ppt

《2011算法第十二十三讲回朔法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ECNUYinpingLiu回溯法柳银萍ECNUYinpingLiu1.回溯法的基本思想回溯法有“通用的解题法”之称。应用回溯法解问题时，首先应该明确问题的解空间。一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来，解任何问题都有一个目标，在约束条件下使目标达优的可行解称为该问题的最优解。在解空间中，前k项决策已经确定的所有决策序列之集称为k定子解空间。0定子解

2、空间即是该问题的解空间。ECNUYinpingLiu例1．旅行商问题:某售货员要到若干个城市去推销商品。已知各个城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使得总的路程（或总旅费）最短。ECNUYinpingLiu我们用一个带权图G(V,E)来表示，顶点代表城市，边表示城市之间的道路。图中各边所带的权即是城市间的距离（或城市间的旅费）。则旅行商问题即是：在带权图G中找到一条路程最短的周游路线，即权值之和最小的Hamilton圈。ECNUYinpingLiu如果假定城市A是驻地。则推销员

3、从A地出发，第一站有3种选择：城市B、C或城市D；第一站选定后，第二站有两种选择：如第一站选定B，则第二站只能选C、D两者之一。当第一、第二两站都选定时，第三站只有一种选择：比如，当第一、第二两站先后选择了B和C时，第三站只能选择D。最后推销员由城市D返回驻地A。推销员所有可能的周游路线.ECNUYinpingLiu例2．定和子集问题：已知一个正实数的集合A={w1,w2,…wn}和正实数M．试求A的所有子集S，使得S中的数之和等于M。这个问题的解可以表示成0/1数组(x1,x2,...,xn)，依据wi是否属于S，xi分别取值

4、1或0。故解空间中共有2n个元素。它的树结构是一棵完全二叉树。ECNUYinpingLiu例3．4皇后问题:在4×4棋盘上放置4个皇后，且使得每两个之间都不能互相攻击，即任意两个皇后都不能放在同一行、同一列及同一对角线上。将4个皇后分别给以1到4的编号，这个问题的解决就是要安排4个皇后的位置。因而，每个决策序列由4个决策组成：P1，P2，P3，P4，这里Pk代表安排第k个皇后的位置，因而有16种可能。该问题的解空间有164个决策序列。这时的约束条件是:任意两个皇后均不能位于同一行、同一列及同一个对角线上。注意到这个解空间比较大，

5、从中搜索可行解较为困难。现在把约束条件中的“任意两个皇后均不在同一行”也放在问题中考虑，即：将4个皇后放在4×4棋盘的不同行上，ECNUYinpingLiu使得每两个皇后均不能位于同一列、同一对角线上。则解空间中共有44个决策序列，因为此时可以假定第k个皇后处于第k行上。此时的约束条件为：任意两个皇后均不能位于同一列及同一个对角线上。事实上，我们还可以用另一种方法描述，使得解空间进一步缩小。将问题陈述为：将4个皇后放在4×4棋盘的不同行、不同列上，使得任意两个皇后均不能处在同一对角线上。这时的解空间应当由4！个决策序列构成。因为

6、此时每个决策序列实际上对应于{1,2,3,4}的一个排列。我们可以用树来描述解空间。ECNUYinpingLiu从例3来看，解空间的确定与我们对问题的描述有关。如何组织解空间的结构会直接影响对问题的求解效率。这是因为回溯方法的基本思想是通过搜索解空间来找到问题的可行解以至最优解。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集合树。此时，解空间有2n个元素，遍历子集树的任何算法均需(2n)的计算时间,如例2。当所给的问题是确定n个元素的满足某种性质的排列时，相应的解空间树称为排列树，此时，解空

7、间有n!个元素。遍历排列树的任何算法均需(n!)计算时间，如例1和例3。本章只讨论具有上两类解空间树的求解问题。ECNUYinpingLiu子集树与排列树遍历子集树需O(2n)计算时间遍历排列树需要O(n!)计算时间voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++

8、){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}ECNUYinpingLiu扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结