《算法设计与》第09章解读.ppt
算法设计与分析算法设计与分析DeSign and Analysis of AlgorithmsIn C+“十一五十一五”国家级规划教国家级规划教材材 陈慧南陈慧南陈慧南陈慧南 编著编著编著编著电子工业出版社电子工业出版社电子工业出版社电子工业出版社 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月第第2部分部分算法设计策略算法设计策略 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月第第9章章分支限界法分支限界法 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.19.1一般方法一般方法一般方法一般方法9.29.2求最优解的分枝限界法求最优解的分枝限界法求最优解的分枝限界法求最优解的分枝限界法 9.39.3带时限的作业排序带时限的作业排序带时限的作业排序带时限的作业排序 9.40/19.40/1背包背包背包背包 9.59.5旅行商问题旅行商问题旅行商问题旅行商问题 9.69.6批处理作业调度批处理作业调度批处理作业调度批处理作业调度 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.1一般方法一般方法 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.1.1分枝限界法概述分枝限界法概述采采用用广广度度优优先先产产生生状状态态空空间间树树的的结结点点，并并使使用用剪剪枝枝函函数数的的方方法法称称为为分分枝枝限限界界法法。按按照照广广度度优优先先的的原原则则，一一个个活活结结点点一一旦旦成成为为扩扩展展结结点点（E-结结点点）R后后，算算法法将将依依次次生生成成它它的的全全部部孩孩子子结结点点，并并将将它它们们一一一一加加入入活活结结点点表表，此此时时R自自身身成成为为死死结结点点。算算法从活结点表中另选一个活结点作为法从活结点表中另选一个活结点作为E-结点。结点。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月不不同同的的活活结结点点表表形形成成不不同同的的分分枝枝限限界界法法，分分为为：FIFO分分枝枝限限界界法法、LIFO分分枝枝限限界界法法和和LC（leastcost）分分枝枝限限界界法法。三三种种不不同同的的活活结结点点表表，规规定定了了从活结点表中选取下一个从活结点表中选取下一个E-结点的不同次序。结点的不同次序。FIFO分枝限界法分枝限界法的活结点表是先进先出队列的活结点表是先进先出队列LIFO分枝限界法分枝限界法的活结点表是堆栈；的活结点表是堆栈；LC分分枝枝限限界界法法的的活活结结点点表表是是优优先先权权队队列列，LC分分枝枝限限界界法法将将选选取取具具有有最最高高优优先先级级的的活活结结点点出出队队列列，成为新的成为新的E-结点。结点。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月例例91(4-皇后问题皇后问题)FIFO分枝限界法求解分枝限界法求解 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月【程序【程序91】分枝限界算法】分枝限界算法templatestructNodeTcost;Node*parent;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月templatevoidBranchBound(Node*t)LiveListNode*lst(mSize);Node*x,*E=t;dofor(对结点对结点E的每个不受限的孩子的每个不受限的孩子)x=newNode;x-parent=E;if(x是一个答案结点是一个答案结点)输出从输出从x到到t的一条路径；的一条路径；return;lst.Append(x);南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月if(lst.IsEmpty()cout“没有答案结点没有答案结点”；return；lst.Serve(E);while（1）；）；南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.1.2LC分枝限界法分枝限界法代价函数代价函数c()若若X是是答答案案结结点点，则则c(X)是是从从根根结结点点到到X的的搜搜索索代代价价；若若X不不是是答答案案结结点点且且子子树树X上上不不含含任任何何答答案案结结点点，则则c(X)=；若若X不不是是答答案案结结点点但但子子树树X上上包包含含答答案案结结点点，则则c(X)等等于于子子树树X上上具具有有最最小小搜搜索索代代价价的的答答案结点的代价。案结点的代价。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月相对代价函数相对代价函数g()衡衡量量一一个个结结点点X的的相相对对代代价价一一般般有有两两种种标标准准：在在生生成成一一个个答答案案结结点点之之前前，子子树树X上上需需要要生生成成的的结结点点数数目目；在在子子树树X上上，离离X最最近近的的答答案案结结点点到到X的的路路径径长长度度。容容易易看看出出，如如果果采采用用标标准准，总总是是生生成成最最小小数数目目的的结结点点；如如果果采采用用标标准准，则则要要成成为为E-结结点点的的结结点点只只是是由由根根到到最最近近的的那那个个答答案案结结点点路路径径上上的的那些结点。那些结点。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 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 2008年年3 3月月9.1.315谜问题谜问题在一个在一个4 4 4 4的方形棋盘上放置了的方形棋盘上放置了1515块编了号的牌，块编了号的牌，还剩下一个空格。问题要求对于任意给定的一种还剩下一个空格。问题要求对于任意给定的一种初始排列，通过一系列的合法移动，将给定的初初始排列，通过一系列的合法移动，将给定的初始排列转换成目标排列。始排列转换成目标排列。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月初初始始状状态态和和目目标标状状态态，从从任任意意初初始始状状态态，经经一一系系列列的的空空格格移移动动，到到达达目目标标状状态态。空空格格可以最多有前、后、左和右四种移动方式。可以最多有前、后、左和右四种移动方式。共共有有16！种种不不同同的的排排列列。这这个个状状态态空空间间树树是是相相当当大大的的。有有必必要要判判定定当当前前到到达达的的状状态态是是否属于该状态空间树。否属于该状态空间树。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月定理定理9-1对给定的初始状态，当且仅当对给定的初始状态，当且仅当为偶数时，可以由此初始状态到达目标状态，其中，为偶数时，可以由此初始状态到达目标状态，其中，i和和j分别是空格在棋盘上的行和列下标。分别是空格在棋盘上的行和列下标。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月 15 15谜问题的部分状态空间树谜问题的部分状态空间树(FIFOBB)南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月 15 15谜问题的部分状态空间树谜问题的部分状态空间树(LCBB)南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.2求最优解的分枝限界法求最优解的分枝限界法 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.2.1上下界函数上下界函数定定义义9-1 状状态态空空间间树树上上一一个个结结点点X X的的代代价价函函数数c c()定定义义为为：若若X X是是答答案案结结点点，则则c c(X X)为为X X所所代代表表的的可可行行解解的的目目标标函函数数值值；若若X X为为非非可可行行解解结结点点，则则c c(X X)=)=；若若X X代代表表部部分分向向量量，则则c c(X X)是是以以X X为为根根的的子子树树上上具具有有最最小小代代价价的的结结点点代代价价。显显然然，这这样样定定义义的的c c(X X)也也是是难难以以计计算的，它的计算难度与求得问题最优解的难度相当算的，它的计算难度与求得问题最优解的难度相当定定义义9-2 函函数数u()和和()分分别别是是代代价价函函数数c()的的上上界界和下界函数。对所有结点和下界函数。对所有结点X，总有总有(X)c(X)u(X)。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月基于上下界函数的分枝限界法的限界方法基于上下界函数的分枝限界法的限界方法 U的值可以按下列原则修正：的值可以按下列原则修正：如如果果X是是答答案案结结点点，cost(X)是是X所所代代表表的的可可行行解解的的目目标标函函数数值值，u(X)是是该该子子树树上上最最小小代代价价答答案案结结点点代代价的上界值，则价的上界值，则U=mincost(X),u(X)+,U；如果如果X代表部分向量，则代表部分向量，则U=minu(X)+,U。使用使用(X)U 剪除多余分枝。剪除多余分枝。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.2.2FIFO分枝限界法分枝限界法templatetemplateNode*FIFOBB(Node*t,T&U)Node*FIFOBB(Node*t,T&U)LiveListNode*lst(mSize);LiveListNode*lst(mSize);Node*ans=NULL,*x,*E=t;Node*ans=NULL,*x,*E=t;dodofor(for(对结点对结点对结点对结点 E E的每个孩子的每个孩子的每个孩子的每个孩子 x)x)if(if(x)U)(x)parent=E;x=newNode;x-parent=E;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月 lst.Append(x);lst.Append(x);if(xif(x是一个答案结点是一个答案结点是一个答案结点是一个答案结点&cost(x)U)cost(x)U)if(u(x)+if(u(x)+cost(x)U=u(x)+cost(x)U=u(x)+;elseU=cost(x);ans=x;elseU=cost(x);ans=x;elseif(u(x)+elseif(u(x)+U)U=u(x)+U)U=u(x)+;dodoif(lst.IsEmpty()returnans;if(lst.IsEmpty()returnans;lst.Serve(E);lst.Serve(E);while(while(E)U);(E)U);whilewhile（1 1）；）；）；）；南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.2.3LC分枝限界法分枝限界法 【程序【程序9-3】基于上下界的基于上下界的LC分枝限界法分枝限界法templateNode*LCBB(Node*t,T&U)LiveListNode*lst(mSize);Node*ans=NULL,*x,E=*t;dofor(对结点对结点E的每个孩子的每个孩子x)if(x)parent=E;lst.Append(x);南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月if(x是一个答案结点是一个答案结点&cost(x)U)if(u(x)+cost(x)U=u(x)+;elseU=coxt(x);ans=x;elseif(u(x)+U)U=u(x)+;if(!lst.IsEmpty()lst.Serve(E);if(E)U)returnans;elsereturnans;while（1）；）；南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.3 带时限的作业排序带时限的作业排序 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.3.1问题描述问题描述对对于于单单处处理理机机的的带带时时限限作作业业排排序序问问题题，如如果果每每个个作作业业具具有有相相同同的的处处理理时时间间，则则可可以以用用贪贪心心法法求求解解。如如果果每每个个作作业业的的处处理理时时间间允允许许不不同同，带带时时限限的的作作业业排排序序问问题题可可描描述述为为：设设有有n个个作作业业和和一一台台处处理理机机，每每个个作作业业所所需需的的处处理理时时间间、要要求求的的时时限限和和收收益益可可用用三三元元组组（ti,di,pi），0in表表示示，其其中中，作作业业i的的所所需需时时间间为为ti，如如果果作作业业i能能够够在在时时限限di内内完完成成，将将可可收收益益pi，求求使使得总收益最大的作业子集得总收益最大的作业子集J。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月例例例例9 91 1设设 有有 带带 时时 限限 的的 作作 业业 排排 序序 实实 例例：n=4，(p0,d0,t0)=(5,1,1)，(p1,d1,t1)=(10,3,2)，(p2,d2,t2)=(6,2,1)和和(p3,d3,t3)=(3,1,1)，求求使使得得总总收收益益最最大的作业子集大的作业子集J。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.3.2分枝限界法求解分枝限界法求解可可变变大大小小元元组组（x0,x1,xk）表表示示解解，xi为为作作业业编号。编号。问问题题的的显显式式约约束束为为：xi 0,1,n 1且且xixi+1(0in 1)，隐隐式式约约束束为为：对对于于选选入入子子集集J的的作作业业（x0,x1,xk），存存在在一一种种作作业业排排列列使使J中中作作业业均均能能如如期期完完成成。问问题题的的目目标标函函数数是是作作业业子子集集J中中所所有有作作业业所所获获取取的的收收益益之之和和，使使得得总总收收益益最最大大的的作作业业子子集集是是问问题题的的最最优优解解。如如果果希希望望以以最最小小值值为为最最优优解解，则则可可以以适适当当改改变变目目标标函函数数，将将其其改改为为未未入入选选子子集集J的的作作业业所所导导致致的损失，即为：的损失，即为：南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月可可变变大大小小元元组组（x0,x1,xk）表表示示解解，xi为为作作业业编编号。号。显显式式约约束束为为：xi 0,1,n 1且且xixi+1(0in 1)，隐隐式式约约束束为为：对对于于选选入入子子集集J的的作作业业（x0,x1,xk），存在一种作业排列使存在一种作业排列使J中作业均能如期完成。中作业均能如期完成。问问题题的的目目标标函函数数是是作作业业子子集集J中中所所有有作作业业所所获获取取的的收收益益之之和和，使使得得总总收收益益最最大大的的作作业业子子集集是是问问题题的的最最优优解解。如如果果希希望望以以最最小小值值为为最最优优解解，则则可可以以适适当当改改变变目目标标函函数，将其改为未入选子集数，将其改为未入选子集J的作业所导致的损失，即为：的作业所导致的损失，即为：南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月(X)u(X)(X)c(X)u(X)南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月可变大小元组状态空间树可变大小元组状态空间树 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.3.3带时限作业排序算法带时限作业排序算法【程序【程序94】带时限的作业排序带时限的作业排序structNodeNode(Node*par,intk)parent=par;j=k;Node*parent;intj;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月templatestructqNodeqNode()qNode(Tp,Tlos,intsd,intk,Node*pt)prof=p;loss=los;d=sd;ptr=pt;j=k;Tprof,loss;Node*ptr;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月templateclassJSpublic:JS(T*prof,int*de,int*time,intsize);TJSFIFOBB();voidGenerateAns(int*x,int&k);private:T*p,total;int*t,*d,n;Node*ans,*root;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月templateTJS:JSFIFOBB()Node*E,*child;QueueqNodeq(mSize);E=root=newNode(NULL,-1);qNodeep(0,0,0,-1,root),ec;TU=total+epsilonwhile(1)Tloss=ep.loss,prof=ep.prof;E=ep.ptr;for(intj=ep.j+1;jn;j+)南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月if(ep.d+tj=dj&lossU)child=newNode(E,j);ec.prof=prof+pj;ec.d=ep.d+tj;ec.ptr=child;ec.loss=loss;ec.j=j;q.Append(ec);Tcost=total-ec.prof;if(cost=U);/while/JSFIFOBB 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.40/1背包背包 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.4.1问题描述问题描述已已知知一一个个载载重重为为M的的背背包包和和n件件物物品品，第第i件件物物品品的的重重量量为为wi(wi0)，如如果果将将第第i件件物物品品装装入入背背包包，将将有有收收益益pi(pi0，0in)。现现求求一一种种最最佳佳装装载载方方案案，使得总收益最大。使得总收益最大。例例92设设有有载载重重能能力力为为M=15的的背背包包，4件件物物品品的的重重量量为为：(w0,w1,w2,w3)=(2,4,6,9)，物物品品装装入入背背包包的的收收益益为为：(p0,p1,p2,p3)=(10,10,12,18)。这这一一0/1背包实例的解为（背包实例的解为（1,1,0,1），总收益为），总收益为38。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.4.2分枝限界法求解分枝限界法求解目标函数：目标函数：代价函数：代价函数：若若X是答案结点（叶结点），则是答案结点（叶结点），则c(X)=cost(X)；若若X是叶结点但非答案结点，则是叶结点但非答案结点，则c(X)=；若若X是非叶结点，是非叶结点，则则c(X)=maxc(lChild(X),c(rChild(X)。上下界函数：上下界函数：LBB(X)、UBB(X)南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月贪心法的解：贪心法的解：Z=（z1,zk,zk+1,zn)0/1背包的最优解：背包的最优解：X=(x1,xk,xk+1,xn)一个可行解：一个可行解：Y(y1,yk,yk+1,yn)南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.4.30/1背包算法背包算法【程序【程序【程序【程序9 95 5】类声明类声明类声明类声明 structNode/状态空间树结点状态空间树结点Node(Node*par,boollft)parent=par;left=lft;Node*parent;boolleft;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月templatestructpqNode/活活结结点点结结构构operatorT()constreturnUBB;pqNode()pqNode(floatcap,Tprof,Tub,intlev,Node*p)cu=cap;profit=prof;level=lev;UBB=ub;ptr=p;floatcu;Tprofit,UBB;intlevel;Node*ptr;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月templateclassKnapsackpublic:Knapsack(T*prof,float*wei,floatmm,intlen);TLCBB();voidGenerateAns(int*x);private:voidLUBound(Tcp,floatcw,intk,T&LBB,T&UBB);T*p;float*w,m;intn;Node*ans,*root;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月【程序程序96】上下界函数上下界函数templatevoidKnapsack:LUBound(Tcp,floatcw,intk,T&LBB,T&UBB)LBB=cp;floatc=cw;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月for(inti=k;in;i+)if(cwi)UBB=LBB+c*pi/wi;for(intj=i+1;j=wj)c=c-wj;LBB=LBB+pj;return;c=c-wi;LBB=LBB+pi;UBB=LBB;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月【程序程序97】0/1背包的背包的LC分枝限界法分枝限界法templateTKnapsack:LCBB()Node*child,*E;TLBB,UBB,L;ans=NULL;PrioQueuepqNodepq(mSize);root=newNode(NULL,false);E=root;LUBound(0,m,0,LBB,UBB);pqNodee(m,0,UBB,0,root);L=LBB-epsilon;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月dointk=e.level;floatcap=e.cu;Tprof=e.profit;E=e.ptr;if(k=n)&(profL)L=prof;ans=E;elseif(cap=wk)child=newNode(E,true);e.ptr=child;e.level=k+1;e.cu=cap-wk;e.profit=prof+pk;pq.Append(e);南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月LUBound(prof,cap,k+1,LBB,UBB);if(UBBL)child=newNode(E,false);e.ptr=child;e.level=k+1;e.cu=cap;e.profit=prof;e.UBB=UBB;pq.Append(e);if(LL);returnL;南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.5旅行商问题旅行商问题 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.5.1问题描述问题描述旅旅行行商商问问题题（travellingsalesperson）是是一一个个看看似似简简单单其其实实十十分分难难解解的的著著名名难难题题之之一一，至至今今仍仍有有许许多多人人在在研研究究它它。此此问问题题描描述述为为：一一个个旅旅行行商商准准备备到到n个个村村庄庄售售货货。他他从从A村村出出发发经经过过其其它它n-1个个村村庄庄，又又回回到到出出发发地地A村村。现现要要求求一一条条最最短短路路径径，使使得得每每个个村庄都村庄都经过经过且且仅经过仅经过一次。一次。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月9.5.2 分枝限界法求解分枝限界法求解设设带带权权有有向向图图G=(V,E)，|V|=n，表表示示连连接接n个个村村庄庄的的道道路路交交通通图图，边边上上的的权权值值为为两两个个村村庄庄间间的的路路程程，cnn是是该图该图的的邻邻接矩接矩阵阵，下面也称，下面也称代价矩阵代价矩阵。旅旅行行商商问问题题的的解解是是一一条条回回路路：（x0,x1,xn 1,xn），x0=xn，0 xin；xi xj，当当i j和和i,j 0,n；E，0 in-1。其其状状态态空空间间树树结结构构见见图图911的的例例子子。图图中中采采用用的的解解结结构构形形式式为为（x1,xn-1），这里假定这里假定x0 xn0。本问题的目标函数是路径长度。本问题的目标函数是路径长度。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月归约代价矩阵归约代价矩阵定定义义9 93 3 如如果果矩矩阵阵的的一一行行（或或列列）中中至至少少包包含含一一个零且其余元素均非个零且其余元素均非负负，则则称此行（或列）已称此行（或列）已归约归约。定定义义9 94 4 如如果果一一个个矩矩阵阵的的所所有有行行和和列列均均已已归归约约，则则称此矩称此矩阵为阵为归约矩阵归约矩阵（reduced matrixreduced matrix）。）。对对矩矩阵阵的的一一行行（列列）进进行行归归约约，可可以以通通过过将将该该行行(列列)中中的的每每个个元元素素减减去去该该行行（列列）的的最最小小数数进进行行，此此最最小小数数称称为为该该行行（列列）的的约约数数。通通过过逐逐行行逐逐列列的的归归约约，可可得得到到一一个个代代价价矩矩阵阵的的归归约约矩矩阵阵。假假定定第第i i行行的的约约数数为为t ti i，第第j j列列的的约约数数为为r rj j，0 0 i,jni,jn，则则所所有有行行和和列列约约数之和称数之和称为为矩阵约数矩阵约数，设为设为L L，。，。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月对对矩矩阵阵的的一一行行（列列）进进行行归归约约，可可以以通通过过将将该该行行(列列)中中的的每每个个元元素素减减去去该该行行（列列）的的最最小小数数进进行行，此此最最小小数数称称为为该该行行（列列）的的约约数数。通通过过逐逐行行逐逐列列的的归归约约，可可得得到到一一个个代代价价矩矩阵阵的的归归约约矩矩阵阵。假假定定第第i i行行的的约约数数为为t ti i，第第j j列列的的约约数数为为r rj j，0 0 i,jni,jn，则则所所有有行行和和列列约约数之和称数之和称为为矩阵约数矩阵约数，设为设为L L，南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月代价矩阵代价矩阵归约矩阵归约矩阵 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月归约行归约行 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月归约列归约列矩阵约数矩阵约数L=25 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月下界函数计算方法下界函数计算方法根根结结点点R的的归归约约矩矩阵阵是是对对邻邻接接矩矩阵阵直直接接归归约约得得到到，其下界函数其下界函数(R)=L，L是矩是矩阵约阵约数。数。树树中中任任意意非非叶叶状状态态X的的归归约约矩矩阵阵B，可可由由其其双双亲亲状状态态P的的归归约约矩矩阵阵A，先先变变换换成成A后后再再归归约约得得到到B；X的的下下界界函函数数(X)=(P)+Aij+r，r是是从从A归归约约到到B的的矩矩阵阵约约数。数。叶叶状状态态S的的下下界界函函数数(S)=c(S)，c(S)为为从从根根到到S的的路路径径长长度。度。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月上界函数上界函数对对于于树树中任何状中任何状态结态结点点X，令上界函数令上界函数值值u(X)=。南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月 南京邮电大学计算机学院南京邮电大学计算机学院 2008 2008年年3 3月月
