（运筹学与控制论专业论文）最小化κ限制连通分支数的近似算法.pdf

摘要 摘要 图划分问题是一类有着广泛用途的问题，它在大规模集成电路设计，计算机信 息存储方案中均有应用。本文所讨论图划分问题为最小化k 限制连通分支数问题： 对于任意连通图g = ( ke ) ，给定y 上的权重函数u ，对任意整数k ，将v 划分 为尽可能少的互不相交的顶点集 ，k ，) ，使得所有k 在原图中的诱导子图 为连通图，并且权重u ( ) k 。该问题即使对于顶点均为单位权重的简单图仍为 p 一完全问题。已知存在多项式时问精确算法，能够解决该问题限制在树上的情 形。对于一般连通图上的极小化k 限制连通分支数问题还缺乏相应的近似算法。 本文先分析了若干启发式算法对该问题的求解质量问题，指出常见的启发式算法 仅考虑顶点间的权重关系，而忽略了对图中割点性质的挖掘。本文进而提出了兼顾 割点性质与权重的新启发式算法，并给出其对于二种特殊图近似比分别为4 与3 的 证明。 关键词：图划分k 限制连通分支割点启发式算法近似算法 摘要 ab s t r a c t g r a p hp a r t i t i o nh a saw i d ea p p l i c a t i o ni ni n d u s t r ya n dn e t w o r kd e s i g n ，e s p e c i a l l yi n v l s ia n dm e m o r ya l l o c a t i o nf o rc o m p u t e rn e t w o r k t h i sp a p e rd i s c u s s e st h ep r o b l e mo f m i n i m i z i n gt h en u m b e ro fk - r e s t r i c t e dc o m p o n e n t s ：g i v e nag r a p hg = ( i s , e ) ，aw e i g h t f u n c t i o n o nva n da ni n t e g e rk ，p a r t i t i o nvi n t od i s j o i n ts u b s e t s ，巧 w ea i m t om i n i m i z et h en u m b e rjo f s u b s e t ss ot h a te a c hki n d u c e sac o n n e c t e ds u b g r a p hi nga n d t h et o t a lw e i g h to fv e r t i c e si n i sn om o r et h a nk t h i sp r o b l e mi snp - h a r de v e nf o ru n i t w e i g h tg r a p h s s o m ep o l y n o m i a le x a c ta l g o r i t h m sh a v eb e e nf o u n dw h e nt h ep r o b l e mi s r e s t r i c t e dt oat r e e h o w e v e r , t h e r ei sl i t t l et ok n o wa b o u ta p p r o x i m a t i o na l g o r i t h m sf o rt h e g e n e r a lp r o b l e m i nt h i sp a p e rw ea n a l y z et h ep e r f o r m a n c eo fs e v e r a lh e u r i s t i ca l g o r i t h m s a n dp o i n to u tt h a tt h e s ea l g o r i t h m sn e g l e c tt h es p e c i a lp r o p e r t yo fs o m ec u tv e r t i c e s w e d e s i g nan e w h e u r i s t i ca l g o r i t h mw h i c ht a k e sb o t hf a c t o r si n t oc o n s i d e r a t i o na n dp r o v et h a t t h ea p p r o x i m a t i o nr a t i oo ft h en e wa l g o r i t h mf o rt w ok i n d so fs p e c i a lg r a p h si s4a n d3 r e s p e c t i v e l y k e y w o r d s ：g r a p hp a r t i t i o n ，k - r e s t r i c t e dc o m p o n e n t ，c u tv e r t e x ，h e u r i s t i ca l g o r i t h m ， a p p r o x i m a t i o na l g o r i t h m l l 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得浙江大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：吕思厄 签字日期：2 ) 口7 年石月了日 学位论文版权使用授权书 本学位论文作者完全了解浙江大学有权保留并向国家有关部门或机构送交 本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江大学可以将学 位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：善足乏 签字日期：2 0 口t 年, e l 了e 1 ， 导师签名： 签字日期： 第一章概论 1 第一章概论 1 1 组合优化问题概述 组合优化问题处理如何找出多元目标函数最大( 最小) 值，其常见的限制条件 为( 1 ) 变量之间有不等式或等式约束：( 2 ) 全部或部分变量必须为整数。由于大量问 题可由离散优化模型表示，组合优化问题有很广泛的研究价值。 组合优化在管理与稀缺资源分配问题中起着至关重要的作用。它在实际生产中 的应用包括资源配置，生产计划。近年来，组合优化方法在预算安排，设备选址， 交通与通讯网络设计，超大规模集成电路设计以及生产自动化等实际问题中也有大 量应用。随着计算机技术的发展，组合优化极大地推动了组合数学，图论和数理 逻辑的发展。目前组合优化受到管理科学，理论计算机科学，应用数学与运筹学的 共同重视，成为热门交叉学科。 在组合优化问题的研究过程中产生了计算复杂性的概念。下面将简要介绍本文 会用到的一些关于复杂性理论的基本知识，参考文献【1 】，【2 】有对复杂性理论的详 细介绍。 定义1 ：算法( a l g o r i t h m ) 就是这样定义的计算过程：对于f 1 题7 r ，它取一组数 值作为输入，经过有限的计算步骤，将输入数据转化为输出，得到7 r 的一个解。 本文所涉及的算法都为确定性算法，印算法每一步的运算是由前面的运算确定的。 定义2 ：若存在常数c ，使得定义在正整数上的函数，与9 ，始终有i ，( n ) i ci 夕( 凡) i ，称函数，( n ) 是d ( 夕( n ) ) 。若函数p 为多项式，组合优化问题的实例长度 为n ，则时间复杂度能被p 与常数c 限制( 即时间复杂度为o ( 几) ) ) 的算法称为 多项武时间算法。 计算复杂性的研究源自对组合优化问题困难程度的分类。当时的研究人员发 现，某些组合优化问题即使问题所给出的实例规模很大，也能找出算法在合理时 间内解决。而另外一些问题除了枚举法外，对找到问题最优解还没有有效的算法。 由此根据解决问题所需要的时间( 算法运行步骤) 与问题输入规模之间的关系，出 第一章概论 现了j p 问题与p 问题的概念。尸类问题是指所有在多项式时间内，能够被确定 型图灵机解决的判定问题。也就是说尸类问题都存在算法能在关于输入的多项武 时间内锝到解决。而j 7 、r p 问题是指所有在多项式时间内，能够被非确定型图灵机 解决其判定问题的问题。尸是否等于n p 仍然是理论计算机科学与数学的重大未 解问题。给定尸问题，则存在算法对它任意一个实例，在有限步之后，一定可以 得到该实例的一个解答，我们说该算法解决问题7 r 。能够解决一个优化问题的算法 并不唯一。对于在尸中的组合优化问题，存在有效算法可以求得其最优解。但对 于j p 问题通常不要求一定得到问题的最优解，因此能否在多项式时间内获得较 好的近似解成为研究的热点。这些对于n p 问题能求得近似解的算法称为近似算 法。文献【3 】，【4 】对近似算法有深入介绍。我们有以下定义： 定义3 ：称算法a 为优化问题7 r 的近似算法，如果对它任意实例，a 总能通过 计算得到问题7 r 的可行解。如果存在常数a 1 ，使得对于任意实例算法得到的可 行解盯相比最优解o o p t 有丢f ( i r o v t ) k 。最优解也只能 将仇，所对应的部分顶点划分入同一连通分支，本文算法将耽， ，各划入一 连通分支。若m 为图g = ( v ，e 7 ) 的完美匹配，则u = 仍。该匹配将顶点集 做了两两配对，配对的顶点权重之和大于k ，且不同配对没有公共顶点。由此 a l c ( v ) 2 v k ，又由k 为任意连通分支的权重上界，必有o p t ( v ) i vj k ， 所以a l g ( v ) 2 0 p t ( v ) 。 若未匹配点集u d ，令其中权重不小于k 2 的点集为x ，小于k 2 的点 集为y 。将x 中的顶点 z l ，x 2 ，) 配对为 ( z 1 ，z 2 ) ，( x 3 ，x 4 ) ) ，则配对两顶 点权重不小于k ，与上面分析同理可得a l g ( x ) 2 0 p t ( x ) ，所以o p t ( v ) i m i + l x l 2 。当权重小于k 2 的未匹配顶点数目不太多，即i y l 2 m i + i x i 时有 a l g ( v ) = i y l + i x l + 2 i m ls2 mj 十i x i + l x i + 2 l m i = 2 i x i + 4 i m i 4 0 p t ( v ) 。 特别地，当l m i n 4 时，即有l y l 2 m i 2 i m i + l x i 。 若最终得到的图g ，= ( v 7 ，e 7 ) 为树。设 f 。，1 2 ，f r 为其叶子点集合。 引理4 ：最优解o p t ( v ) 至少为叶子点数7 。 证明：若该树每个非叶子点至多只与一个叶子点相邻，则由算法终止的条件 可知任取叶子点以，其与邻点的权重满足( ( 如) + u ( ) 七。又口；，否则 将同时与叶子点如，如相邻。可得r 对互不相交的顶点，每对顶点权重之和大 于k ，所以o p t ( v ) r 。若该树有非叶子点同时与多个叶子点相邻，则可假设 第二章最小化k 限制连通分支数问题 在初始中图与割点相邻的叶子点连通分支数至少为2 。否则若初始图中有割点让1 只与一个叶子点代表的连通分支c 1 相邻，则在合并过程中其相邻的割点仳，必与 另一- 9 叶子点相邻的割点u 2 合并。由算法优先考虑非割点- 9 割点的合并可知有 u ( c 1 ) 十w ( u 1 ) 七。最有解也无法将c 1 与让l 划分入同一连通分支。若初始图中已 有割点与至少两个最终形成叶子点的连通分支相邻，在算法终止所得图中叶子点 f ，1 2 ，l p 同时与割点牡相郐。参- 92 t 合并的顶点只能- 9 他中点相邻，否则如 将为非叶子点。在割点让的形成中，若u - 9 只- 9 其相邻的某个叶子连通分支f 7 合 并，则最优解中z 也不能- 9 f 1 ，1 2 ，l p ) 共存- 9 同一连通分支。若与z 1 共存则意 味这会有某个f 1 单独划分入一连通分支，所以总连通分支数不会由于z 7 与其它叶 子点的合并而减少。 引理5 ：对任意树丁，可在多项式时间内找到它的一个匹配m ，使得所有非 叶子点均被匹配。 证明：任取丁中非叶子点仰，把它做为根( r o o t ) 。标记钉的子代( c h i l d r e n ) 为，v l ，仃2 ，忱。若忱均为树丁的叶子点，则取( 0 1 ，u ) 作为匹配对，所有非叶子 点均被匹配。否则不妨令 u 1 为非叶子点，取( 0 1 ，口) 作为匹配对，再将顶点 u 1 ，口在 丁中删除。口l ， 的子代( c h i l d r e n ) ，作为所得森林中子树的根。对子树继续从根 开始如上处理，当所有子树均为孤立点时算法终止。若有树丁中非叶子点口未被 匹配，设t ，成为孤立点前属于子树r ，若口为r 的根，则钉必能与其某个子代 组成匹配。若可不为r 的根，则 或者与r 的根组成匹配对，或者作为删除t 7 的根组成匹配对后所得子树的根。口在所有可能情况下均不可能成为未匹配的孤立 点，所以匹配m 总能在线性时间找到。由g ，中任意相邻两点的权重之和都大于 k ，可知o p t ( v ) i m i 。 定理2 ：本文提出的启发式算法对算法终止时形成树的图近似比为3 。 证明：设算法停止时所得树丁的非叶子点数为z 。由引理5 ，匹配m 可将所 有非叶子点匹配，得z 2 1 m i 。由引理4 ，a l g ( v ) = z + r 2 1 m i + o p t ( v ) 2 0 p t ( v ) + o p t ( v ) = 3 0 p t ( v ) 。 1 2 第二章最小化k 限制连通分支数问题 2 3 结论 本文提出了针对最小化k 限制连通分支数问题的算法。该算法在顶点划分过程 中对割点与非割点按照指定优先级处理，尽量使得非割点集不与割点集混合划分 入同一连通分支。算法在一定程度上克服了常见启发式算法对割点与非割点不加区 分的缺陷，进而对两类特殊图取得常数近似比分别为4 ，3 。 1 3 参考文献 参考文献 1 】m r g a r ya n dd s j o h n s o n ，c o m p u t e r sa n di n t r a c t a b i l i t y ：ag u i d et ot h et h e o r y o fn p c o m p l e t e n e s s ：2 0 8 ，w h f r e e m a na n dc o m p a n y , s a nf r a n c i s c o ，19 7 9 2 】d z d ua n dk k o ，t h e o r yo fc o m p u t a t i o n a lc o m p l e x i t y , j o h nw i l e y s o n s ，n e w y o r k ，2 0 0 1 3 】v vv a z i r a n i ，a p p r o x i m a t i o na l g o r i t h m s ，s p r i n g v e r l a g ，b e r l i n ，2 0 0 1 4 】d s h o c h b a u m ，e d i t o r , a p p r o x i m a t i o na l g o r i t h m sf o rn p h a r dp r o b l e m s ：4 6 8 6 ， p w sp u b l i s h i n gc o m p a n y , 19 9 7 【5 】b w k e m i g h a na n ds l i n ，a ne f f i c i e n th e u r i s t i cp r o c e d u r ef o rp a r t i t i o n i n gg r a p h s ， t h eb e l ls y s t e mt e c h n i c a lj o u r n a l ，4 9 ：2 9 1 3 0 7 ，19 7 0 6 】s d u t t ，n e wf a s t e rk e m i g h a n l i nt y p eg r a p hp a r t i t i o n i n ga l g o r i t h m s ，i np r o c i e e e c o n f e r e n c eo nc o m p u t e r - a i d e dd e s i g n ：3 7 0 3 7 7 ，19 9 3 【7 】c f i d u c c i aa n dr m a t t h e y s e s ，al i n e a rt i m eh e u r i s t i cf o ri m p r o v i n gn e t w o r kp a r t i t i o n s ，i n19 t hi e e ed e s i g na u t o m a t i o nc o n f e r e n c e ：17 5 181 ，19 8 2 8 】b h e n d r i c k s o na n dr l e l a n d ，am u l t i l e v e la l g o r i t h mf o rp a r t i t i o n i n gg r a p h s ，i n p r o c s u p e r c o m p u t i n g ，19 9 5 【9 】m j b e r g e ra n ds h b o k h a r i ，ap a r t i t i o n i n gs t r a t e g yf o rn o n u n i f o r mp r o b l e m s a c r o s sm u l t i p r o c e s s o r s ，i e e et r a n s a c t i o n so nc o m p u t e r sc 一3 6 ：5 7 0 - 5 8 0 ，19 8 7 1o 】g l m i l l e r , s h t e n g ，w t h u r s t o n ，a n ds a v a v a s i s ，a u t o m a t i cm e s hp a r t i t i o n - i n g ，g e o r g e ，j rg i l b e r ta n dj w h l i u ，e d i t o r s ，g r a p ht h e o r ya n ds p a r s em a t r i x c o m p u t a t i o n ，v o l u m e5 6o ft h ei m av o l u m e si nm a t h e m a t i c sa n di t sa p p l i c a t i o n s ： 5 7 8 4 ，s p r i n g e rv e r l a g ，19 9 3 【11 】j r g i l b e r t ，g l m i l l e r , a n ds h t e n g ，g e o m e t r i cm e s hp a r t i t i o n i n g ：i m p l e m e n t a t i o na n de x p e r i m e n t s ，i np r o e i n t e r n a t i o n a lp a r a l l e lp r o c e s s i n gs y m p o s i u m ：418 - 4 2 7 ， 1 9 9 5 12 】h d s i m o n ，p a r t i t i o n i n go fu n s t r u c t u r e dp r o b l e m sf o rp a r a l l e lp r o c e s s i n g ，c o m p u t i n gs y s t e m si ne n g i n e e r i n g ，2 ( 2 3 ) ：13 5 14 8 ，19 91 1 4 参考文献 【13 】a p o t h e n ，h d s i m o n ，a n dk p l i u ，p a r t i t i o n i n gs p a r s em a t r i c e sw i t he i g e n v e c t o r s o f g r a p h s ，s i a mj o u r n a lo i lm a t r i xa n a l y s i sa n d a p p l i c a t i o n s ，11 ( 3 ) ：4 3 0 - 4 5 2 ，1 9 9 0 【1 4 】b h e n d r i c k s o na n dr l e l a n d ，a ni m p r o v e ds p e c t r a lg r a p hp a r t i t i o n i n ga l g o r i t h mf o r m a p p i n gp a r a l l e lc o m p u t a t i o n s ，s i a mj o u r n a lo ns c i n t i f i cc o m p u t i n g ，16 ( 2 ) ：4 5 2 4 6 9 ，1 9 9 5 15 】r l e l a n da n db h e n d r i c k s o n ，a ne m p i r i c a ls t u d yo fs t a t i cl o a db a l a n c i n ga l g o r i t h m s ，i np r o c s c a l a b l eh i g h p e r f o r m a n c ec o m p u t i n gc o n f e r e n c e ：6 8 2 6 8 5 ，19 9 4 16 】j r g i b e r ta n de z m i j e w s k i ，ap a r a l l e lg r a p hp a r t i t i o n i n ga l g o r i t h mf o ram e s s a g e p a s s i n gm u l t i p r o c e s s o r , i n t e r n a t i o n a lj o u r n a lo fp a r a l l e lp r o g r a m m i n g ，1 6 ( 1 ) ：4 2 7 4 4 9 ，1 9 8 7 17 】j e s a v a g ea n dm g w l o k a ，p a r a l l e l i s mi ng r a p hp a r t i t i o n ，j o u r n a lo fp a r a l l e la n d d i s t r i b u t e dc o m p u t i n g ，13 ：2 5 7 2 7 2 ，19 9 1 18 】s t b a r n a r da n dt t d s i m o n ，af a s tm u l t i l e v e li m p l e m e n t a t i o no f r e c u r s i v es p e c t r a l b i s e c t i o nf o rp a r t i t i o n i n gu n s t r u c t u r e dp r o b l e m s ，i np r o c 6 t hs i a mc o n f e r e n c eo n p a r a l l e lp r o c e s s i n gf o rs c i e n t i f i cc o m p u t i n g ：711 - 718 ，1 9 9 3 【19 】a g u p t a ，f a s ta n de f f e c t i v ea l g o r i t h m sf o rg r a p hp a r t i t i o n i n ga n ds p a r s e m a t r i xo r - d e r i n g ，i b mj o u r n a lo f r e s e a r c ha n dd e v e l o p m e n t ，4 1 ( 1 ) ：1 7 1 1 8 3 ，1 9 9 7 2 0 】e o f j a l l s t r o m ，a l g o r i t h m sf o rg r a p hp a r t i t i o n i n g ：as u r v e y , l i n k o p i n ge l e c t r o n i c a r t i c l e si nc o m p u t e ra n di n f o r m a t i o ns c i e n c e ，v 0 1 3 ：h t t p ：i p 1 i u s e e a c i s 19 9 8 010 ， 1 9 9 8 【21 】e o h a d l o c k ，m i n i m u ms p a n n i n gf o r e s t so fb o u n d e dt r e e s ，p r o c 5 t hs o u t h e a s t e r n c o n f e r e n c eo nc o m b i n a t o r i c sa n dg r a p ht h e o r y , a n dc o m p u t i n g ：4 4 9 - 4 6 0 ，u t i l i t a s m a t h e m a t i c ap u b l i s h i n g ，w i n n i p e g ，19 7 4 【2 2 】b h e n d r i c k s o na n dr l e l a n d ，t h ec h a c ou s e r sg u i d e ，v e r s i o n2 0 ，t e c h n i c a lr e p o r t s a n d9 5 - 2 3 4 4 ，s a n d i an a t i o n a ll a b o r a t o r i e s ，19 9 5 【2 3 】g k a r y p i sa n dvk u m a r , af a s ta n dh i g hq u a l i t ym u l t i l e v e ls c h e m ef o rp a r t i t i o n i n g i r r e g u l a rg r a p h s ，t e c h n i c a lr e p o r t9 5 0 3 5 ，u n i v e r s i t yo fm i n n e s o t a ，d e p a r t m e n to f c o m p u t e rs c i e n c e ，19 9 5 2 4 】c w a l s h a w , m c r o s s ，a n dm g e v e r e t t ，m e s hp a r t i t i o n i n ga n dl o a d - b a l a n c i n gf o r d i s t r i b u t e dm e m o r yp a r a l l e ls y s t e m s ，i np r o c p a r a l l e ld i s t r i b u t e dc o m p u t i n gf o r 1 5 参考文献 c o m p u t a t i o n a lm e c h a n i c s ，19 9 7 【2 5 】h d s i m o na n dc f a r h a t ，t o p d o m d e c ：as o f t w a r ef o rm e s hp a r t i t i o n i n ga n d p a r a l l e lp r o c e s s i n g ，t e c h n i c a lr e p o r tr n r 9 3 0 11 ，n a s a ，19 9 3 2 6 】l l o v a s z ，ah o m o l o g yt h e o r yf o rs p a n n i n gt r e e so fag r a p h ，a c t am a t h a c