资源预览内容
第1页 / 共41页
第2页 / 共41页
第3页 / 共41页
第4页 / 共41页
第5页 / 共41页
第6页 / 共41页
第7页 / 共41页
第8页 / 共41页
第9页 / 共41页
第10页 / 共41页
亲,该文档总共41页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
计算机算法设计与分析,North China Electric Power University,Computer Algorithms Design & Analysis,华北电力大学计算机科学与工程系,Dept. of Computer Science&Engineering of North China Electric Power University,第六章 回溯算法(Backtrack Algorithm), 回溯法的算法框架, 自然数的排列问题, 婚姻搭配问题, n后问题, 图的着色问题,North China Electric Power University, 旅行售货员问题, 符号三角形问题,1 回溯法的算法框架,North China Electric Power University,回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时,总是先判断该结点是否肯定不包含问题的解,如果肯定不包含,则跳过对以该结点为根的子树搜索。否则,进入该子树,继续按深度优先的策略进行搜索。 回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可结束。,North China Electric Power University,1.问题的解空间: 应用回溯法解问题时,首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个最优解。例如,对于有n种可选择的物品的0-1背包问题,其解空间由长度为n的0-1向量组成。该解空间包含了对变量的所有可能的0-1赋值。例如,当n=3时,其解空间是(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)。 通常将问题的解空间组织成树或图的形式。例如,对于n=3的0-1背包问题,其解空间树可用下面的完全二叉树表示。,A,B,C,D,E,F,G,H,I,J,L,K,M,N,O,1,0,1,0,1,0,1,0,1,0,1,0,1,0,North China Electric Power University,2.回溯法的基本思想: 确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前的扩展结点就成为死结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。,在用回溯法搜索解空间树时,通常采用两种策略来避免无效搜索,提高回溯法的搜索效率。其一是用约束函数在扩展结点处剪去不满足约束条件的子树;其二是用限界法剪去不能得到最优解的子树。这两类方法统称为剪枝函数。,A,B,C,D,E,F,G,H,I,J,L,K,M,N,O,x1=1,x1=0,x2=1,x2=0,x3=1,x3=0,x3=1,x3= 0,x2=1,x2=0,x3=1,x3=0,x3=1,x3=0,例:0-1背包问题 n=3,C=20,(p1,p2,p3)=(20,15,25) (w1,w2,w3)=(10,5,15),求X=(x1,x2,x3)使背包价值最大?,(10,20),(15,35),(15,35),(10,20),(10,20),(5,15),(20,40),(15,35),(5,15),(20,40),(0,0),(0,0),(15,25),(20,40),(20,40),(0,0),(20,40),当前最优解,可行解,中间计算结果,综上所述,运用回溯法解问题通常包含以下三个步骤:,1)针对所给问题,定义问题的解空间;2)确定易于搜索的解空间结构3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。,3.递归回溯: 由于回溯法是对解空间的深度优先搜索,因此在一般情况下可用递归函数来实现回溯法如下: void Backtrack(int t) if(tn) Output(x); else for(int i=f(n,t);in) Output(x); else for(int i=0;in) Output(x); else for(int i=t;in) output(x); else for (int i=0;in) output(x); else for (int i=t;in) for(int i=1;i=n;i+) coutxi ; coutendl; else for(int i=t;i=n;i+) swap(x,t,i); pailie(x,t+1,n); swap(x,t,i); ,3 婚姻搭配问题,问题描述:,有n对男女要配成n对夫妇,其中第i位男士对第j位女士的爱恋程度为pij,第i位女士对第j位男士的爱恋程度为qij,显然pij不一定等于qji,设计一个算法,确定各对夫妇的最佳婚配,使方案中各对夫妇的婚姻最满意。,分析与解答:,刻划n对夫妇婚姻总体的满意程度的标准:,其中第i位男士的配偶为第i位女士,不同的婚配方案共有n!种,采用回溯算法找出各种婚配方案,计算不同方案的婚姻满意度,使S取值最大的方案即为所求解。,void perference(int k,int n) if(k=n) for(int i=k;i=n;i+) swap(bk,bi); perference(k+1,n); swap(bk,bi); else float tmp=0; for(int i=1;ipref) pref=tmp; for(i=1;i n) / 到达叶结点 if (cwbestw) bestw=cw;return; if (cw + wi = c) / 搜索左子树 xi = 1; cw += wi; backtrack(i + 1); cw -= wi; xi = 0; / 搜索右子树 backtrack(i + 1); ,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号