算法设计与分析第09章

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

1、算法设计与分析DeSignandAnalysisofAlgorithmsInC++“十一五”国家级规划教材陈慧南编著电子工业出版社南京邮电大学计算机学院2008年3月第2部分算法设计策略南京邮电大学计算机学院2008年3月第9章分支限界法南京邮电大学计算机学院2008年3月9.1一般方法9.2求最优解的分枝限界法9.3带时限的作业排序9.40/1背包9.5旅行商问题9.6批处理作业调度南京邮电大学计算机学院2008年3月9.1一般方法南京邮电大学计算机学院2008年3月9.1.1分枝限界法概述采用广度优先产生状态空间

2、树的结点，并使用剪枝函数的方法称为分枝限界法。按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，并将它们一一加入活结点表，此时R自身成为死结点。算法从活结点表中另选一个活结点作为E-结点。南京邮电大学计算机学院2008年3月不同的活结点表形成不同的分枝限界法，分为：FIFO分枝限界法、LIFO分枝限界法和LC（leastcost）分枝限界法。三种不同的活结点表，规定了从活结点表中选取下一个E-结点的不同次序。FIFO分枝限界法的活结点表是先进先出队列LIFO分枝限界法的活

3、结点表是堆栈；LC分枝限界法的活结点表是优先权队列，LC分枝限界法将选取具有最高优先级的活结点出队列，成为新的E-结点。南京邮电大学计算机学院2008年3月例9－1(4-皇后问题)FIFO分枝限界法求解南京邮电大学计算机学院2008年3月【程序9－1】分枝限界算法templatestructNode{Tcost;Node*parent;}南京邮电大学计算机学院2008年3月templatevoidBranchBound(Node*t){LiveList*>lst(

4、mSize);Node*x,*E=t;do{for(对结点E的每个不受限的孩子){x=newNode;x->parent=E;if(x是一个答案结点){输出从x到t的一条路径；return;}lst.Append(x);}南京邮电大学计算机学院2008年3月if(lst.IsEmpty()){cout<<“没有答案结点”；return；}lst.Serve(E);}while（1）；}南京邮电大学计算机学院2008年3月9.1.2LC分枝限界法代价函数c(·)若X是答案结点，则c(X)是从根结点到X的搜索代价；

5、若X不是答案结点且子树X上不含任何答案结点，则c(X)=；若X不是答案结点但子树X上包含答案结点，则c(X)等于子树X上具有最小搜索代价的答案结点的代价。南京邮电大学计算机学院2008年3月相对代价函数g(·)衡量一个结点X的相对代价一般有两种标准：①在生成一个答案结点之前，子树X上需要生成的结点数目；②在子树X上，离X最近的答案结点到X的路径长度。容易看出，如果采用标准①，总是生成最小数目的结点；如果采用标准②，则要成为E-结点的结点只是由根到最近的那个答案结点路径上的那些结点。南京邮电大学计算机学院2008年3

6、月南京邮电大学计算机学院2008年3月相对代价估计函数ĝ(.)ĝ(X)作为g(X)的估计值，用于估计结点X的相对代价，它是由X到达一个答案结点所需代价的估计函数。一般地，假定(X)满足如下特性：如果Y是X的孩子，则有(Y)≤(X)。代价估计函数ĉ(.)ĉ(X)是代价估计函数，它由两部分组成：从根到X的代价f(X)和从X到答案结点的估计代价(X)，即ĉ(X)=f(X)+ĝ(X)。一般而言，可令f(X)等于X在树中的层次。南京邮电大学计算机学院2008年3月9.1.315谜问题在一个44的方形棋盘上放置了15块编了号的

7、牌，还剩下一个空格。问题要求对于任意给定的一种初始排列，通过一系列的合法移动，将给定的初始排列转换成目标排列。南京邮电大学计算机学院2008年3月初始状态和目标状态，从任意初始状态，经一系列的空格移动，到达目标状态。空格可以最多有前、后、左和右四种移动方式。共有16！种不同的排列。这个状态空间树是相当大的。有必要判定当前到达的状态是否属于该状态空间树。南京邮电大学计算机学院2008年3月定理9-1对给定的初始状态，当且仅当为偶数时，可以由此初始状态到达目标状态，其中，i和j分别是空格在棋盘上的行和列下标。南京邮电大学

8、计算机学院2008年3月15谜问题的部分状态空间树(FIFOBB)南京邮电大学计算机学院2008年3月15谜问题的部分状态空间树(LCBB)南京邮电大学计算机学院2008年3月9.2求最优解的分枝限界法南京邮电大学计算机学院2008年3月9.2.1上下界函数定义9-1状态空间树上一个结点X的代价函数c(·)定义为：若X是答案结点，则c(X)为X