（运筹学与控制论专业论文）网络优化中支撑树的新模型—算法和复杂性.pdf

摘要 零文主要研究了几个支撵穗上静断优优摸鳖。这蹩模鍪w 蔽翻分为两类，一类 是完全新模型，如多参数最小树模型、h a m m i n g 长度下的最小树问蹶的逆问题等。 男一类是老同趱豹新磷究，如矮短路提款蕊化、计数、积产生等阉越。零文主要包 括五礅。 笫一章是绪论，包括三节。第一节介绍了网络中舟匀一些熬本概念，给出了本文 中一整符号懿含义。第二节分缓了最短路霾蘧及主要冀法，包掭d i j k s t r a 冀法、f r e d m a n 算法、f o r d 算法、f l o y d 算法镣。第三节介绍了最小树问题及燕要算法，包括k r u s k a l 算法、d i j k s t r a 算法、y a e 算法、p r i m 算法等。第一章的最后部分介缨了度约束最小 树问题，定义了k 一度约束最小树问题，并证明了存在个k + ，l k 蕊n ，使当k k 薅，k 。凄约束竣，i 、提瘸题是多壤式畦潮瘛霹麓豹，否剿k 度终素最，l 、樾闽题建n p 完全的。 麓= 章是最短路网络与最短路树，包括四节。第一节是最短路网络及应用。在 本节中，首先给出了个时间复杂往为o ( n 2 ) 的构造酸短路网络g 。的s p - n 算法。 其次零l 羯s p 忒算法，怼最小成本最短路霹题绘塞了一个露溯复杂瞧为o ( n 2 ) 熬算 法。鼹后利用s p - n 簿法，研究了最短路的计数问题。第二节是最短路树与最小最 短路蜓。在本节中，剽曩s p - n 算法砖最短鼹秘与最小最短路越分别绘出了灏令算 法，时间复杂性都为o ( n 2 ) 。第三节戆最短路树的计数问题，利用树形图的计数方 法，本节给交了最短鼹糖的诗鼗算法。第瑟节楚最短籍糖靛枣疑产童淹逶，将s p - n 算法与g a b o w 算法组台成一个新算法* - ( a l l - s p t ) 辣法，即产生所裔的最短路树。 第三章是最短路慰的相关闻题，包括三节。第一节是完念最短路树，包辐宠全 最短路树的定义、性质和算法。第二节是p e n d a n t s m e d i a n 支撵树问麟。在本节中， 利用x 3 c 问题的n p 宪全性，证明了p e n d a n t s 。m e d i a n 支撑树问题是n p 完全的。第 三节怒爨短爨稳戆楣蓑瘸题。本节营先醭究了g l o b a l m s l i m 支撵蟪逡麓，裂蠲3 s a t 问题的n p 完全性，证明了g l o b a l s u r f l 支撑树问题怒n p 宪全的，并在非负网络中 绘窭了一个对润复杂瞧为0 ( 妒) 豹算法。其次谤究了最小半缀最短路楗运题，裂爆 最短潞问题的n p 一究众性，诞明了最小半径最短路树问题也砖n p - 完全的。蠼后将 g l o b a l s u m 和半径组会在一起彤或一个双强标忧他问题，并刹月3 s a t 问题的n p 完 全性，证明了这个双鞠标优化问题也燕n p - 完全的。 第四章是r o b u s t 支撑树问题，包括两节。第一节是多参数最小树问题。在本节 中，剥震楚分鹚蘧静n p 宠全蛙，证明了多参数最小搪滂题是n p ，完全鹣；利囊g r e e d y 算法和f i s h e r 算法，给出了问题的上下界估计：给出了一个近似算法并分析了其性 i v 能比；最后同样利用划分问题的n p 完全性，证明了最大最小后悔支撑树问题也是 n p 完全越。第二节是最小树阉题的邋间题。农本节中，建立了最小树闽题的逆闯题 模型，将h a m m i n g 长度下的模型转化成二分黼中的最小顶点覆盖问题，从而用匈牙 刹方法给出了一个算法，时间复杂性为o ( m n2 ) 。最矮将h a m m i n g 长度和厶长度组 合在一起，形成了一个双目标优化问题，从而提出了一个新o p e n 问题。 第五章是支撑树的序列产生问题，包括嬲节。第节是基本概念。第二节是支 撑穗酾瓣长分布。在零节中，给密了支撵褥稿长分布定义，并稻蔫予集帮闻髓静复 杂性酲明了求支撑树树长分布l ( g ) 问题是n p - 完全的。第三节是严格第k 最小树问 题，对k = 2 的特殊憾况绘出了一个多项式算法。第四节是最小树的产生和一魑相关 问题。本节研究了最小树网络、支撵树的连通性以及由于边的删除最小树的长度交 动情况。 关键词：网络，支撑树，最短路树，算法，n p 究全性 v abstract 爵l i sp a p e rs t u d i e ss o m en e wm o d e l so fs p a n n i n gt r e e t h en e wm o d e l sm a yb e d i v i d e di n t ot w oc l a s s e s ，s u c ht h a to n ei s c o m p l e t en e wm o d e l s ，f o re x a m p l e ，m u l t i p l e p a r a m e t e r ss p a n n i n gt r e ep r o b l e ma n di n v e r s ep r o b l e mo fm i n i m l l n ls p a r m i n gt r e e ，t h e s e c o n di sn e wr e s e a r c ha b o u tc l a s s i e a lm o d e l s f o ri n s t a n c e 也e r e o p t i m i z a t i o n 、 e n u m e r a t i n ga n dg e n e r a t i o n o fs h o n e s tp a t ht r e e t h i sd i s s e r t a t i o nc o n s i s t so ff i v ec h a p t e r s c h a p t e rl i si n t r o d u c f i o n ，w h i c hi n c l u d e s3s e 娃i o n s 。孤es e c t i o nli n t r o d u c e ss o m e b a s i cc o n e ti nn e t w o r ka n dg i v e st h eu n i f o r m e dt e r m i n o l o g yu s e di nt h i sp a l ：i e r , s e c t i o n2 i n t r o d u c et h es h o r t e s tp a t hp r o b l e ma n di t s e l e m e n t a r ya l g o r i f l m a s ，s u c ha sd i j k s t r a a l g o r i t h m ，f r e d m a na l g o r i t h m s ，f o r da l g o r i t h ma n df l o y da l g o r i t h m ，s e c t i o n3i n t r o d u c e t h em i n i m u m s p a n n i n g t r e ep r o b l e ma n di t sp r i m a r ya l g o r i t h m s ，s u c ha sk u s k a la l g o r i t h m ， d i j k s t r aa l g o r i t h m 、y a oa l g o r i t h ma n dp r i ma l g o r i t h m 。硒e l a s t p a r to f 也i sc h a p t e r i n t r o d u c et h ed e g r e e c o n s t r a i n e ds p a n n i n gt r e ep r o b l e m ，g i v e st h ec o n c e p to fk d e g r e e c o n s t r a i n e d s p a n n i n gt r e e ，a n dp r o v e t h a te x i s tai n t e g e r k ，l k + n ，s u c ht h a ti f k 有一条边# g 暑( 正) 露( 正) ，故r = 瓦十e e 还是g 的支撑树。丁称作由t 2 n 正进行了一次迭代。 如果两个不问的支撩树有k 条边不同，那么经过一系列的交换，能番 由一个树到达另个树? 定遴2 设置秘不是g 戆嚣个支撵瓣，l 嚣( 霉) 、昱暖镕= k ，剽互经过k 次 遮代即可到达咒。 证秘觅【j ，2 j 。 定义3 设t 是g 的一个支撑树，e e ( t ) ，f 岂e ( g ) 、e ( t ) 。如果t e + f 遥是g 的一个支撑树，刚 e ，称作t 的一个可行交换。 在求严格第k 最小树的闯题中，经卷尾剿可行交换的檄念。 第二节最短貉霹题及主要算法 一个图往往是现实世界中菜些现象的发酸，边代表了两个个体之瀚 的连接关系，而这种连接关系的强度又需要一些参数来反映，这些参数包 捂：成本、时间、容量、可靠性、后悔值等。 每袋边赋壤爱，个图鄄戏失一个网终g = 是个网络，l 是长度参数。d i j k s t r a 在 4 中给出了 求解嚣受权网络中爨短路的算法，该算法嚣作d i j k s t r a 簿法。 d i j k s t r a 算法 s t e p0 踅坞= o ，“，= 1 j ( ，1 ) ，s = v 1 ，r = v s s t e p 1 在r 中计算：m i 9 “，= “k 。若= 惝，则停止，v 1 到v i 没有 v ：e 。 路；否则转s t e p2 s t e p2 爨s # s u v l 霆# 烈散；。对_ 显，“，仁烈矬每。，& + 1 4 1 ， ，转 s t e p1 。 程d i j k s t r a 算法的应用辛，霹能会离现z 。= o o 的情漉。这种情凝下算 法的执行方法的参见 1 ，2 ，5 】。 d i j k s t r a 算法适用于非负权网络，算法的时间复杂性为o ( n2 ) ，计算结 果为求出了一令顶点至l 其它疆点麴最短路。今最调爱此冀法时，诗算过程 中的“，称作标号。对于非负权网络， 6 】中给出了一个算法，时间复杂性 为o ( m + nl o g1 7 1 ) 。警翔络为稀蔬潮络时，该雾法优于d i j k s t r a 算法。我们 称该算法为f r e d m a n 算法，在此不再详述。当网络中有负权，但无负回 路时，我们调用f o r d 算法。f o r d 算法燕个逼近算法，算法的辩阊复杂性 为o ( n 3 ) 。f o r d 算法的详细内容见 1 ，2 ，7 】。对于无负网路的网络，f l o y d 于1 9 6 2 年也给出了一个算法，见【8 。 在谗多网终设计中，爨要嗣到所有点对之阀的最短路，始在本文所 要研究的完全最短路树中，即需要用到所有点对之间的最短路的长度。另 外选童盐霹蘧和定谴滴题也弱蜀繇裔点慰之阉懿最短路翁长度。f l o y d 簿法 浙没大学滞士学位论文 实际上蹙求爱蠢点对之阉最缀鼹戆令算法。 f l o y d 算法： s t e p0 置“拶= f 。，毋= 工m = l s t e p1对1 i h ，l ，s m ，计算： 球拶= m i n u 器- i ) ， 譬”+ “嚣” 如果“0 。蔓“墨1 + “嚣”，则亨= 彬。，否则了= l 譬“ s t e p2 若m = n ，缘衷，焱劐m # m l ，转s t e p l f l o y d 算法适用于无负回路的网络，算法的时间复杂饿为o ( n 3 ) 。 d i j k s t r a 簿法和f l o y d 算法都怒好算法，其辩阀复杂经都为输入裁模 的多项式，但这两个蒋法都只适用于特殊的网络，下面分析在般的网络 中，最短路问题的时间复杂悔问题。 与最短路问题相对应的还有个最长路阕邀，该闻题力求鼹个顶点 之间的长度最大的路。 引理1 最长路问题是n p 完全的。 鼓长路阉题静笺杂往冤【9 。计算复杂往、p 润蘧秘n p 完全闯题瞧 见 9 】。根据定义，g = 中的最短路问题等价于g = 中的 最长潞问题，因此由g l 理t 得到如下结论。 缝论1 各一般的网络中，最短路闯题是n p 完全魄。 墩短路问题的n p 一完全性在 10 】中也有说明。 第纛节最小支撑树闯题及主要算法 对于网络g 的支撑树t ，其长度l ( t ) 定义为t 的构成边的长度之和， 即上( r ) = ，。最小树( m i n i m u m s p a n n i n gt r e e ，今后简记为m s t ) 问题 e e e ( t 为求g 的一个支撑树r ，使l ( r ) 达到最小，即求解优化问题m i n l ( t ) ：t 浙江大学博士学位论文 是g 的支撑树1 。 为给出求最小树的算法，先分析最小树的性质。 定理3 设r 是g = 的支撑树，则r 是g 的最小树的充分必要 条件为v e e e ( t + ) ，记c ( r ，e ) 为t + + e 中的唯一回路，则有l e = m a x l ，。 f e c ( r ) 证明见 1 ，2 ，5 】。 由定理3 看到：对于一个支撑树r + ，如果任意一个可行交换 都 不能使交换后的支撑树变小，则t 即成为最小支撑树。因此对于最小树 来讲，局部最优即为整体最优。 以定理3 为基础，产生了许多求m s t 的算法。k r u s k a l 于1 9 5 6 年提 出了一个求m s t 的算法，见 1 1 。该算法也常称为g r e e d y 算法。 k r u s k a l 算法 s t e d0 对边按长度的大小由小到大排列。不妨设排列结果为 e 1 ，e 2 ，e 。置s = o ，i 2 0 ，j 。1 s t e p1 若1 s i = i = n 1 ，停止，g s l = t 即为所求。 s t e p2 若g s u t j 自不含回路，则s 乍s w e j ) ，i 仁i + 1 ，转 s t e p1 ：否则，j 乍j + 1 ，转s t e p 2 k r u s k a l 算法的计算量主要在s t e p0 ，排序所用的计算量为o ( m l o g n ) ， 因此k r u s k a l 算法的时间复杂性为o ( m l o gn ) 。该算法在后面的字典序最 小树中有应用。 d i j k s t r a 于1 9 5 9 年提出了求m s t 问题的另一个常用算法，见 1 2 。 该算法不用对边长事先进行排序，而是形成一个f r a g m e n t ，逐步向外延 伸，直到该f r a g m e n t 包含n - 1 条边为止。 濠江大学撼士学证论文 d i j k s t r a 繁法 s t e p0 置t = o ，f ； v 。) s t e p1诗算m i n 。：e = i ，。设f = 。 置t 仁t u ， ，f 仁f u v ，) s t e p2 如果i f = ，猁停止，t 即为所求，否剿转s t e p1 出予d i j k s t r a 算法不用攀先对边进行热痒，因此算法粒时潜复杂性为 o ( n2 ) 。 y a o 在【l3 】中绘窭了一个隶瓣m s t 豹簿法，菸薅闻笈杂淫为o ( m l o g l o gn ) 。从时间复杂性的角度讲，y a o 的算法优于k r u s k a l 算法。 k r u s k a l 算法、d i j k s t r a 舞法、y a o 冀法、p r i l n 算法( 觅【1 4 】) 等成 为我们对最小支撑树进行研究的算法基础，对这些舞法调用或对其进行改 造，将会产生求解其它支撑树问题的新算法。 最小支撑树问题是个经艇的组合优化问题，上述的4 个算法已很好 麴瓣决了这令蠲题。艇是在实际瘦鲻孛，辫这个溺瑟提赉了一些疆利或器 变形，如在一个信息网络的设计中，要求从顶点v ，发出的线路不超过d i 条， 1 f sh 。 定义4 度约束最小支撑树问题为求m i n l ( t ) ：t 怒o 酌支撑树， d r p ，) s 蠢，l s s 辨 。d e ( i i h ) 为一组攀先绘寇躲皇然数。 度约束最小支撑树问题是n p - 宪全的，见【9 。实际上该问题是强n p - 完全豹，霹秀当d l = 露。= l ，d i = 2 ，2 i 茎n l 靖，度缝隶最，l 、支撂薅窝嚣鼯 为h a m i l t o n 路问题。该问题的强n p 完全性决定了这是一个很雉的问题。 15 i 研究了度约束最小树的橼质，【1 6 】研究了度约柬最，j 、掰中边酌交换， i 7 】 对度约束最小支撑树阀题，利用p r u f e r 数，绘出了一个遗传算法。尽管 已有了这些研究结果，已如的算法还远远满足不了实际工作的要求。 考感到发终衷鼗小支撵撼目题豹强n p 完全性，诲多专家开始礤究 该问题的子问题，其中的一个子问题是降低支撑树中度受限制的顶点的个 浙江大学博士学位论文 数。 定义5k - 度约束最小支撑树问题为求m i n l ( t ) ：t 是g 的支撑树 d ，( v ，) d ，1 i k ) 。一( 1 i k ) 为一组事先给定的自然数。 n 度约束最小支撑树问题即为度约束最小支撑树问题，是强n p 完全 的；o 度约束最小支撑树问题即为经典的最小支撑树问题，是p 的，已 有上述4 个多项式算法；关于1 一度约束最小支撑树问题，h n g a b o w 在 18 中给出了一个时间复杂性为o ( ml o gl o gn + nl o gn ) 的算法，因此证明了该 问题也是p 的。当2 k n 一1 时，k 度约束最小支撑树问题是n p 完全的， 还是p 的? 定理4 存在一个k + ，使当k