（应用数学专业论文）约束最小生成树算法的研究.pdf

摘要最小生成树问题足一个经典的例络优化问题，目前已有高效的算法在多项式时i b j 内对其进行求解，比如p r i m 算法与k r u s k a l 算法。然而实际问题往往要求对生成树加上一定的限制，形成了一类带有约束的最小生成树问题。度约束最小生成树问题与直径限制最小生成树问题就是这类问题中的两个典型代表，并且在现实生活中具有广泛的应用，例如，通信网络，电路设计，管道铺设等方面。因此，对这两种问题求解算法的研究具有很好的现实意义。本文的主要工作概括如下：首先，针对度约束最小生成树问题，提出了一种新的快速算法。新的快速算法包括两个主要部分：第一部分描述如何构造一棵度约束树：第二部分针对度约束树的构造方式设计了一种改进策略。通过改进策略，获得了近似程度更高的结果。文中给出了算法的有效性证明及其复杂度分析。通过大量的数值实验表明新的快速算法性能良好。其次，针对直径限制的最小生成树问题，在序列编码的基础上设计了一种遗传算法。该算法采用了新的变异算子和局部搜索算子。新的变异算子有效的提高了种群的多样性；基于序列编码方式设计的局部搜索算子产生了适应度更好的个体序列。文中给出了局部搜索算子的有效性证明。大量的数值实验表明该算法是非常有效的。关键词：度约束直径限制生成树算法a b s t r a c tt h ep r o b l e mo fi d e n t i f y i n gm i n i m u ms p a n n i n gt r e e ( m s t ) o fac o n n e c t e d ，u n d i r e c t e dg r a p hi sac l a s s i c a ln e t w o r ko p t i m i z a t i o np r o b l e mw h i c hc a nb es o l v e de f f i c i e n t l yi np o l y n o m i a lt i m eb yk r u s k a la l g o r i t h ma n dp ma l g o r i t h m 。u n f o r t u n a t e l y , p r a c t i c a lp r o b l e m so f t e nn e e ds o m ec o n s t r a i n t so nt h es p a n n i n gt r e e ，t w ot y p i c a lr e p r e s e n t a t i v e so ft h e s er e l a t e dp r o b l e m sa r et h ed e g r e e c o n s t r a i n e dm i n i m u ms p a n n i n gt r e ep r o b l e ma n dt h eb o u n d e d - d i a m e t e rm i n i m u ms p a n n i n gt r e ep r o b l e m ，t h e yh a v e w i d ea p p l i c a t i o n si nt h er e a lw o r l d ，s u c ha sc o m m u n i c a t i o nn e t w o r k s ，c i r c u i td e s i g n ，p i p e l i n el a y i n ga n ds oo n s o ，i t so fp r a c t i c a ls i g n i f i c a n c ef o ru st os t u d yt h es o l u t i o na l g o r i t h m s t h em a i nw o r ki ss u m m a r i z e da sf o l l o w s ：f i r s t l y ，an e wf a s ta l g o r i t h mi sp r o p o s e df o rt h ed e g r e e - c o n s 拄a i n e dm i n i m u ms p a n n i n gt r e ep r o b l e m t h en e wf a s ta l g o r i t h mc o n s i s t so ft w om a j o rp a n s t h ef i r s tp a r td e s c r i b e sh o wt oc o n s t r u c tad e g r e e c o n s t r a i n e dt r e e t h es e c o n dp a r tp r e s e n t sa ni m p r o v e m e n ts t r a t e g yb a s e do nt h ed e g r e e c o n s t r a i n e dt r e eo b t a i n e df r o mt h ef i r s tp a r t b yt h ei m p r o v e m e n ts t r a t e g y , w ec a l lo b t a i nab e t t e rs o l u t i o n t h ec o m p l e x i t yo ft h ea l g o r i t h mi sa n a l y z e da n dt h ev a l i d i t yt h e o r e mi sp r o v e d 。m a n yn u m e r i c a lt e s t ss h o wt h a tt h en e wf a s ta l g o r i t h mh a sv e r yg o o dp e r f o r m a n c e s e c o n d l y , ag e n e t i ca l g o r i t h mf o r t h eb o u n d e d d i a m e t e rm i n i m u ms p a n n i n gt r e ep r o b l e mi sd e s i g n e db a s e do nap e r m u t a t i o nc o d i n gs c h e m e t h ea l g o r i t h ma d o p t san e wm u t a t i o no p e r a t o ra n dal o c a ls e a r c hs c h e m e t h en e wm u t a t i o no p e r a t o ri m p r o v e st h ed i v e r s i t yo ft h ep o p u l a t i o ne f f e c t i v e l y , a n dt h el o c a ls e a r c hs c h e m eb a s e do nt h ep e r m u t a t i o nc o d i n gs c h e m ec a no b t a i na ni n d i v i d u a lw i t hab e t t e rf i t n e s s a tt h es a m et i m e t h ev a l i d i t yo ft h el o c a ls e a r c hs c h e m ei sp r o v e d al a r g en u m b e ro fe x p e r i m e n t ss h o wt h a tt h eg e n e t i ca l g o r i t h mi sv e r ye f f e c t i v e k e y w o r d s ：d e g r e e - c o n s t r a i n e db o u n d e d - d i a m e t e rs p a n n i n gt r e ea l g o r i t h m西安电子科技大学学位论文创新性声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：- y _ 亥东同期兰丝2 ：! ：! !西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期l 白j 论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。( 保密的论文在解密后遵守此规定)本人签名：导师签名：r 期印? 2 ：! ：纩笫一章绪论第一章绪论本章主要介绍了网络优化的应用背景及研究现状。首先阐述了网络优化研究的典型闷题，然后筒述了算法复杂性的分析方法，最后列出了本文的内容提要和章节安排。1 1 引言随着社会的发展和科技的进步，网络优化的理论与方法已经广泛的渗透于运筹学、信息论、控制论、管堙科学和计算机科学等领域，并在工程技术、经济、军事等诸多方面都有着极为重要的应用。现代社会在很大程度上是一个由通讯网络，运输购终，熊源和物资分配网络构成的巨大的复杂系统。潮络优化能为人 j控制和管理这个系统提供种有效的方法。由于大规模网络优化问题的需要，研究各种有效的算法一直是嘲络优化婿究的一个主旋律。人们发现，网络最优化中的许多问题很难找到有效的算法，也不知道它们是否存在有效算法，这使得计算复杂度和近似算法的研究受到普遍的重视。这两者的结合正是当前网络优化研究的潮流。许多网络优化问题是n p 。h a r d 问题，也是科学和工程计算中重要和基本的问题，这类问题的求解一直是算法研究领域的热点闽题。虽然n p h a r d 闻题j 基常难解决，但在实际应用中我们不得不去处理这些问题。对于n p h a r d 的网络优化问题，一般采j 鼋近似算法来解决。近年来，许多学者把研究的重点放在求解网络优化难题的一些新型启发式算法上，如禁忌搜索、模拟退火算法、遗传算法、蚁群算法等，这些算法被称为现代启发式优化算法。这些算法是2 0 世纪8 0 年代初兴超的，在理论和实际应用方面都取得了较大的发展，并且有一个共同的目标获得n p h a r d 网络优化问题的全局最优解。本文将启发式算法应用在一些复杂的网络优化问题上，显示出其强大的生命力和美好的发展潜力。1 2 网络最优化问题自从克西荷夫运用图沦从事电路网络的拓扑分析以来，尤其是近几十年，网络理论的研究和应用十分弓1 人注目。电路网络、运输网络、信息网络等与工程秘应用紧密相关的课题受到了高度的蘑视。其中，多数的问题都与优化相关，涉及到问题的费用、容量、可靠性和其他性能指标，有薰要的应用价值。下面我们给约束最小乍成树算法的研究出一些经典的实例。一最小树问题假设要在力个城市之间建立通信联络网，则连通门个城市只需要r l 一1 条线路。这时自然会考虑这样一个问题，如何在最节省经费的自仃提下建立这个通信网。在每两个城市之问都可以设置一条线路，相应地都要付出一定的经济代价。门个城市之i 日j 最多可能设置n ( n 一1 ) 2 条线路，那么如何在这些可能的线路中选择r l 一1 条以使总的耗费最小昵?可以用连通网络来表示疗个城市以及聆个城市之问可能设置的通信线路，其中网络的顶点表示城市，边表示两城市之问的线路，赋给边的权值表示相应的代价。刀个顶点的连通网络可以建立许多不同的生成树，每棵生成树都可以是一个通信网。现在我们要选择这样一棵生成树，也就是使总的耗费最少。这个问题就是构造连通网络的最小代价生成树问题，简称为最小树问题。最小树问题是一个历史悠久的网络优化问题，而现实生活中遇到的问题，往往要求对生成树加上一定的限制，形成了一类带有约束的最小生成树问题。对约束最小生成树问题的算法研究常常是基于最小生成树的经典算法。二最短路问题交通网络中常常提出这样的问题：两地之i 日j 是否有路可通? 在有几条通路的情况下，哪一条最短? 交通网络可以画成赋权图，图中顶点代表城镇，边代表城镇| 兀j 的公路，边上的权表示公路长度。前面提出的问题就是赋权图中求最短路径的问题，即求两个顶点问的长度最短的链。这里链的长度指的是链上所包含的边的权值总和。最短路问题是网络优化中一个很重要，很基本的课题。许多网络优化问题可以转化成最短路问题、或者利用最短路算法作为其子程序。比如，网络流问题，中国邮递员问题和旅行售货员问题等。因此最短路的用途已远远超过了其直观意义。三关键路径问题一项大的工程往往由许多作业环境构成，其中某些作业可以同时进行，某些作业之间却有着依赖关系，必须按一定先后顺序执行。例如一项建筑工程涉及到采购材料、平整地基、预制构件、埋设管道、砌墙立屋等多项作业。其中平整地基和预制构件可以同时进行，而室内装修却须待砌墙立屋之后才能动工等等。这自然就提出一个问题，要怎样合理安排才能使工期最短? 此外，有的工程还有别的限制条件，如r 期限制，经费预算限制等，这又涉及到如何安排才能使成本最低并且符合工程限制条件? 这些i 、口j 题可以转化为网络图论中的关键路径问题加以解决。四中国邮递员i u j 题第一章绪论一个邮递员送信，要走完他负责投递的全部街道，完成任务后西j 到邮局，应按怎样的路线走，他所走的路程j 会最短l ! j i ：? 如果将这个问题抽象成图论语言，就是给定个连通图g ，g 的每条边的权值为对戍的街道长度( 距离) ，中国邮递员问题就是要在图g 中找一条闭途径p ，使它包含g 的每条边至少一次，而且尸所包含的边的权总和最小。五旅行售货员问题旅行售货员问题也称为货郎担问题。有一个售货员，从他所在城市出发去访问刀一1 个城市，要求经过每个城市恰好一次，然后返回原地，问他的旅行路线怎样安排才最经济( t i p 线路最短) ?这个问题用图论术语叙述就是：g = ( v ，e ，w ) 是门个顶点的赋权完全图，这里v = h ，屹，k 是城市的集合，是连接城市的道路的集合，w 是从e 到正实数集合的一个函数( 即“h ，v ，) 是城市v 与y ，之间的距离) ，显然对v 中任意三个城市u ，v i ，屹，显然它们之f n j 的距离应满足三角不等式：以v ，v ，) + 叫y ，峪) 以坼，v k )( 1 1 )求出该赋权图上的最短哈密尔顿回路。上面血个问题是网络最优化的几个基本问题，除此以外，还有最大流问题，最小费用流问题和最小费用循环流问题等，从这些问题中可以看出网络最优化在实际问题中的广泛应用。在经济管理等很多领域早，网络最优化也是一种有效的手段，它可以帮助我们提高效率、节省丌支，因此，这是一个实用性很强的数学分支。1 3 算法及算法分析所谓最优化就是使目标函数在约束条件下达到最小值或最大值。网路优化主要是研究网络优化问题的计算方法。可以把解决某个问题的计算方法称为适用于该问题的算法。一般的说，算法就是一组可行的，确定的，有穷的规则。对于属于它解决范围的每个实例，任何人只要会正确的执行规则要求的操作，并遵循规则的指示一步一步的进行，在有限步后就能得到该实例的完善，j 下确的答案。因此，算法可以由计算机来执行。1 3 1 算法的五个重要特性l 有穷性一个算法必须总是( 对任何合法的输入值) 在执行有穷步之后结束，且每一步都可在有穷时间内完成：2 确定性算法每一条指令必须有确定的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。约水最小生成树算法的研究3 可行性一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。4 输入一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。5 输出一个算法有一个或多个输出。这些输出是同输入有着某些特定关系的量。1 3 2 算法的设计要求通常设计一个“好 算法应考虑到以下标准：( 1 )正确性算法应当满足具体问题的需求。通常一个大型问题的需求，要以特定的规格说明方式给出。目前多数是用自然语言描述需求，它至少应当包括对于输入、输出和加工处理等的明确的无歧义性的描述。设计或选择的算法应当正确地反映这种需求，否则，算法的正确与否的衡量标准就不存在了。( 2 ) 可读性算法主要是为了人的阅读与交流，其次a 是机器执行。可读性好有助于人们对算法的理解，晦涩难懂的程序易于隐藏较多的错误，从而难以调试和修改。( 3 ) 健壮性当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。例如，一个求凸多边形面积的算法，是采用求各三角形面积之和的策略来解决问题的。当输入的坐标集合表示的是一个凹多边形时，不应继续计算，而应报告输入出错。并且处理出错的方法应是返回一个表示错误或错误性质的值，并终止程序的执行，以便在更高的抽象层次上进行处理。1 3 3 算法复杂度计算复杂性的问题，属于计算理论中的一个重要领域，它是由对有效算法的需求而发展起来的，产生于上世纪六十年代，繁荣于七八十年代。在计算复杂性领域中，研究的主要目的是一个算法所需要的时间和空间，即当给出合法的输入时，为了得到输出，该算法所需要的时间和空问。设z ( ，1 ) 和正( 刀) 是定义在萨整数集上的两个正实值函数，如果存在一个常数c o ，使得当刀足够大时有石( 门) 呒( 门) ，则记z ( 刀) = o ( 正( ，1 ) ) 。用这个记号来描述算法的复杂性，可以使复杂性的表达式得以简化。若一个算法的复杂性f ( n ) 是r i的多项式函数，则称这个算法是有效的或有多项式界的，有时也简单的说这个算法是好算法或多项式算法。我们把不是有效的算法称为无效的或无多项式界的。无效算法的一类典型代表是指数算法，即复杂性f ( n ) 是门的指数函数的算法。因为，对于任意给定的正数o t 和a 1 ，当刀足够大时，刀。 a “。所以，当实例的规第一章绪论模门增大时，任意一个多项式算法终将变得比任何指数算法更有效。这就是把多项式算法称为有效算法的原因之一。一般情况下，算法的基本操作重复执行的次数足问题规模门的某个函数f ( n ) ，算法的时i b j 量度i - d 作r ( n ) = d ( ( 玎) )( 1 2 )它表示随问题规模玎的增大，算法执行时间的增长率和f ( n ) 增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。类似于算法的时i n j 复杂度，空间复杂度作为算法所需存储空间的度量记为s ( ，1 ) = 0 ( 厂( ，z ) )( 1 3 )其中疗为问题规模。一个上机执行的程序除了需要存储空问来寄存本身所用的指令、常数、变量、输入的数据外，也需要一些对数据进行操作的工作单元和存储一些实现计算所需信息的辅助空问。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空问，否则应同时考虑输入本身所需空间。1 4 研究现状最小生成树( m i n i m u ms p a n n i n gt r e e ，简称m s t ) 问题i zj 是网络优化中一个常见的基本问题，已有成熟的算法可以进行有效的求解。直径限制最小生成树问题与度约束最小生成树问题是最小生成树问题的两个拓展问题。直径限制最小生成树问题要求在给定的图中寻找满足直径限制的权值最小的生成树，对于一般情况，当4 d ，其t o o i中唿= ( 磁，螺) 。曝，。令s + ；= u ，量+ ；= 易u 唆 ，转s t e p l 。2 4 求解复杂网络优化问题的遗传算法简介随着网络优化问题规模的扩大，网络优化问题搜索空i 日j 的急剧扩大，在现有的计算机一 ：用枚举法很难，甚至是不可能缛到其精确最优解。对于这类复杂闷题，第一：章图0 0 网络n 勺基本理论人们已意谚 到应把精力放到寻求其满意解上，而遗传算法则是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于网络优化问题中的n p h a r d 问题的近似求解菲常有效。遗传算法是从代表问题i 能潜在解集的一个种群( p o p u l a t i o n ) 丌始的，而一个种群则内经过编硬3 ( c o d i n g ) 的一定数髫的个体( i n d i v i d u a l ) 组成。轫始种群产生之籍，按照适者生存和优胜劣汰的原理，逐代( g e n e r a t i o n ) 演化产生嗽越来越好的近似解。在每一代，根据阅题域中个体的适应度( f i t n e s s ) 大小挑选( s e l e c t i o n ) 个体，并借助于自然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c f o s s o v e f ) 和变异( m u t a t i o n ) ，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后尘代种群t l f i ；j 代更加适凌环境，末代种群中的最优个体经过解蚕l - q ( d e c o d i n g ) ，n - i以作为问题近似最优解。2 4 。l 遗传算法的框架第1 步随机产生初始种群，个体数目一定。第2 步计算今体的适应度，并判断是否符合优化准剃，若符合，输出最佳个体及其代表的最优解，并结束计算；否则转向第3 步。第3 步依据适应度选择再生个体，适应度高的个体被选中的概率嵩，适应度低的个体可能被淘汰。第4 步按照一定的交义概率和交叉方法，生成新的个体。第5 步按照一定的变并概率和变异方法，生成新的个体。第6 步由交叉和变异产生的新代种群，返回到第2 步。2 4 2 遗传算法中的优化准则一般依据问题的不同有不同的确定方式。例如可以采用以下的准则之一作为判断条件：1 种群中个体的最大适应度超过预先设定值。2 ，种群中的平均适应度超过预先设定的值。3 世代数超过预先设定值。2 4 。3 遗传算法的基本操作1 编码当膈遗传算法求解问题时，必须在基标问题实际表示与遗传算法的个体结构之问建立联系，即确定编码和解码运算。一般来说，由于遗传算法计算过程的鲁棒性，它对编码的要求并不苛刻，但编码的策略对于遗传算子，尤其是对交叉和变异算子的功能和设计有很大的影响，用户应斟酌确定。理沦上而言，编码应浚适合要解决的触题，而不是简单的描述问题。问题的约水最小生成树锋法的研究编码一般考虑以下几个舰则：( 1 ) 完全性( c o m p l e t e n e s s ) 原则上，分铝在所有问题域的懈都可能被构造出来。( 2 ) 封闭性( c l o s u r e ) 每个编码对应一个可接受的个体，封闭性保i 正系统从不产生无效的个体。( 3 ) 紧致f 生( c o m p a e t n e s s ) 若两种编码g i 和9 2 都被解码成相同的个体，若g i 比g ：所占鲶空问少，就认为g ，l l g ：紧致。( 4 ) 可扩展性( s c a l a b i l i t y ) 对于具体的问题，编码的大小决定了解码的时间，两者存在一定的函数关系，若增加一种表现型，作为个体的编码大小也做出相应的增加。除了上面几个特性外，还包括多麓性( m u l t i p l i c i t y ) ，个体可塑性( f l e x i b i l i t y ) ，模块性( m o d u l a r i t y ) ，冗余性( r e d u n d a n c y ) ，复杂性( c o m p l e x i t y ) 。2 。初始种群的产生初始群体中的每个个体般都是逶过随机方法产生，群体规模在足十到几百之i 日j 取值，根据问题的复杂程度不同而取值不同。种群规模的选敢一般遵循以下两个规则：( 1 ) 问题越难，种群规模应适当大一些。( 2 ) 利用已有的信息，尽量减少，一般取值范蹶为几十到几百。3 适应度函数遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用季孛群中每个个体的适应度值柬进行搜索。因此适应度的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的。对强标函数值域的某种映射变换称为适应度的尺度变换。适应度函数的设计主要满足以下条件：( 1 ) 单值、连续、毒 负、最大化。( 2 ) 合理、一致性：要求适应度值反映对应解的优劣程度。( 3 ) 计算量小；适应度函数的设计应尽可能的简单，这样可以减少计算时间和空| 珏j 上的复杂性，降低计算成本。4 遗传操作( 1 ) 选择选择过程的第一步是计算适应度。在被选集中每个个体具有一个选择概率，这个选择概率取决于种群中个体的适应度及其分席。爱酶常用静选择方法有：轮盘赔选择法，随机遍历抽样法，局部选择法，锦标赛选择法。( 2 ) 交叉交叉是把两个父个体的部分结构加以替换霭组而生成新个体的操作，交叉的第一：章幽与网络的壁本理论目的是为了能够在下一代产生新的个体，就像人类社会的婚姻过程。通过重组交叉操作，遗传算法的搜索能力得以飞跃地提高。交叉是遗传算法获得新优良个体的最重要的手段。常用的交义包括：单点交叉、多点交叉、均匀交叉、部分匹配交叉、顺序交叉等。( 3 ) 变异交叉之后是子代的变异，子代个体以很小的概率或步长产生转变。变异本身是一种局部随机搜索，与选择，交叉算子结合在一起，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力，同时使得遗传算法保持了种群的多样性，以防止出现非成熟收敛。在变异操作中，变异概率不能取得过大，如果变异率大于0 5 ，遗传算法就退化为随机搜索，而遗传算法的一些重要的数学特征和搜索能力就不复存在了。常用的变异算子有：位点变异、插入变异、对换变异、边界变异、非均匀变异、高斯变异等。2 5 小结本章首先介绍了关于图与网络的基础知识，然后介绍了关于最小生成树问题的经典算法及理论基础，最后介绍了求解网络优化中n p h a r d l h 题常见的遗传算法框架及基本操作。第章度约水最小生树算法的研究第三章度约束最小生成树算法的研究本章首先介绍了研究度约束最小生成树问题的经典算法，在此基础上提出了求解该问题的新的快速算法，大量的数值实验表明，该算法的性能良好。同时算法中的改进策略对d p r i m 算法的改进效果也十分明显。最小生成树问题( m i n i m u ms p a n n i n gt r e ep r o b l e m 简称m s t ) 是网络优化中遇到的重要问题之一，到目前为止，人们对最小生成树问题进行了大量的研究，产生了许多算法，比如经典的p n m 算法，k r u s k a l 算法，破圈法等。然而，实际问题常常要求对生成树中各顶点的度数加上一定的限制，一般情况下，该问题是一个n p h a r d 问题。这种带有顶点度约束的最小生成树问题被称为度约束最小生成树( d e g r e e c o n s t r a i n e dm i n i m u ms p a n n i n gt r e e ，d c m s t ) t 司题【2 0 】。在现实世界中，有许多这样的例子。比如：道路系统设计中多数情况是两条路构成的十字路口；通信网络中为了防止节点故障带来的脆弱性，对节点的度也有一定的限制。另外，在电路设计、管道铺设、计算机网络中也经常用到。3 1 1 度约束最小生成树的数学模型连通图g = ( v ，e ，) ，其中矿= h ，v 29 o 9 k 是顶点的有限集合，e 是边的有限集合。= ( w j 。表示权矩阵且= w j , ，w i i = + o o 。并设各顶点的度约束为抚( i = 1 ，2 刀) ，则d c m s t 问题的模型为：m i nz = w w j 驴( 3 一1 )j - ，石仃sb fi g= iz - 1si - 1 ，v scy ，s o，e s( 3 2 )( 3 3 )这晕，变量= ：凳? 在最优树中isf 为集合s 中所含图g 的顶点个数，约束( 3 2 ) 为度限制，约束( 3 3 ) ，( 3 4 ) 保证了所得的是一棵生成树。4一，j矿l，一力u=叽一vx。川b。川1 8约水最小生成树算法的研究3 1 2 现有的求解度约束最小生成树的快速算法1 求解度约束最小生成树的d p r i m 算法i o jd - p r i m 算法的主要思想是：在不违反度约束的前提下，每次找出距离当前树最近并且不属于当自矿树的顶点，将其加入到当日订树中，直至获得一棵生成树。若将初始点遍历v 中各点，然后在所得的行个解中( 或至多疗个解中) 取最好的一个，就可以得到我们所需的解。d - p r i m 算法步骤：s t e p1 初始点s - - - l ；s t e p2 最近邻点n ，卜0 ；顶点度d e g ，4 - - 0 ( i v ) ；s t e p3 置聆，卜s ，最近距离d i6 - - 叱f ，( f v s ) ；s t e p4当前树顶点集巧 - - j ，当前树边集辱卜a ；s t e p5找使得m i n d ；i d e g f 岛，d e g 仉吃，f y 一，f s 的下标“；s t e p6 若以= 0 0 或t 。= 0 ，则g 不连通或搜索失败，程序停止；s t e p74 - - - 巧u “ ，辱4 - - bu ( ”，t 。) ，d e g 。 - - - d e g 。+ 1 ，d e g 儿6 - - d e g + l ；s t e p8v k v 一，若w k 0 ，t i 转，否则转20s t e p 3s t e p 2 ：s t e p 2 扛i + 1 。若，m ，转s t e p l ；s t e p 3令i + i = 乙+ 乞，t l , = l i i 一1 ，t = t 6 一l ，j = j + l ；s t e p 4 若，= t 一l ，结束，r 是近似最优解；否则转s t e p 2 。启发式思想对于求解n p h a r d 问题是十分有效的。文献 1 0 】基= = p r i m 算法的思想提出了度约束最小生成树的快速算法( d p r i m ) ，取得了良好的结果，但仍存在一定的不足，算法每次找距离当日，j 树最近且不属于当前树的顶点，这样做常常注重了权而忽略了度。文献【2 l 】中基- i ：k r u s k a l 算法的思想提出了另一种快速解法( d - k r u s k a l ) ，在不违反度约束和不形成圈的日，j 提下，每次加入权值最小的边。文献第章度约束最小生树算法的研究1 92 2 针对度约束最小牛成树的特征，设计了一种新的编码方式，并在此基础上提出了新的遗传算法求解陔问题，取得了较好的结果。虽然遗传算法在求解度约束最小生成树问题的精确度 上：要比一般的快速算法高，但是对于大规模问题，遗传算法的效率要比快速算法低很多，因此研究快速算法具有很好的现实意义。本章基于启发式思想提出了求解该问题的新的快速算法( ( n e wf a s t a l g o r i t h m ，n f a ) ) ，该算法主要包括两个部分：度约束树的构造( d e g r e e c o n s t r a i n e dt r e ec o n s t r u c t i o n ，d c t c ) , 乖u 改进策略( i m p r o v e m e n ts t r a t e g y ，i s ) 。数值实验表明，新的快速算法对于求解度约束最小生成树问题是十分有效的。近年来研究旅行售货员问题的智能算法【2 3 。4 j f 艮多。求解度约束最小生成树的算法经过修改可以得到求解旅行售货员问题的一种近似快速算法：首先置各项点的度限制为2 ，这时算法求得的是一棵线性树，最后将该线性树的两个悬挂点相连，就得原t s p 问题的近似最优解。3 2 度约束树的构造1考虑权值的度约束树的构造( d c t c i )构造思想：由g 的一棵最小生成树r 出发，对r 中违背度约束的顶点，每次去掉一条与它关联的权值最大的边，添加一条不违背度约束条件的权值最小的边，直到顶点满足度约束限制为止。算法如下：s t e p0图g 的权矩阵为，最小生成树r 。度约束色，f v ，t 中顶点的度记为以，t i = 岛- d i ，f = l ；s t e pl如果f = n 则转s t e p2 ；s t e p2如果 0 ，j = l ，2 _ ，l ，t = r 一气矗，t i = t ，+ 1 ，t ，= t ，+ l ，否贝u ，i = f + l ，转s t e pi ；s t e p3u = iu 与v 连通，e t t 0 ，v = y ，l 匕与连通，_ r t ， 0 ) ；s t e p4w i , ，= m i n l w 0v u ，v ，t = 丁+ ( ，z ) ，= t i t 一1 ，t = t 一l ，f = f + 1 ，转s t e p l 。2 不考虑权值的度约束树的构造( d c t c 2 )s t e p0设图g 的顶点集为v ，边集为e ，度约束包，i v ，b = a ；s t e p1随机从中选择一条边( i ，_ ，) ，如果顶点，的度d e g ( i ) 与顶点的度d e g ( j ) 分别满足d e g ( i ) 包和d e g ( j ) 0 ，v = v ，l ，与k 连通，且f ， 0 ：s t e p5若f l a g = l ，煲lw , o 矗= m i n w u | 哆u ，匕y ，巧且匕 ；否煲#w , o 矗= m i n w oiv u ，v j v 。t = ，+ ( k ，) ，坛= 气一1 ，t 如= o 矗一l ；s t e p6t e d g e = t e d g e - e ，若t e d g e o ，则从t e d g e 中选择一条边e = ( v 卅，k ) ，f l a g = 0 ，转s t e p4 ，否则转s t e p7 ；s t e p7 若v ( t ) 0 ，v = v jl ，与吃连通，且f ， 0 ；s t e p5w o ，o = m i n w o | v u ，0 毯y ，t = r + ( 、，v 南) ，气= 气一l ，t 南= t 矗一l ，第二章度约束最小生树算法的研究i = i + 1 ，转s t e p3 ：s t e p6如果缈( 丁) 形( 0 ) ，转s t e p1 ；否则终止。3 4 算法的有效性和复杂度分析定理3 1 ( d c t c l 的有效性定理) 如果模型( 3 1 1 ) 中各顶点的度约束反2 ，( i = 1 ，2 ，t 1 ) ，贝j j d c t c i 最后产生一棵度约束树。证明：d c t c l 由一棵最小生成树出发，将不满足度约束的顶点，删除与其关联的边后，将树分成两个子树，每个子树中至少分别存在一个度不大于l 的顶点，即算法中的u 0 ，且v g 。因此可以从边割 u ，v 】中选出一条边添加到图中后，使不满足度约束的顶点的度得到降低。通过不断对不满足度约束的顶点进行降度，最后获得一棵满足度约束条件的生成树。定理3 2 ( d c t c 2 的有效性定理) 如果模型( 3 1 1 ) 中各顶点的度约束岛2 ，( i = 1 ，2 ，刀) ，贝j j d c t c 2 最后产生一棵度约束树。证明：由于s t e pl 中要求加入图丁中的边关联的顶点在7 中不连通，即加入该边后图丁不形成圈，因此如果经过有限步循环后不能获得一棵树，那么获得的图丁将是一个森林。假设石和瓦是任意两棵子树，则必存在度为1 的顶点m 正及v 2 乃，因为( m ，) 可以添加到图r 中，所以石和正应当是一棵子树，与假设z 和五是两棵子树矛盾。因此经过有限步循环后获得的是一棵树，又因为s t e pl 中对添加的边的顶点的度的限制，所以获得的树是一棵度约束树。在3 - 3 中，两种改进策略关键在于计算集合u 和v ，而计算这两个集合采用广度优先搜索的运算量为o ( n 2 ) ，因此两种改进策略的时间复杂度分别为o ( n 4 ) 和o ( n 3 ) 。从d c t c l 的流程很容易看出算法的时间复杂度为o ( n 3 ) 。d c t c 2 的时间复杂度为o ( n 2 ) 。新的快速算法是由d c t c i 与i s l 构成的，记为n f a ；由d c t c 2 与i s 2 构成的近似算法与n f a 类似，只是度约束树的产生具有一定的随机性，因此称为随机近似算法，记为r f a 。3 5 数值实验例3 1 给定图g 的权矩阵( 取自文献 9 】) 如下：度约束6 f = 3 ( f 1 ，2 ，9 )2 2约水最小生成树算法的研究w =解：由n f a 求得的近似最优解为：e t = ( 1 ，3 ) ，( 2 ，3 ) ，( 2 , 4 ) ，( 2 ，5 ) ，( 4 , 6 ) ，( 4 , 7 ) ，( 7 ，8 ) ，( 7 ，9 ) ，近似最优值为3 4 。例3 2 给定图g 的权矩阵如下：度约束岛= 2 ( f = 1 ，2 ，9 )=解：由r f a 求得的近似最优解为：e t = ( 1 ，4 ) ，( 1 ，7 ) ，( 2 ，6 ) ，( 2 ，8 ) ，( 3 ，7 ) ，( 3 ，8 ) ，( 4 , 9 ) ，( 5 ，6 ) ，近似最优值为8 4 。例3 3 为了测试n f a 算法的性能，以及对度约束色的敏感程度，给出了大量随机算例，它们的规模分别为5 0 、6 0 、7 0 、8 0 和9 0 ，算例分别记为r 5 0 、r 6 0 、r 7 0 、r 8 0 和r 9 0 。其中权矩阵h q 0 ，1 0 0 的伪随机数构成，算法的性能指标同文献 2 l 】，r = r r 为算例的均值( 样本数取为1 0 ) ，。和分别为其最小值和最大值。表3 1 比较结果( 随机产生权矩阵)岛= 2包= 3包= 4刀。，。，厂帕。rr 5 01 6 9 2 42 3 5 4 82 6 0 5 l1 0 4 1 71 1 1 2 61 1 8 2 31 0 0 0 01 0 2 3 71 0 6 7 2r 6 01 7 0 4 32 1 1 9 32 9 5 3 31 0 7 1 61 1 5 3 21 1 7 9 21 0 0 0 21 0 3 5 31 1 2 1 6r 7 01 8 6 7 42 0 6 8 72 5 4 2 61 0 4 0 51 1 0 3 81 1 9 4 l1 0 0 0 01 0 2 0 41 0 8 1 3r 8 02 0 6 3 92 2 7 6 93 0 7 3 81 0 2 8 l1 1 0 6 41 1 6 3 41 0 0 0 01 0 3 0 31 0 7 4 6r 9 01 9 6 0 02 2 9 5 22 8 1 4 51 0 4 3 41 1 0 8 61 1 9 7 61 0 0 0 41 0 2 7 11 0 4 3 8乃旧mh 8m 孔悸毖眩加m6 m他7 俗294685492 埒4m m9d7：29 加527722 坦m327b9 坫勉m322947 博侈335m5 挖扒乃6m 拍5 鲳9 儿弘88 如弘砣”儿8 扒5 如弛 9m加弘6弛砣拍殂弘6如硒弘4 挖m弘拍5如5勰5m扒加扒8弱拍5砣拍弘加8m拍勰48”6第j 章度约束最小生树算法的研究表3 2 比较结果( 随机产生权矩阵)扫= 5莎= 6厶= 7刀。，。，。，。r 5 01 0 0 0 01 0 0 1 11 0 0 7 31 0 0 0 01 0 0 0 01 0 0 0 01 0 0 0 01 0 0 0 01 0 0 0 0r 6 01 0 0 0 01 0 0 8 51 0 3 l o1 0 0 0 01 0 0 2 21 0 1 6 71 0 0 0 01 0 0 0 01 0 0 0 0r 7 01 o o o o1 0 0 2 71 0 1 7 81 0 0 0 01 0 0 0 0t 0 0 0 01 0 0 0 01 0 0 0 01 o o o or 8 01 0 0 0 01 0 0 0 21 o o l 71 0 0 0 01 0 0 0 31 0 0 2 91 0 0 0 01 o 0 0 01 0 0 0 0r 9 01 0 0 0 01 0 0 3 21 0 1 1 81 0 0 0 01 0 0 0 11 0 0 1 51 0 0 0 01 0 0 0 01 0 0 0 0算例分析：从上述结果可以看出，随着度约束范围的增大，通过快速算法获得的度约束最小树越来越接近最小生成树。例3 4 下面给出r f a 算法的性能测试，测试方法同例3 3 。表3 3 比较结果( 随机产生权矩阵)厶= 2扫= 3厶= 4刀。，厂舢。，。，r 懈r 5 01 5 6 3 42 4 5 4 02 9 1 8 31 0 2 8 81 0 7 9 81 1 4 5 71 0 0 0 01 0 0 9 01 0 2 2 lr 6 01 8 5 3 82 6 1 4 53 1 7 7 91 0 6 8 71 1 1 9 01 2 8 4 41 0 0 0 01 0 1 3 81 0 7 1 9r 7 02 0 4 3 62 9 7 1 23 5 3 6 61 0 2 3 01 0 9 6 91 1 8 5 l1 0 0 0 01 0 1 8 81 0 3 9 1r 8 02 1 2 6 92 8 1 2 83 5 9 2 91 0 4 6 51 1 0 9 91 2 1 0 31 0 0 0 01 0 1 3 91 0 4 5 0r 9 02 4 2 9 53 0 9 4 64 0 8 0 41 0 2 0 81 1 0 7 81 2 0 8 01 0 0 0 61 0 2 9 71 1 0 1 2表3 4 比较结果( 随机产生权矩阵)6 j = 5包= 6包= 7刀。，。，名。，r 5 01 0 0 0 01 0 0 0 51 0 0 5 31 0 0 0 01 0 0 0 01 0 0 0 01 0 0 0 01 0 0 0 01 0 0 0 0r 6 01 0 0 0 01 0 0 5 31 0 2 6 21 0 0 0 01 0 0 2 81 0 2 8 01 0 0 0 01 0 0 0 01 0 0 0 0r 7 01 0 0 0 01 0 0 1 71 0 1 2 71 o o o o1 0 0 2 21 0 1 7 01 0 0