《算法设计与分析》第08章

《《算法设计与分析》第08章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析DeSignandAnalysisofAlgorithmsInC++“十一五”国家级规划教材陈慧南编著电子工业出版社第2部分算法设计策略第8章回溯法8.1一般方法8.2n-皇后8.3子集和数8.4图的着色8.5哈密顿环8.60/1背包8.7批处理作业调度8.1一般方法8.1.1基本概念解以向量形式表示：(x0,x2,…,xn-1)规定每个xi取值的约束条件称为显式约束（explicitconstraint）。对给定的一个问题实例，显式约束规定了所有可能的元组(候选解)，它们组成问题的候选解集，被称为该问题实

2、例的解空间（solutionspace）。隐式约束（implicitconstraint）给出了判定一个候选解是否为可行解的条件。目标函数，也称代价函数（costfunction），用来衡量每个可行解的优劣。使目标函数取最大（或最小）值的可行解为问题的最优解。状态空间树（statespace）是描述问题解空间的树形结构。树中每个结点称为一个问题状态（problemstate）。如果从根到树中某个状态的路径代表了一个作为候选解的元组，则称该状态为解状态（solutionstate）。如果从根到某个解状态的路径代表一个作为可

3、行解的元组，则称该解状态为答案状态(answerstate)。例0/1背包问题M，n；wi,pi(x0,x1,x2,x3)显示约束：xi∈{0，1}隐式约束：∑xiwi≤M目标函数：∑xipi当n=3时对应的状态空间树树中总结点数2n01010101010101第1层第2层第3层第3层例0/1背包问题元素a0,a1,…,an-1排序问题解向量（x1,x2,…,xn-1),显示约束：xi∈{0,1,…,n-1}且xi≠xj(i≠j)隐式约束：xi≤xj(i≤j)无目标函数(13,24,09)树中总结点数n!8.1.2剪

4、枝函数和回溯法为了提高搜索效率，在搜索过程中使用约束函数（constraintfunction），可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题，还可使用限界函数（boundfunction）剪去那些不可能包含最优答案结点的子树。约束函数和限界函数的目的是相同的，都为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，它们统称为剪枝函数（pruningfunction）。使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法（backtracking）；广度优先生成结点，并使用剪枝函数的

5、方法称为分枝限界法（branch-and-bound）。【程序8－1】递归回溯法VoidRBacktrack(intk){//应以Rbacktrack(0)调用本函数for(每个x[k],使得x[k]T(x[0],,x[k-1])&&(Bk(x[0],,x[k])){if((x[0],x[1],,x[k])是一个可行解)输出(x[0],x[1],,x[k]);RBacktrack(k+1);}}T(x[0],,x[k-1])代表xk所有可能取值约束函数Bk(x[0],,x[k])部分向量(x[0],,x[

6、k-1])代表从根到一个问题状态Y的路径【程序8-2】迭代回溯法VoidIBacktrack(intn){intk=0;while(k>=0){if(还剩下尚未检测的x[k]，使得x[k]T(x[0],,x[k-1])&&Bk(x[0],,x[k]){if((x[0],x[1],,x[k])是一个可行解)输出(x[0],x[1],,x[k]);k++;}elsek--;}}8.1.3回溯法的效率分析状态空间树种总结点数为：2n,n!,nnp(n)是n的多项式，是生成一个结点所需的时间回溯算法的最坏情况时间复杂度

7、可达O(p(n)n!)（或O(p(n)2n)或O(p(n)nn)）。蒙特卡罗方法（MonteCarlo）。这种估计方法的基本思想是在状态空间树中随机选择一条路径(x0,x1,…,xn1)。设X是这条随机路径上，代表部分向量(x0,x1,…,xk1)的结点，如果在X处不受限制的孩子数目是mk，则认为与X同层的其他结点不受限制的孩子数目也都是mk。整个状态空间树上将实际生成的结点数估计为m=1+m0+m0m1+m0m1m2+【程序8-3】蒙特卡罗算法intEstimate(SType*x){intk=0,m=1,r=1

8、;do{SetTypeS={x[k]

9、x[k]T(x[1],,x[k1])&&Bk(x[1],,x[k]==true)}；if(!Size(S))returnm;r=r*Size(S);m=m+r;x[k]=Choose(S);k++;}while(1);}函数size返回集合S的大小；函数Choose从集合