（应用数学专业论文）q01规划模型下最大团、最大加权独立集问题的研究.pdf

太原理i 人学硕l 研究生学何论文 q o 一1 规划模型下最大团、最大加权独立集 问题的研究 摘要 图中的最大团问题与最大独立集问题均属于图论中经典的n p - 完全 问题，该类问题所具有的固有困难，已使其普遍有效算法的寻求变得希 望渺茫。但由于该类问题深刻而广泛的理论及应用背景，寻求其尽可能 有效的精确算法和近似算法，近年来仍是计算数学工作者们十分关注的 课题。 本文首先介绍了最大团及最大加权独立集问题的数学含义及其关 系。对该类问题在国内外研究现状的介绍，重点放在各种精确算法和启 发式算法的思想以及基本算法流程方面。 本文进一步重点阐述了q 0 1 规划模型 m i n 。厂( x ) = c 7 x + 去x 7 o x ，x o ，1 y 上 ( 其中q = ( g ， ，。是一个n ”阶的有理矩阵，c 是一个”维有理向量) 的背 景及其一般形式，并具体介绍了求解该类模型使用的分支定界算法。上 述模型和算法是本文模型和算法的基础。 在第三、第四、第五章中，作者基于上述q o 1 规划模型提出了形式 更为简洁的q 0 1 规划模型，此种模型与原有模型相比，与图的基本不变 量具有更直接对应关系，这一改进对建模过程的简化特别有效。在此模 型基础上，本文首先针对非加权最大团问题给出其分支定界法的理论基 础及算法步骤直至算法实例，其次，又针对最大加权独立集问题进一步 太原理l 。人学硕 。 j 究生学位论文 进行了理论推导，简化了模型和算法步骤。不仅针对最大加权独立集问 题，也返回来简化并改进了非加权最大团问题的算法效果，文中对此均 有算例和计算结果加以分析说明。 本文在对求解q o 1 规划模型的分支定界法研究中，采取了贪婪排序 方式、非贪婪排序方式以及作者在导师指导下提出的基于“平均新权” 的排序方式，而且对不同排序方式在不同密度情形下的运算效果进行了 比较分析，得出一些初步结果。这些结果显示，对于不同密度的图，上 述不同排序方法不仅对运算效果有重大影响，而且各自适用于不同密度 范围的图，从而它们具有一定程度的“互补性”。这一互补性对进一步的 研究工作也有启发作用。 本文最后对进一步研究工作的思路提出了一定设想。 关键词：最大团，最大加权独立集，q 0 1 规划，分支定界法 太原理i 人学硕十研究生学位论文 s t u d yo nm a x i m u mc l i q u e a n dm a x i m u mw e i g h t e di n d e p e n d e n ts e t p r o b l e mb a s e do n q o 一1p r o g r a m m i n g a b s t r a c t t h ep ro b l e m so fm a x i m u mc l i q u ea n dm a x i m u mi n d e p e n d e n ts e ti n a r b i t r a r yg r a p ha r ew e l l k n o w n c l a s s i c a l n p c o m p l e t e o w i n g t ot h e i r p r o f o u n da c a d e m i ca n da p p l i e db a c k g r o u n d ，r e c e n t l y ，e x p l o r i n ga ne x a c t a l g o r i t h mo rh e u r i s t i c sa sf i n ea sp o s s i b l eo ft h e s ep r o b l e m si sh o t s p o tf o r s om a n ym a t h e m a t i c i a n s i nt h i sp a p e r , w ef i r s t l yp r e s e n tm a t h e m a t i c a lm e a n i n g sa n dr e l a t i o n s h i p b e t w e e nm a x i m u mc l i q u ea n dm a x i m u mi n d e p e n d e n ts e t t h ee x p a t i a t i o no f i n v e s t i g a t i o na c t u a l i t ya b o u tt h e s ep r o b l e m se m p h a s i z e di nt h ei d e a sa n d g e n e r a lf l o w so fv a r i o u se x a c ta l g o r i t h m sa n dh e u r i s t i c s s e c o n d l y , w ep r e s e n tt h eg e n e r a lf o r ma n db a c k g r o u n do fq 0 - 1p r o g r a m m i n g m i n f ( x )c r x + 昙7 掣，x o ，1 ” ( c i sar a t i o n a lv e c t o ro f o r d e r n ，q = ( g ，) i sar a t i o n a l m a t r i xo f o r d e r n ) ， b r a n c ha n db o u n da l g o r i t h mf o rt h i sm o d e li sd i s c u s s e di nd e t a i li n t h i s c h a p t e r m o d e la n da l g o r i t h mi no u rp a p e rr o o ti nt h em o d e l a n da l g o r i t h mw e d i s c u s sa b o v e b a s e do na b o v em o d e l ，a u t h o rb r i n gf o r w a r dam o r ec o m p a c tq 0 1p r o g r a m m i n g i th a s m o r ec l o s ec o r r e s p o n d i n gc o n n e c t i o nw i t ht h eb a s a l i n v a r i b a l so fg i v e ng r a p h f o l l o w i n gi nt h i sm o d e l ，w ef i r s t l yp r e s e n tt h e i i i 尘些堑生叁兰至堡丛塞生堂笪堡塞 t h 。o r yf o u n d a t i o n ，a r i t h m e t i ca p p r o a c ha n dc o m p u t e e x a m p l eo fb r a n c ha n d b o u n da l g o r i t h m sf o rn o n w e i g h tm a x i m u m c l i q u ep r o b l e m ，n e x t ，w ee d u c e t h es i m i l a r q 0 1 p r o g r a m m i n go fm a x i m u mw e i g h t e di n d e p e n d e n ts e t p r o b l e m ，a n de v e np r e d i g e s tt h em o d e la n da r i t h m e t i ca p p r o a c hn o to n l vo f m a x l m u mw e i g h t e d i n d e p e n d e n ts e t p r o b l e mb u ta l s oo fn o n w e i g h t m a x l m u mc l i q u ep r o b l e m ，r e l a t e de x a m p l e sa r eb e i n gp r e s e n t e dt os h o w o u r i d e a s u s i n gt h r e es o r tt e c h n i q u e s - - g r e e d ys o r t s e a r c h ，n o n g r e e d vs o n s e a r c ha n dt h es o r ts e a r c hb a s e do na v e r a g en e w w e i g h tw h i c hr o o ti nm v t u t o 。8g u i d a n c e - w et e s to u ra r i t h m e t i co nr a n d o m g r a p h sa n dy e tc o m p a r e t h eo p e r a t i o ne f f e c t so ft h r e es o r tt e c h n i q u e s e x p e r i m e n tr e s u l t ss h o wm a t g r 。朗ys e a r c hs u i tt os o l v i n gl a r g es c a l ed e n s eg r a p h p r o b l e m s ，a n dt h a t n o n g r e e d ys e a r c hh a v i n gb e t t e re f f e c to ns m a l ls c a l e s p a r s eg r a p h s ，t h e s e a r c nb a s e qo na v e r a g en e w w e i g h ts o r t ，w h i c hw ed i s c u s s e de m p h a s i z ei n t n l sp 印e rs o l v l n gm o d e r a t es c a l ea n dm e d i u md e n s i t y g r a p h se f f e c t i v e l y t h u s ，t h e ya r ea l lb e n e f i c i a lc o m p l e m e n t a r i t i e so fe a c ho t h e ra n da r ea i i d e v e l o p m e n t a l l yo ff o r e i n v e s t i g a t i o n s l a s t l l y , w eb r i n gf o r w a r ds o m ea s s u m ea b o u to u rf a r t h e re m p l o y m e n t s 1 ( e yw o r d s ：m a x i m u mc l i q u e ，m a x i m u mi n d e p e n d e n ts e t ，q 0 。1 p r o g r a n a m i n g ，b r a n c ha n db o u n da l g o r i t h m i v 太原卵1 人学硕 研究生学何论文 主要符号说明 本文只考虑有限阶无向简单图g = ( 矿，e ) ，设矿= k ，k ，v ) 为其顶 点集，e = e i 岛，e 3 ， 为其边集，i v l = ”，i e l = m 。 图g 的邻接矩阵为4 ，= ( ) 。其中 ( v ，v ，) e 时，= 1 ； ( v ，v ，) e 时，= 0 。 图g 补图亏的邻接矩阵为以= ( 瓦) ，其中 ( v ，v ，) e ，瓦= 0 。 ( _ ，v ，) e 时，瓦= 1 。 ，表示”阶单位矩阵。 以正整数集w = w 1w ：，w t ， 表示图g 顶点的权集合，对每一个项点 v ，t v ，定义( i ) = h y l ( v ，v ，) 1 ( f ：l ，2 ，3 ，”) 表示顶点v ，在g 中的邻 集，( | v ( 劝表示项点v ，邻集的权，即邻集中各项点的权和。 图g 的加权邻接矩阵记为a ，。= ( ) ，其中 ( ，v ，) e 且，时，= ( w + w ) 2 ； ( v ，) 譬e 或f _ 时，= o 。 图g 补图g 的加权邻接矩阵记为= ( ) ，其中 ( v ，v ，) r r i 时，= ( w + w ，) 2 ； ( ，v ，) e 或f _ j 时，w 。= 0 。 ，。= ( 嘭 。，称为加权单位矩阵，其中 v 太原理i 人学顺 研究生。学化论文 f ，时，w = 0 ： i = 时，w ，= ( w + w , ) 2 = w ，。 z ( f - 1 ，- ， ) 表示顶点v 的度。 w 表示顶点v 的原始权。 z ( o = w i 一w j 表示顶点的新权。 = l 乞表示图中所有顶点新权的平均值，称为平均新权。 v 7 表示候选顶点集。 x = f o ，1 ”表示其分量取值为0 或1 的n 维向量。 x 7 表示向量_ 的转置。 p = o ，1 ”表示其分量取值在 o ，1 内的r t 维向量。 “表示以x 中各分量一阶偏导数下界为分量的向量。 b 表示以x 中各分量一阶偏导数上界为分量的向量。 l c l 表示团的规模，即图的阶数。 本文中图的密度如”s i t y = 罢 l 月 其余未加说明的术语及记号见文献【4 7 。 v i 声明 y9 7 9 3 9 5 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：毖日期： 论文作者签名：篁型趿丛 日期：塑：互：! 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 导师签名： 日期：主翌：鱼：圭! 日期：竺! ：生型 太原理一人学硕十研究生学位论文 第一章绪论 1 1 最大团、最大加权独立集问题及其意义 给定一个无向图g = ( 矿，e ) ，其中v = k ，k ，k ， 是图g n n , 点y 6 ，e v x v 是图g 的边集。图g = ( v ，e ) 的补图为舀= ( 矿，丘) ， 其中 e = ( v ，) l v ，v j 矿，i j 且( _ ，) 茌g 图g 的团是指，存在y 的一个子集，其导出子图是g 的完全子图，即c 是图g 的 一个团，如果对于v v ，v ，v ( c ) ，边( v ，v ，) e 。如果团c 不是图中其它任何团的真 子图，则称该团为图g 的极大团。图g 的最大团是指基数最大的团，最大团的基数 称为该图的团数，记为国( g ) 。最大团问题( t h em a x i m u mc l i q u ep r o b l e m 缩写为m c ) 就是在给定的图中寻找该图的最大团。 给定正整数集 ，w 2 ， 与顶点集y v 。，v ：，v n ) 对应，w ( f - 1 ，2 ，3 ， ) 称 为顶点v ( f _ 1 ，2 ，3 ，月) 的权，图的顶点集v v 的权w ( v ) 指矿中所有顶点权之和。 所谓最大加权团i h 题( t h e m a x i m u m w e i g h t e d c l i q u e p r o b l e m 缩写为m w c ) 就是寻 找图中权和为最大的团，其权和称为图的加权团数，记为c o ( o ，w ) 。显然，最大团问 题是最大加权团问题的特例。 图g 的独立集是指，存在v 的一个子集，其中的元素两两互不邻接，即s 是一个 独立集，如果对于v v , ，v ，矿( s ) ，j j 2 ( v , ，v ，) 诺e 。如果一个独立集不是图中其它任何 独立集的真子集，则称该独立集为图g 的极大独立集。图g 的最大独立集指基数最 大的独立集，其基数称为图g 的独立数，记为a ( g ) 。最大独立集问题( t h em a x i m u m i n d e p e n d e n ts e tp r o b l e m 缩写为m i s ) 就是在给定的图中寻找其最大独立集。 所谓最大加权独立集问题( t h em a x i m u mw e i g h t e di n d e p e n d e n ts e tp r o b l e m 缩写 为m w i s ) 就是寻找图中权和为最大的独立集，其权和称为图的加权独立数，记为 太原理1 人学硕十研究生学位论文 a ( g ，w ) 。 图g 的点覆盖r 是指顶点集y 的一个子集，它关联图g 的所有边，即若 ( v ，v ，) e ，则一定有v t 或v ，t 。如果一个点覆盖是图中其它任何点覆盖的真子 集，则称该点覆盖为图g 的极小点覆盖。图g 的最小点覆盖是指具有最小基数的点 覆盖，其基数称为图g 的覆盖数，记为p ( g ) 。最小点覆盖问题( t h em i n i m u mv e r t e x c o v e r p r o b l e m 缩写为m v c ) 就是在给定的图g 中寻找其基数最小的点覆盖。 最小加权点覆盖问题( t h e m i n i m u m w e i g h t e d v e r t e x c o v e r p r o b l e m 缩写为m w - v c ) 是寻找图中权和为最小的顶点覆盖，其权和称为图的加权覆盖数，记为p ( g ，w ) 。 显然，c 是图g 的团当且仅当c 是补图6 的独立集，或者v v ( c ) 是图舀的点覆 盖，图的团数、独立数、覆盖数有以下关系： c o ( g ) = a ( g ) ，a ( g ) + 1 3 ( g ) = ”，c o ( g ) + p ( g ) = ” 因此这三个问题之一中获得的任何结果都可以立即转化为其它两个问题的等价 形式。 在理论上，以上三个问题属于组合数学领域中著名的n p 一完全问题，可在多项式 时问复杂度内转化为许多著名的难题，如三元精确覆盖问题( x 3 c ) ，旅行商问题( t s p ) 以及许多非数学领域的应用问题。例如，编码理论问题可转化为h a m i l t o n 图的最大 加权团问题1 2 - 4 1 ；故障诊断问题可以转化为c f a t 环图的最大团问题 5 - 6 1 ；圆的置放问 题可转化为圆的交图的最大加权团问题 7 1 ；自动生产系统中，每个部件有多种生产方 案的计划模型可以转化为具有最小成本的多部图的最大团问题”1 等等。 另外，最大团问题在几何学、经济学、计算机视觉、生物学、聚类分析、信息检 索、移动通信、图象显示、模式识别、电台信息传送和v l s i 电路设计等领域都有重 要应用 9 - 1 3 1 。 1 2 国内外研究现状 1 9 7 9 年，m i c h a e lr g a r e y 和d a v i ds j o h n s o n 证明了在一般图上求解最大独立 集问题是n p 一难题 t 4 1 ，即几乎不可能存在多项式时间复杂度算法求解这个问题。更有 2 太原理l 人学硕十研究生学位论文 甚者，二卜世纪九- t - 年代初期有人证明，甚至对于找到图的近似最大独立集。1 ”， 也难以寻求多项式时间复杂度算法。尽管存在上述根本意义上的消极结果，但基于最 大团、最大独立集问题的广泛应用背景和和对其深刻理论认识的需求，这类问题仍然 刺激国内外学者不断对其进行广泛深入的研究。 近年来，研究的重点是大量搜索算法的研究和试验9 1 ，其中包括精确算法( e x a c t a l g o r i t h m ) 和启发式算法( h e u r i s t i c s ) ，均针对加权和非加权两种情形。 精确算法中最早的是枚举法( e n u m e r a t i v ea l g o r i t h m ) 1 ，最常用的是在枚举法基 础上改进得到的分支定界法。枚举法的思想比较简单，这早不再赘述，分支定界法在 后面章节中我们将作详细讨论。 启发式算法是相对于精确算法提出的，其含义为1 ：启发式算法是一种技术， 这种技术使得在可接受的计算费用内寻找最好的解，但不一定保证所得解的可行性和 最优性，甚至在多数情况下，无法阐述所得解与最优解的近似程度。启发式算法与近 似算法的区别是：近似算法保证所得解与最优解的误差在给定的界限内，而启发式算 法不考虑所得解与最优解的偏离程度。 一般启发式算法以顺序贪婪算法( s e q u e n t i a lg r e e d yh e u r i s t i c s ) 及局部搜索算法 ( 1 0 c a ls e a r c hh e u r i s t i c s ) 最为经典。 现代优化算法是上个世纪八十年代以来兴起的启发式算法。其中包括禁忌搜索算 法、模拟退火算法、遗传算法、人工神经网络算法，d n a 算法等等。这些算法不论产 生的背景如何，都可以用来寻求n p 一完全问题的全局最优解，但由于n p 一完全问题本 质上的难解性，上述算法既不能保证其有效性，又不能保证求得最优解。然而实际问 题的需要，又给了这些算法巨大的发展空间，使其成为当代求解n p 一完全问题的主力 军，并且不断的发展完善。 下面将各种启发式算法的思想和基本步骤阐述如下： 顺序贪婪算法顺序贪婪算法是在贪婪算法的基础上发展起来的，它通过下列两 种方式得到图的一个极大团：一种方式是从候选顶点集中重复删去顶点，使之形成团， 哪个顶点被取消进入团的资格由候选顶点集的特征函数决定。另外一种途径是，在目 前已找到极大团的邻域内( 某些极大团的集合) 进行搜索以改进此解，这种方法称为局 部搜索算法，最常见的是k 一替换法( k - i n t e r c h a n g eh e u r i s t i c s ) 。 局部搜索算法局部搜索是一种很常用的基本搜索技术，绝大多数启发式算法都 融入了局部搜索技术。例如模拟退火算法、禁忌搜索算法等。局部搜索算法解的 效果直接依赖于初始可行解五的选取和邻域n ( x “) 的定义，其中z “指当前找到的 最优解。为改善解的质量，应该扩大搜索邻域以期望包含更好的解，但这是以增加搜 索时1 8 j 为代价的。对最大独立集问题，这种不断扩张搜索邻域的策略在图的规模扩大 到一定地步就不可行了。一种变通的方法是引入随机因子，这方面一个较为精细的算 法可见文献 2 4 。另外，文献 2 5 也提出了一个带有随机因子的