《算法设计与》第09章解读优秀PPT.ppt

《《算法设计与》第09章解读优秀PPT.ppt》由会员分享，可在线阅读，更多相关《《算法设计与》第09章解读优秀PPT.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析DeSign and Analysis of AlgorithmsIn C+“十一五十一五”国家级规划教国家级规划教材材 陈慧南陈慧南陈慧南陈慧南 编著编著编著编著电子工业出版社电子工业出版社电子工业出版社电子工业出版社 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月第第2部分部分算法设计策略算法设计策略 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月第第9章章分支限界法分支限界法 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月9.19.1一般方法一般方法一般方法一般方法

2、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分枝限界法概述分枝限界法概述接接受受广广度度优优先先产产生生状状态态空空

3、间间树树的的结结点点，并并运运用用剪剪枝枝函函数数的的方方法法称称为为分分枝枝限限界界法法。依依据据广广度度优优先先的的原原则则，一一个个活活结结点点一一旦旦成成为为扩扩展展结结点点（E-结结点点）R后后，算算法法将将依依次次生生成成它它的的全全部部孩孩子子结结点点，并并将将它它们们一一一一加加入入活活结结点点表表，此此时时R自自身身成成为为死死结结点点。算算法从活结点表中另选一个活结点作为法从活结点表中另选一个活结点作为E-结点。结点。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月不不同同的的活活结结点点表表形形成成不不同同的的分分枝枝限限界界法法，分分为为：

4、FIFO分分枝枝限限界界法法、LIFO分分枝枝限限界界法法和和LC（leastcost）分分枝枝限限界界法法。三三种种不不同同的的活活结结点点表表，规规定定了了从活结点表中选取下一个从活结点表中选取下一个E-结点的不同次序。结点的不同次序。FIFO分枝限界法分枝限界法的活结点表是先进先出队列的活结点表是先进先出队列LIFO分枝限界法分枝限界法的活结点表是堆栈；的活结点表是堆栈；LC分分枝枝限限界界法法的的活活结结点点表表是是优优先先权权队队列列，LC分分枝枝限限界界法法将将选选取取具具有有最最高高优优先先级级的的活活结结点点出出队队列列，成为新的成为新的E-结点。结点。南京邮电高校计算机学院南

5、京邮电高校计算机学院 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=n

6、ewNode;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不

7、不是是答答案案结结点点且且子子树树X上上不不含含任任何何答答案案结结点点，则则c(X)=；若若X不不是是答答案案结结点点但但子子树树X上上包包含含答答案案结结点点，则则c(X)等等于于子子树树X上上具具有有最最小小搜搜寻寻代代价价的答案结点的代价。的答案结点的代价。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月相对代价函数相对代价函数g()衡衡量量一一个个结结点点X的的相相对对代代价价一一般般有有两两种种标标准准：在在生生成成一一个个答答案案结结点点之之前前，子子树树X上上须须要要生生成成的的结结点点数数目目；在在子子树树X上上，离离X最最近近的的答答案案结结点

8、点到到X的的路路径径长长度度。简简洁洁看看出出，假假如如接接受受标标准准，总总是是生生成成最最小小数数目目的的结结点点；假假如如接接受受标标准准，则则要要成成为为E-结结点点的的结结点点只只是是由由根根到到最最近近的的那那个个答答案案结结点点路路径径上上的的那些结点。那些结点。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月相对代价估计函数相对代价估计函数(.)(X)作作为为g(X)的的估估计计值值，用用于于估估计计结结点点X的的相相对对代代价价，它它是是由由X到到达达一一个个答答案案

9、结结点点所所需需代代价价的的估估计计函函数数。一一般般地地，假假定定(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的方形棋盘上放置了的方形棋盘上放置

10、了15块编了号的牌，块编了号的牌，还剩下一个空格。问题要求对于随意给定的一种还剩下一个空格。问题要求对于随意给定的一种初始排列，通过一系列的合法移动，将给定的初初始排列，通过一系列的合法移动，将给定的初始排列转换成目标排列。始排列转换成目标排列。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月初初始始状状态态和和目目标标状状态态，从从随随意意初初始始状状态态，经经一一系系列列的的空空格格移移动动，到到达达目目标标状状态态。空空格格可以最多有前、后、左和右四种移动方式。可以最多有前、后、左和右四种移动方式。共共有有16！种种不不同同的的排排列列。这这个个状状态态空空

11、间间树树是是相相当当大大的的。有有必必要要判判定定当当前前到到达达的的状状态态是是否属于该状态空间树。否属于该状态空间树。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月定理定理9-1对给定的初始状态，当且仅当对给定的初始状态，当且仅当为偶数时，可以由此初始状态到达目标状态，其中，为偶数时，可以由此初始状态到达目标状态，其中，i和和j分别是空格在棋盘上的行和列下标。分别是空格在棋盘上的行和列下标。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月 15 15谜问题的部分状态空间树谜问题的部分状态空间树(FIFOBB)南京邮电高校计算机学

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

13、(X)=；若若X代代表表部部分分向向量量，则则c(X)是是以以X为为根根的的子子树树上上具具有有最最小小代代价价的的结结点点代代价价。明明显显，这这样样定定义义的的c(X)也也是是难难以以计计算的，它的计算难度与求得问题最优解的难度相当算的，它的计算难度与求得问题最优解的难度相当定定义义9-2 函函数数u()和和()分分别别是是代代价价函函数数c()的的上上界界和和下界函数。对全部结点下界函数。对全部结点X，总有，总有(X)c(X)u(X)。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月基于上下界函数的分枝限界法的限界方法基于上下界函数的分枝限界法的限界方法U的

14、值可以按下列原则修正：的值可以按下列原则修正：假假如如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

15、*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是一个答案结点是一个答案结点是一个

16、答案结点是一个答案结点&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）；）；）；）；南京邮电高校计算机学院南京邮

17、电高校计算机学院 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

18、=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问题描述问题描述对对对对于于于于单单单单处处处处理理理理机机机机的的的的带带带带时时时时限限限限作作作作业业业业排排排排序序序序问问问问题题题题，假假假假如如如如每每每每个个

19、个个作作作作业业业业具具具具有有有有相相相相同同同同的的的的处处处处理理理理时时时时间间间间，则则则则可可可可以以以以用用用用贪贪贪贪心心心心法法法法求求求求解解解解。假假假假如如如如每每每每个个个个作作作作业业业业的的的的处处处处理理理理时时时时间间间间允允允允许许许许不不不不同同同同，带带带带时时时时限限限限的的的的作作作作业业业业排排排排序序序序问问问问题题题题可可可可描描描描述述述述为为为为：设设设设有有有有n n个个个个作作作作业业业业和和和和一一一一台台台台处处处处理理理理机机机机，每每每每个个个个作作作作业业业业所所所所需需需需的的的的处处处处理理理理时时时时间间间间、要要要要求

20、求求求的的的的时时时时限限限限和和和和收收收收益益益益可可可可用用用用三三三三元元元元组组组组（ti,ti,di,di,pipi），0i0in n表表表表示示示示，其其其其中中中中，作作作作业业业业i i的的的的所所所所需需需需时时时时间间间间为为为为ti ti，假假假假如如如如作作作作业业业业i i能能能能够够够够在在在在时时时时限限限限didi内内内内完完完完成成成成，将将将将可可可可收收收收益益益益pipi，求求求求使得总收益最大的作业子集使得总收益最大的作业子集使得总收益最大的作业子集使得总收益最大的作业子集J J。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3

21、 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,n1且且xixi+1(0in1

22、)，隐隐式式约约束束为为：对对于于选选入入子子集集J的的作作业业（x0,x1,xk），存存在在一一种种作作业业排排列列使使J中中作作业业均均能能如如期期完完成成。问问题题的的目目标标函函数数是是作作业业子子集集J中中全全部部作作业业所所获获得得的的收收益益之之和和，使使得得总总收收益益最最大大的的作作业业子子集集是是问问题题的的最最优优解解。假假如如希希望望以以最最小小值值为为最最优优解解，则则可可以以适适当当变变更更目目标标函函数数，将将其其改改为为未未入入选选子子集集J的的作作业业所所导导致致的损失，即为：的损失，即为：南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3

23、 3月月可可变变大大小小元元组组（x0,x1,xk）表表示示解解，xi为为作作业业编编号。号。显显式式约约束束为为：xi 0,1,n1且且xixi+1(0in1)，隐隐式式约约束束为为：对对于于选选入入子子集集J的的作作业业（x0,x1,xk），存在一种作业排列使存在一种作业排列使J中作业均能如期完成。中作业均能如期完成。问问题题的的目目标标函函数数是是作作业业子子集集J中中全全部部作作业业所所获获得得的的收收益益之之和和，使使得得总总收收益益最最大大的的作作业业子子集集是是问问题题的的最最优优解解。假假如如希希望望以以最最小小值值为为最最优优解解，则则可可以以适适当当变变更更目目标标函函数，

24、将其改为未入选子集数，将其改为未入选子集J的作业所导致的损失，即为：的作业所导致的损失，即为：南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月(X)u(X)(X)c(X)u(X)南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月可变大小元组状态空间树可变大小元组状态空间树 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月9.3.3带时限作业排序算法带时限作业排序算法【程序【程序【程序【程序9 94 4】带时限的作业排序带时限的作业排序带时限的作业排序带时限的作业排序structNodestructNodeN

25、ode(Node*par,intk)Node(Node*par,intk)parent=par;j=k;parent=par;j=k;Node*parent;Node*parent;intj;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月月templatecl

26、assJSpublic: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)

27、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.4

28、0/1背包背包 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月9.4.1问题描述问题描述已已已已知知知知一一一一个个个个载载载载重重重重为为为为M M M M的的的的背背背背包包包包和和和和n n n n件件件件物物物物品品品品，第第第第i i i i件件件件物物物物品品品品的的的的重重重重量量量量为为为为wi(wiwi(wiwi(wiwi(wi0)0)0)0)，假假假假如如如如将将将将第第第第i i i i件件件件物物物物品品品品装装装装入入入入背背背背包包包包，将将将将有有有有收收收收益益益益pi pi pi pi(pipipipi0 0 0 0，0i0i0

29、i0in)n)n)n)。现现现现求求求求一一一一种种种种最最最最佳佳佳佳装装装装载载载载方案，使得总收益最大。方案，使得总收益最大。方案，使得总收益最大。方案，使得总收益最大。例例例例9 9 9 92 2 2 2 设设设设有有有有载载载载重重重重实实实实力力力力为为为为M=15M=15M=15M=15的的的的背背背背包包包包，4 4 4 4件件件件物物物物品品品品的的的的重重重重量量量量为为为为：(w0,(w0,(w0,(w0,w1,w1,w1,w1,w2,w2,w2,w2,w3)=(2,w3)=(2,w3)=(2,w3)=(2,4,4,4,4,6,6,6,6,9)9)9)9)，物物物物品品品

30、品装装装装入入入入背背背背包包包包的的的的收收收收益益益益为为为为：(p0,(p0,(p0,(p0,p1,p1,p1,p1,p2,p2,p2,p2,p3)=(10,p3)=(10,p3)=(10,p3)=(10,10,10,10,10,12,12,12,12,18)18)18)18)。这这这这一一一一0/10/10/10/1背背背背包包包包实实实实例例例例的的的的解解解解为为为为（1,1,1,1,1,1,1,1,0,0,0,0,1 1 1 1），总总总总收益为收益为收益为收益为38383838。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月9.4.2分枝限界法求

31、解分枝限界法求解目标函数：目标函数：目标函数：目标函数：代价函数：代价函数：代价函数：代价函数：若若若若X X是答案结点（叶结点），则是答案结点（叶结点），则是答案结点（叶结点），则是答案结点（叶结点），则c c(X X)=cost()=cost(X X)；若若若若X X是叶结点但非答案结点，则是叶结点但非答案结点，则是叶结点但非答案结点，则是叶结点但非答案结点，则c c(X X)=)=；若若若若X X是非叶结点，是非叶结点，是非叶结点，是非叶结点，则则则则c c(X X)=max)=maxc c(lChild(lChild(X X),),c c(rChild(rChild(X X)。上下界函

32、数：上下界函数：上下界函数：上下界函数：LBB(LBB(X X)、UBB(UBB(X 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/structNode/状态空间树结点状态空间树结点状态

33、空间树结点状态空间树结点Node(Node*par,boollft)Node(Node*par,boollft)parent=par;left=lft;parent=par;left=lft;Node*parent;Node*parent;boolleft;boolleft;南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月templatestructpqNode/活活结点点结构构operatorT()constreturnUBB;pqNode()pqNode(floatcap,Tprof,Tub,intlev,Node*p)cu=cap;profit=prof;l

34、evel=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;南京邮电高校计算机学院南京邮电高

35、校计算机学院 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

36、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;i

37、f(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);i

38、f(LL);returnL;南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月9.5旅行商问题旅行商问题 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月问题描述问题描述旅旅行行商商问问题题（travellingsalesperson）是是一一个个看看似似简简洁洁其其实实特特殊殊难难解解的的著著名名难难题题之之一一，至至今今仍仍有有很很多多人人在在探探讨讨它它。此此问问题题描描述述为为：一一个个旅旅行行商商准准备备到到n个个村村庄庄售售货货。他他从从A村村动

39、动身身经经过过其其它它n-1个个村村庄庄，又又回回到到动动身身地地A村村。现现要要求求一一条条最最短短路路径径，使使得得每每个个村庄都经过且仅经过一次。村庄都经过且仅经过一次。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月9.5.2 分枝限界法求解分枝限界法求解 设设带带权权有有有有向向向向图图G=(V,E)G=(V,E)，|V|=n|V|=n，表表表表示示示示连连接接接接n n个个个个村村村村庄庄庄庄的的的的道道道道路路路路交交交交通通通通图图，边边上上上上的的的的权权值值为为两两两两个个个个村村村村庄庄庄庄间间的的的的路路路路程程程程，cnncnn是是是是该

40、图该图的的的的邻邻接矩接矩接矩接矩阵阵，下面也称代价矩，下面也称代价矩，下面也称代价矩，下面也称代价矩阵阵。旅旅旅旅 行行行行 商商商商 问问 题题 的的的的 解解解解 是是是是 一一一一 条条条条 回回回回 路路路路：（x0,x1,x0,x1,xn,xn1,xn1,xn），x0=xnx0=xn，0 0 xinxin；xixi xjxj，当当当当i i j j和和和和i,ji,j 0,n0,n；xixi+1 E E，0 0in-1in-1。其其其其状状状状态态空空空空间间树树结结构构构构见见图图9 91111的的的的例例例例子子子子。图图中中中中接接接接受受受受的的的的解解解解结结构构构构形形

41、形形式式式式为为（x1,x1,xn-1,xn-1），这这里里里里假假假假定定定定x0 x0 xnxn0 0。本本本本问问题题的的的的目目目目标标函数是路径函数是路径函数是路径函数是路径长长度。度。度。度。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月归约代价矩代价矩阵定定义93假假如如矩矩阵的的一一行行（或或列列）中中至至少少包包含含一一个个零且其余元素均非零且其余元素均非负，则称此行（或列）已称此行（或列）已归约。定定义94假假如如一一个个矩矩阵的的全全部部行行和和列列均均已已归约

42、，则称此矩称此矩阵为归约矩矩阵（reducedmatrix）。）。对矩矩阵的的一一行行（列列）进行行归约，可可以以通通过将将该行行(列列)中中的的每每个个元元素素减减去去该行行（列列）的的最最小小数数进行行，此此最最小小数数称称为该行行（列列）的的约数数。通通过逐逐行行逐逐列列的的归约，可可得得到到一一个个代代价价矩矩阵的的归约矩矩阵。假假定定第第i行行的的约数数为ti，第第j列列的的约数数为rj，0i,jn，则全全部部行行和和列列约数数之之和和称称为矩矩阵约数，数，设为L，。，。南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月对矩矩阵的的一一行行（列列）进行行归

43、约，可可以以通通过将将该行行(列列)中中的的每每个个元元素素减减去去该行行（列列）的的最最小小数数进行行，此此最最小小数数称称为该行行（列列）的的约数数。通通过逐逐行行逐逐列列的的归约，可可得得到到一一个个代代价价矩矩阵的的归约矩矩阵。假假定定第第i i行行的的约数数为titi，第第j j列列的的约数数为rjrj，0 0i,jni,jn，则全全部部行行和和列列约数之和称数之和称为矩矩阵约数，数，设为L L，南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月 南京邮电高校计算机学院南京邮电高校计算机学院 2008 2008年年3 3月月代价矩阵代价矩阵归约矩阵归约矩阵

44、 南京邮电高校计算机学院南京邮电高校计算机学院 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月月