（计算机软件与理论专业论文）贪心算法和网络设计中的若干问题.pdf

复旦大学硕士学位论文 摘要 在本文中，我们将考虑如下三个在网络设计中抽象出来的优化问题， 一是内点带权最小生成树问题二是多商品设备选址问题，三是多层次 设备选址问题。本文中考虑的这三个问题的若干版本均是n p 难的，因此 本文对这三个问题的近似性的上界和下界做了系统的研究。我们证明了 在度量空间中内点带权生成树问题是n p h a r d 的，并给出了两个在度量空 间下的近似算法，分别达到了3 ，5 2 和3 1 0 6 的近似度，同时证明了问题是难 以有小于1 4 6 3 的近似度的，除非p d t i m e n d ( j o g j 0 9 n ) 1 。在一般空间 下，我们也给出了两个近似算法，分别达到了2 3 5 h a n 和2 三k 的近似度，其 中风= e ：l ，同时证明了对任意e 0 ，问题是难以有小于( 1 一f ) 王k 的 近似度的，除非p d t i m e n o ( t o g 。t 8 1 。对多商品设备选址问题，我 们给出t o ( h a n ) i t i i 以度的算法。对多层次设备选址问题，我们的算法能达 到i n kn 的近似度，如果k 是设备的层次数。 本文中，在这三个问题的很多版本的近似算法中，我们都使用了我们近 似集合覆盖问题的贪心算法。这个贪心算法尽管概念上简单，但在有些问 题中具体使用起来却并不容易。本文选取的这三个问题的几个近似算法是 集合覆盖贪心算法相同的框架在近似不同问题时使用方法不同的非常好的 例子。 关键词：网络设计，贪心算法，内点带权的最小生成树，设备选址，多商品 设备选址，多层次设备选址，图论，n p - h a r d 问题，近似算法，不可近似性。 中图分类号：t p 3 0 1 6 复旦大学硕士学位论文 a b s t r a c t i nt h i st h e s i s ，w ec o n s i d e rt h r e en e t w o r kd e s i g np r o b l e m s ：1 m u i n s p a n n i n gt r e ew i t hi n n e rn o d ec o s tp r o b l e m ( m s t i ) ；2 m u l t i c o m m o d i t yf a c i l - i t yl o c a t i o np r o b l e m ( m f l p ) ；3 m u l t i l e v e lf a c i l i t yl o c a t i o np r o b l e m ( m l f l ) t h e s ep r o b l e m sb x en p - c o m p l e t e ，s ow ed e s i g np o l y n o m i a la p p r o x i m a t i o n a l g o r i t h m sa n ds h o wi n a p p r o x i m a b i l i t yf o rt h e s ep r o b l e m s m o r es p e c i f i c a l l y , f o rm s t i ，w ep r o v et h a ti ti sn p - h a r de v e ni nm e t - t i cs p a c e s f o rm e t r i cs p a c ec a s ew h e r et h ee d 雷ew e i g h t sa r es y m m e t r i c a n ds a t i s f yt h et r i a n g l ei n e q u a l i t y , w ep r o v et h a tt h ep r o b l e mi sn p - h a r d a n d 百v ea 3 5 2a p p r o x i m a t i o na l g o r i t h ma n da ni m p r o v e df a c t o r3 1 0 6 w e a l s os h o wt h a ta na p p r o x i m a t i o nf a c t b o ro f1 4 6 3i si m p o s s i b l eu n l e s s p 刃，m e 【护o o g j 0 9 ”) 】f o rt h ec a s ew i t hg e n e r a lw e i g h t s ，w ep r e s e n tt w op o l y - n o m i a lt i m ea l g o r i t h m sw h i c ha c h i e v ea p p r c o d m a t i o nf a c t o r so f2 3 5h na n d 2 ( k 一1 ) ，r e s p e c t i v e l y , w h e r eni st h e n u m b e ro fn o d e si nt h eg r a p ha n d 巩i st h en - t hh a r m o n i cn u m b e r t h i sn e a r l ym a t c h e st h el o w e rb o u n d ： r t op o l y n o m i a l - t i m ea p p r o x i m a t i o na l g o r i t h mc a na c h i e v ea na p p r o x i m a t i o n f a c t o ro f ( 1 一e ) 风，f o ra n ye 0 w ea l s og i v ea na p p r o x i m a t i o na l g o r i t h m w i t hf a c t o r 一1 w h e r e i st h em a x i m u md e g r e eo ft h eg r a p h w eg i v el o g a r i t h m i ca p p r o j d m a t i o na l g o r i t h m sf o rt h en o n - m e t r i cm u l t i - c o m m o d i t ya n dm u l t i l e v e lf a c i l i t yl o c a t i o np r o b l e m s t h ef o r m e ra l g o r i t h m s a r eo p t i m a lu pt oac o n s t a n tf a c t o r ，t h el a t t e ra l g o r i t h mi sf a ra w a yf r o m t h el o w e rb o u n d ，b u ti ti st h ef i r s ta l g o r i t h mt os o l v et h eg e n e r a lm u l t i l e v e l p r o b l e m t os o l v et h em u l t i c o m m o d i t yp r o b l e m ，w ea l s od e f i n ean e wp r o b - 一i l 复旦大学硕士学位论文 l e m ，t h ef x i e n d l yt o u ro p e r a t o rp r o b l e m ，w h i c hw ea p p r o x i m a t eb yag r e e d y a l g o r i t h m n o t et h a tf o rm a n yo ft h ea l g o r i t h m sm e n t i o n e d a b o v e w e1 】s et h eg r e e d y p a r a d i g mw h i c hg i v e sah n - a p p r o x i m a t i o nf o rs e tc o v e rp r o b l e m a l t h o u g h t h ec o n c e p to ft h i sg r e e d ya l g o r i t h mi ss i m p l e ，s o m e t i m e si ti st r i c k ya n d c o m p l i c a t e dt on l a k ei t w o r k t h i st h r e ep r o b l e m sa r ee x 锄p l 圈w h e na n d h o wt h i sg r e e d ya p p r o x i m a t i o nc a l lb ea p p l i e d k e yw o r d s ：n e t w o r kd e s i g n ，s p a n n i n gt r e ew i t hw e i g h t e di n n e rn o d e s ， m u l t i c o m m o d i t yf a c i l i t yl o c a t i o n ，m u l t i l e x n e lf a c i l i t yl o c a t i o n , g r a p ht h e o r y , n p - h a r dp r o b l e m ，a p p r o x i m a t i o na l g o r i t h m ，n o n a p p r o x i m a b i l i t y c h i n e s el i b r a r yc l a s s i f i c a t i o n ：t p 3 0 1 6 复旦大学硕士学位论文 b i p a r t i t eg r a p h ，1 1 c o m p l e t eg r a p h ，1 0 c o n n e c t e dd o m i n a t i n gs e t ，2 9 c o n n e c t e dd o m i n a t i n gs e t ，3 c o n n e e t i v e ，1 0 c u t ，1 1 c y c l e ，1 0 e u l a rt o t l t ，1 1 索引 f a c i l i t yl o c a t i o n ，4 f a c i l i t yl o c a t i o n ，1 6 f a c i l i t yl o c a t i o nw i t hs e r v i c ei n s t a l - l a t i o nc o s t ，f l s c ，5 ，4 0 f o r e s t ，1 1 m u l t i c o m m o d i t yf a c i l i t yl o c a t i o np r o b - l e i n ，m f lp 4 ，4 0 m u l t i l e v e lc o n c e n t r a t o rl o c a t i o np r o b - l e n a ，m c l p 8 ，4 9 m u l t i l e v e lf a c i l i t yl o c a t i o np r o b l e m ，m l f l ， 7 4 9 n o d ew e i g h t e ds t e i n e rt r e ep r o b l e m ， 1 9 n p 类，1 2 n p 难，1 3 n p 完全，n p c ，n p - c o m p l e t e ，1 3 p a t h ，1 0 p 类，1 2 p r i e n d l yt o u ro p e r a t o rp r o b l e m ，f r o ，s e tc o v e r ，1 4 4 5 g r a p h 1 0 h a m i l t o n i a up a t h ，1 1 i n d u c e ds u b g r a p h ，1 0 s h o r t e s tp a t hc l o s u r e ，1 1 s p a n n i n gt r e e ，1 0 s t a r ，1 1 s u b g r a p h ，1 0 t r e e ，1 0 m m d m u ml e a fs p m m m gt r e e ，3 不可近似性，1 4 m a x i m u ml e a fs p a n n i n gt r e e ，m l s t ，不可判定问题，1 2 2 1 m e t r i cs p a c e ，1 1 ，2 1 m i n i m u ms p a - n n m gt r e e ，1 0 m i n i m u ms p a n n i n gt r e ew i t hi n n e r n o d ec o s t ，m s t i ，2 ，2 0 带服务代价的设备选址问题，5 ，如 点带权s t e i n e r 树问题，1 9 度量空间，1 l 。2 1 复旦大学硕士学位论文 多层次集中器选址问题，8 ，4 9 多层次设备选址问题，7 ，4 9 多商品设备选址问题，4 ，如 多项式时间可解，1 2 二分图，1 l 割，1 1 哈密顿路，1 1 环1 0 回路，1 0 集合覆盖问题，1 4 近似度，1 4 连通。1 0 连通支配集，2 9 连通支配集问题，3 路1 0 内点1 0 内点带权的生成树，2 ，2 0 欧拉回路，1 1 森林，1 1 设备选址问题，4 设施选址问题，1 6 生成树，1 0 树，1 0 算法1 ，2 2 算法2 ，2 4 算法4 ，3 6 图，l o 完全图，1 0 星形，1 1 叶子最多生成树，2 1 友好旅游协会问题，4 5 诱导子图，1 0 子图，1 0 最短路闭包。1 1 最多叶子生成树问题，3 最小生成树，1 0 6 3 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：么猹 论文使用授权声明 日期：翌丑、9 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 名：堑一名旌隰 复旦大学硕士学位论文 第一章引言 在本文中，我们将考虑如下三个在网络设计中抽象出来的优化问题，一 是内点带权最小生成树问题，二是多商品设备选址问题，三是多层次设备 选址问题。这三个问题均是n p 难的，本文对这三个问题的近似性的上届和 下界做了系统的研究。本文内容主要来自于作者在硕士期间发表的如下文 章【3 3 】和【3 2 】 在正式介绍这三个问题之前，我们将介绍这三个问题内在的联系，和我 们为什么选取这三个问题的原因。本文中，在这三个问题的很多版本的近 似算法中，我们都使用了近似集合覆盖问题的贪心算法( 见2 4 节) 。自从集合 覆盖的贪心算法被提出后【5 】，众多问题的近似算法都在延续这个贪心算法 的框架，如【1 1 ，1 2 】等尽管这个贪心算法的思想非常的简单，但在很多具体 问题中，想要能够成功的使用这个框架也是需要很多的技巧的。本文选取 的这三个问题的几个近似算法是集合覆盖贪心算法相同的框架在近似不同 问题时使用方法不同的非常好的例子。需要注意的是，我们另外有一些其 他关于这三个问题在不同情况下的近似算法和不可近似度结果，使用的方 法并不是贪心算法的框架。下面我们详细的介绍本文将讨论的三个问题。 1 1内点带权的最小生成树问题 1 2问题定义 最小生成树问题是计算机科学中最早提出和系统研究的问题之一。 有很多有效率的多项式算法可以解决该问题，如p r i m 算法【2 9 】和k r u s k a l 算 复旦大学硕士学位论文 图1 1 ：内点带权最小生成树( m s r n ) 。图中黑色粗边代表最优解，黑色实 心点为最优解中的内点，最优解的权重为黑色实心点的权重和黑色粗边的 权和，5 7 。 法【2 2 】。每一个算法入门书籍中都有关于最小生成树问题的介绍，如 6 1 ( c h a p t e r 2 3 ) 目前对最小生成树有线性的随机算法 1 s l 和确定性的最优算法 2 s l ( 目 前尚不知道是否是线性) 。最小生成树问题有诸多重要变种，如最小比率生 成树，叶子最多生成树，叶子最少生成树，度数最小生成树，最d 、s t e i n e r 树 等。这些问题表面上都和最小生成树问题有着相似的结构，但实际上其中 的很多都是n p h a r d 问题。 本文考虑最小生成树问题的一个自然的变种，生成树中的非叶子结 点的权重也要记入生成树的总权重中，本文称该问题为内点带权的生成 树( m i n i m u ms p a n n i n gt r e ew i t hi u n e rn o d ec o s t ( m s t i ) ) 。我们将在 第3 1 节证明该变种也是n p h a r d 的。 问题形式化定义如下：给定一个边和点都带权的连通图g ( k e ) ，权 函数为t i ：e u v r + ，目标是找到一棵生成树t ，它的权重 ( t ) = 。f w ( e ) + 。拓w ( v ) 最小，其中厅为t 的内点的集合。例子见图1 1 。 1 2 1相关问题及以前的结果 在后面的第三章里我们还将看到内点带权生成树还是连通支配集问 复旦大学硕士学位论文 题( c o - - 眦dd o m i n a t i n gs e t ) 和最多叶子生成树问题( m a x i m u ml e a fs p a n - n i n gt r e e ) 的推广。这两个问题都是n p - h a r d 问题。对连通支配集。目前最好 的近似结果是o ( m n ) 的近似度，和( 1 一) i n n 的不可近似度f 1 1 ，1 2 】。对最多 叶子生成树，i f l 前最好的近似结果是3 的近似度【2 4 1 ，不可近似度为该问题没 有p t a s ( p o l y n o m a i lt i m ea p p r o x i m a t i o ns c h e m e ) ，即存在 0 ，该问题 没有( 1 + e ) 的近似度【9 l ( i e 即a p x - h a r d ) 1 2 2 我们的结果 我们证明了即使在度量空间中内点带权生成树问题也是n p - h a r d 的。 由第3 1 节中的n p - h a r d 的证明我们可以看出该问题是连通支配集问题和 最多叶子生成树问题的推广。在度量空间下，我们给出了两个近似算法， 分别达到了3 5 2 和3 1 0 6 的近似度，同时证明了问题是难以有小于1 4 6 3 的 近似度的，除非p d t i m e 【护( i o g l o s “】在一般空间下，我们也给t t l 了两个近似算法，分别达到了2 3 5 f 彻和2 巩的近似度，其中t t = ：l1 ；， 同时证明了对任意e 0 ，问题是难以有小于( 1 一e ) 风的近似度的，除 非pcd t i m e n d ( j 0 s l o g n ) 1 。 1 3多商品设备选址问题 1 3 1问题来源和定义 最初的设备选址问题起源于如下场景。假设有一公司准备在一些城市 建立分支生产产品，在每个城市建立分支需要的资本投入不同。公司已经 调查清楚了各个城市对该产品的需求，现在该公司想要满足所有这些需求， 并且要求花费的代价最小。当然，在每个城市都设立分支生产产品在很多 时候并不是一个经济的方法，因此我们只在其中一些城市设立分支，而没有 设立分支的城市我们通过运输的办法来满足对产品的需求，公司的花费包 含开设分支的花费和运输费用。因此，在该公司的最经济策略中，需要指定 我们将在哪些城市开设分支，并以哪些路线来运输产品到没有开分支的那 些城市。我们可以从该问题抽象出一个模型来，设所有的城市及其交通路 复旦大学硕士学位论文 径构成一个带权图，其中每个顶点代表一个城市，任意一条边的权重代表两 端点城市之间的运输费用，同时每个顶点的权重为在该城市设立分支所需 要费用。我们的目的是找到所有顶点的一个子集，在这些地点建立分支，使 得如下两部分费用之和最小：( 1 ) 建设这些分支的费用之和，( 2 ) 每个城市 到这些分支中间某一个的运输费用之和。我们先简单介绍一下最初的设备 选址问题的形式化定义：该问题一般有两种版本的定义，一个是二分图的 版本，另一个是一般图的版本。我们这里先只给出二分图的版本，我们将在 第2 5 节中再讨论这两个版本的等价性。 设备选址问题( f a c i l i t yl o c a t i o n ) 定义是：给定一个二分图g ( 以y ；e ) ， 我们称u 为设备集合，y 为客户集合。其中枷：v r + u 0 ) 为点权，表示 开放一个设备的代价。叫：e 一ru ( 0 为边权，表示连接一个设备和一个 客户的代价。问题的解要求开放一些设备0 u ，和一些边f e ，使得每 个客户都能通过一个开放的边连接到一个开放的设备上。很自然的，我们 要求开放代价的和最小化，即最小化如下目标函数 c o a ( o ，1 2 ) = ：w ( u ) + 芝：椰( e ) u e oe e e 我们在本文研究的多商品设备选址问题是如上的设备选址问题的推广。 在这个场景中，我们有多种商品要提供，每个城市有不同的商品需求。并且 在不同城市开设分支提供商品的代价不同，甚至在某些城市将不能建立提 供某些商品的分支。我们将使用如下两个模型来刻画上述问题，其中第二 个模型是第一个的推广。 1 模型一：我们称这个模型为为多商品设备选址问题f m u l t i c o m m o d i t y f a c i l i t yl o c a t i o np r o b l e m ，m f l p ) 。给定一个二分m e ( 以y ；e ) ，我 们称u 为设备集合，y 为客户集合。s 为商品集合。设s ：u 一2 5 为每 个设备可以提供的商品集合，s ：v 一2 5 表示每个客户需要的商品 集合( 2 5 表s 的所有子集的集合) 。设t t ，：u r + u o ) 为点权，表示 开放一个设备的代价，一个设备u 如果被开放了，那么它能够提 供s ( u ) 这些商品。加：e r + u ( 0 1 为边权，表示连接一个设备和一 个客户的代价。问题的解要求开放一些设备d u ，和一些边f e ， 使得每个客户的每种商品的需求都能得到满足，即如果一个客户需要 4 复旦大学硕士学位论文 图1 2 ：多商品设备选址f 习题( m f l p ) ，商品集合s = 1 ，2 ，3 ，4 ，5 ，6 ) ，黑色 实心点代表开放的设备，黑色粗边代表开放的边。最有解的权重为1 0 + 1 5 + 8 + 3 + 3 + 14 - 5 + 1 0 + 1 5 + 6 = 6 6 。注意客户c 3 连接了两个开放的设 备，l 和，4 商品s s ，那么该客户一定需要被一个开放的边连接到一个开放的设 备u 上g s s 似) a ( 注意一个客户很可能必须被连接到几个设备上) 很自然的，我们要求开放代价的和最小化，即最小化如下目标函数 c o 毹( o ，f ) = 伽( + 加( e ) u e o e e e 例子参见图1 2 。 2 模型二：我们称该版本为带服务代价的设备选址问题f f a c i l i t y l o c a t i o nw i t hs e r v i c ei n s t a l l a t i o nc o s t ，f l s c ) 给定一个二分m a ( 阢矿；e ) ，我们称u 为设备集合，y 为客户集合。s 为商品集合。s ：v 一2 5 表示每个客户需要的商品集合( 2 s 表s 的所 有子集的集合) 。其中 ：u r + u o ) 为点权，表示一个设备的初始 开放代价。而叫：u s r + u o ) 为附加商品提供费用，伽( u ，s ) 代 表如果在开放的设备u 上提供商品s 需要附加的费用。需要注意的是一 个设备s 如果要提供一个( 或多个) 商品，该设备首先要开放( 既首先 要花费( u ) ) 。加：e r + u 0 1 为边权，表示连接一个设备和一个客 户的代价。问题的解要求开放一些设备0 u ，并对于每个t | 0 ，我 一5 _ 复旦大学硕士学位论文 图1 3 ：带服务代价的设备选址问题( f l s c ) ，商品集e s = l ，2 ，3 ，4 ，5 ，6 ) ， 黑色实心点代表开放的设备，黑色粗边代表开放的边。右边为设备开放费 用 ( ，) 和附加商品提供费用叫( ，8 ) ，对每个，u 和s s 。方框里的代表已 经开放的设备和设备里的附加商品服务。最优解的权重为所有方框里的权 重和黑色粗边的权重和，1 1 7 们提供一些商品p ( t ) s ，并开放一些边f e ，同样的，我们要使 得每个客户的每种商品的需求都能得到满足。即最小化如下目标函数 c o s t ( o ，p f ) = ( 加扣) + 叫( 钍，s ) ) + 埘( e ) u e o j e p ( u 、 c e 例子参见图1 3 。 我们不难看出在f l s c f a 题中，如果附加商品瓤j w ( u ，s ) 只能取和o 的 话，f l s c 问题就是m f l p 问题。因此说f l s c 是m f l p 的推广 1 3 2相关问题及以前的结果 设备选址问题是组合优化领域的核心问题之一。在一般情况下或度量 空间或欧式空间中，该问题是都n p h a r d 的。到目前为止，对于该问题在不 同空间上的多种变种都存在大量的研究，关于设备选址问题的相关结果，请 参见第2 5 节。 多商品设备选址问题首先由文献 3 0 1 提出。他们首先给出了该问题在度 量空间上，当每个客户只要求一个商品时的o ( 1 0 9 l s i ) i a 似度的算法。他们 6 霎| 圉圈出箍端 霎一 复旦大学硕士学位论文 使用的技术是把整数规划放松成线性规划，再通过取整( r o l l d i n g ) 得到的。 在s h m o y se t 以【3 5 1 中给出了模型二，即f l s c 问题，在度量空间下的近似度 为6 的算法，但他们的算法需要一个假设，即所有设备可以按开放价格排序， 而且所有商品价格的排序也符合这个顺序。 1 3 3 我们的结果 在本文的第四章中，我们将给出m f l p 和f l s c 问题在一般空间上 的近似算法。我们的结果是对m f l p 问题，算法的近似度为竭v i 帅其 中l ，l 是客户的数量，i s l 是商品的数量。对f l s c 问题我们给出了3 竭卅的 算法。如果所有设备的初始开放代价叫( u ) 都是0 ，那么我们算法的近似 度可以达到2 竭v 悯。并且我们证明对任意e 0 ，m f l p 和f l s c 问题没 有近似度为( 1 一e ) m a x ( 胁i yj ，t n l s l 的多项式时间近似算法，除非p d t i m e n d ( i o g k 帕1 这说明我们的算法近似度在不考虑的常数因子的意义 下是最优的。 1 4 多层次设备选址问题 1 4 1问题定义 设备选址问题有许多变种，他们描述了在实际问题中更加复杂的要求。 比如客户如果有k 个要求，而设备集合被分成的k 个层次，每个层次提供一 种服务满足一种要求，那么问题可以抽象成如下问题。 多层次设备选址问题多层次设备选址问题f m u l t i l e v e lf a c i l i t yl o c a t i o n p r o b l e m ，m l f l ) 的形式化定义：给定一个图g e ) ，其中v = f e = 晶，月，易，最) ，e ( f o f 1 ) u ( f 1 f 2 ) u u ( f k 一1 最) 。其中c 是 客户的集合，f 1 ，最是设备的集合，被分成k 个层次。边集是定义在客 户c = f o 和第一层设备只间和其他相邻两层的设备间。同其它设各选址 问题一样，其中w ：u 叁1 e r + u o 为点权，表示一个设备的初始开 放代价。叫：e r + u 0 为边权，表示连接一个设备和一个客户或连 接两个设备的代价。这里，一个客户，0 c 被满足，当且仅当存在一个开 复旦大学硕士学位论文 放的路径p = t 】0 ，口l ，地，仉 ( 即路径上的点和边都开放) ，其中仇只。 记a = u 垒1 是每一层次上一些开放的设备，其中k 只。我们要求使得每 个客户都被满足。该问题的目标是： 吗n ”( ”) + d i s o i 4 u f o ( o ，k ) 口，o 厅 ( d i s c l a u f o f r o ，k ) 表示在一4u 昂诱导的图上，o 到k 的最短路距离。具体定义 参见预备知识，第2 1 节1 注意在这个版本中，一条开放的边的权可以被花 费几次( 比如用边权来代表运输费用) ，如果有多条路经过这条边的话。 很多实际情况中，我们要求一条开放的边权只能被花费一次( 比如用边 权来代表修建线路的费用) ，我们得到问题的如下版本，我们称为多层次集 中器选址问题( m u l t i l e v e lc o n c e n t r a t o rl o c a t i o np r o b l e m ，m c l p ) 。记该 问题可行解一4 = u 叁1 m ，其中k 只该问题的目标是： 呼三呻) + 互概吣( 刚- ) ) + 善磊。梨 + 。毗m ) 例子见图1 4 1 4 2相关问题及以前的结果 多层次设备选址问题是一个在组合优化领域有很长历史的问题，是设 备选址问题重要变种之一在 3 6 1 中，s h m o y se ta 1 把他们用来解决设备选 址问题的过滤和取整( f i l t e r i n ga n dr o u n d i n g ) 方法用到度量空间下多层次设 备选址问题，得到近似度为3 1 6 的算法。不久后，a a r d a le t 以给出了度量 空间下近似度为3 的近似算法【1 】对于层数k 比较小的情况，有更好的近似 算法，比如在【2 l 中对k = 2 时有1 7 7 近似，在k = 3 时有2 5 1 近似，在k = 4 时 有2 8 1 近似。对一般空间的情况，当层数为2 时，z h a n g 在4 1 1 给出了m l f l 问 题和m c l p 问题的d ( f n i g l ) 近似度的算法，i c i 为客户数量。 1 4 3 我们的结果 在本文的第五章，我们给出了对于一般空间上的m l f l 问题和m c l p 问 题的近似度为o ( 1 n i c i ) 的算法，其中是设备的层数。具作者目前所知， 一8 - 复旦大学硕士学位论文 图1 4 ：多层次设备选址问题( m l f l ) 和多层次集中器选址问题( m c l p ) ， 黑色实心点代表开放的设备，黑色粗边代表开放的边。在m l f l 中，图上 解的权重为w ( a 1 ) + ( ，碗) - 4 - ( 1 ) + 叫( ，1 2 ) - 4 - ( ，1 3 ) - i - 2 加( e ( 五1 ， 1 ) ) - i - 叫( e ( ，2 l ， 2 ) ) + 2 ( e ( 如，1 3 ) ) + 叫( e ( ，1 1 ，c 1 ) ) + t l ，( e ( 1 ，c 2 ) ) + 叫( e ( 2 ，c 3 ) ) + w ( e ( f x 3 ，c 4 ) ) + 叫( e ( 。，岛) ) 。注意，e ( ，2 - ， - ) 和e ( 尼， 3 ) 都被两条路经过，所 以要算两次权重。而在m c l p 中，图上解的权重为叫( ，2 1 ) + t l ，( ，2 2 ) + 叫( ，1 1 ) + t 7 ( 2 ) + 伽( 3 ) + ”( e ( ，2 - ，1 - ) ) + 叫( e ( ，2 1 ，1 2 ) ) + 伽( e ( ，2 2 ，1 3 ) ) + 伽( e ( l ，c 1 ) ) + 伽( e ( l ，晚) ) + 叫( e ( 2 ，c 3 ) ) - i - w ( e ( a 3 ，q ) ) - i - 叫( e ( 3 ，岛) ) 这个结果是第一个在一般空间上，对于一般的k 给出的m l f l 的近似结果。 当然这个结果和这个问题的不可近似下界仍有一定距离，该问题是否 有o ( t n l c l ) i 丘似度的算法仍是未知的。 复旦大学硕士学位论文 第二章预备知识 在本章中我们介绍本文中用的图论的术语和记号，并介绍一些基本的 问题。如集合覆盖问题，设备选址问题等，这些问题将在本文后面用到。 2 1图论预备知识 本文中我们会使用如下术语和记号。一个 ( g r a p h ) 是一个二元组g = ( k e ) ，其中我们称集合y 为点集( 其中的元素称为点) ，称日vxv 为 边集( 其中的元素称为边) 。图中每个点u 相邻的边的个数称为口的度，记 为d e g g ( v ) 。整个图的度定义为a = m a x v y d e g g ( v ) 。 如果一个图的任意两个不同结点问都有边相连，我们称这个图为完 全图( c o m p l e t eg r a p h ) 。一个边序列( l ，也) ，( 忱，地) ( 啦一l ，讥) 是g 的一条 路( p a t h ) ，如果i j 的话有优那么我们称这条路为一条简单路如 果对所有1 isk 一1 ，我们有陬，地+ 1 ) e 。一条首尾相连的简单路被称 为环或回路( c y c l e ) 。一个图是连通( c o n n e c t i v e ) 的，如果该图的任意两点间 都存在一条路。一个图的边的子集构成的新图成为原图的子图( s u b g r a p h ) 。 设s y 为图g 点集的子集，那么我们定义子图g ( s ( sxs ) ne ) 为由s 诱 导的诱导子 ( i n d u c e ds u b g r a p h ) ，记为g f 剐。 一个连通且无环的图称为树( t r e e ) 。给定一个连通图g ( ve ) 和它的子 图t ( v f ) ，如果t 是一棵树，我们称r 是g 的一个生成树( s p a 扣n i n gt r e e ) 。 设t 为图g ( ke ) 的一棵生成树，定义厅为树r 的内点( i n n e rn o d e s ) ( 非叶子 结点或度数大于1 的结点) 的集合。图g 中边权之和最小的生成树被称之为 最小生成树( i n i 血u ms p a n n i n gt r e e ) 陋 题。给定一个图f ，如果f 是无环的， 1 m 复旦大学硕士学位论文 我们称f 是一个森林( f o r e s t ) 。我们能够看出森林是由树组成的。我们定义 星形( s t a r ) 为最多只有一个内点的树。 我们说一个图的边权函数w ：e r 是定义在度量空间( m e t r i c s p a c e ) l - 的，如果边权函数满足三角不等式，即：对任意边( ，口) ，( t t ，) 和( t ， ) ，有w ( u ，口) + 硼扣，伽) 叫( ，加) 。 对一个边带权的图g ( ke ) ，一条路的长度( 或距离) 定义为路上所有 边权之和。两点砒口间的晟短路被定义为这两点间具有最短长度的路，记 为d i s a ( u ，口) 。对p q v ，同时定义d i s a ( u ，q ) = m 吣o d i s v ( v ，g ) ，d i s a ( p ，q ) = m i n 蚝p d i s g ( p ，q ) 。对一个边带权图g e ) ，权函数为，我们定义一个一 个边带权完全图g ( v e ) ( 权函数为面) 为g 的最短路闭包( s h o r t e s tp a t h c l o s u r e ) 。如果对面( t ， ) = d i s a ( t ，口) 。我们不难发现g 的权函数是满 足度量空间的性质的。对不相交的两个点集4 ，且，我们记a ，b 的割( c u t ) 为s ( a ；b ) = e ( d ，b ) e a a ，b b 。 我们称一条回路为图g 的欧拉回路( e l d a rt o u r ) ，如果这条路访问g 的 每条边恰好一次一个图存在欧拉回路当且仅当这个图是连通的且每个点 度数为偶数( 见【3 1 1 第1 8 页) 。我们称一条路为图g 的哈密顿路( h a m i l t o n i a n p a t h ) ，如果这条路访问g 的每个点恰好一次。哈密顿路问题是著名 的n p c 问题。 我们称一个图g ( ve ) 为二分图( b i p a r t i t eg r a p h ) ，如果y 可以被分为不 相交的两部分k 和k ，且e k 。k 和被称为g 的两部分我们记 该图为g ( m ，y 2 ；e ) 。 2 2n p 完全问题与近似算法 为了便于理论上衡量一个算法的效率，现在一般用算法所需要的基本 操作数目和输入规模的函数来度量算法的时间复杂度。为了计算的方便，一 般用渐进时间复杂度，渐进复杂度使用符号如0 ，d ，u ，q ，e 等，读者可以参 考f 6 1 ，第4 1 5 1 页 对指定问题设计高效算法通常需要更深的挖掘问题的组合结构。在对 很多问题的组合结构的研究过程中，很多研究者发现，有许多问题自身有 复旦大学硕士学位论文 着特定的复杂的组合结构，这种内在复杂结构的结果是，要解决该问题，必 须付出一定数量的时间或空间。一个大家熟知的例子就是在r a m 比较模型 下，排序问题至少需要o ( n l o g n ) 的时间复杂度【2 1 】，这里n 是需要排序的元 素个数。因此，计算复杂性理论作为一个研究问题内在组合结构的复杂程 度，和解决该问题所需要的时间空间的下界的系统理论就应运而生了。计 算复杂性理论发源于二十世纪六十年代，其标志是n p 完全理论的建立，而 建立该理论的c o o l 痢将该理论广泛推广到众多问题的k a r p 也因此得到了计 算机科学最高奖，图灵奖。有关计算复杂性理论，读者可以参考【3 7 ，2 7 】。 实际上，早在计算复杂性理论之前，有计算机科学之父之称的图灵早 在1 9 3 6 年就证明了有些问题非常之难，以至没有任何有限的算法( 图灵机) 来解决该问题1 3 8 1 ，这类的问题称为不可判定问题。读者可以参考 3 7 1 。而复 杂性理论的研究内容就是揭示计算某些问题的难度，证明没有任何算法能 在指定的资源( 时间，空间或通讯次数等) 内计算该问题。在今后的叙述中， 我们要用到图灵机的概念，读者可以参阅计算理论的书籍，如 3 7 】。 通常，某个算法可以解决某问题，而这个算法的时间复杂度是o ( n ) ， 这里n 是问题的输入规模，k 是常数，那么这个问题就是多项式时间可解的。 目前除了图灵机外，还有很多确定性计算模型，它们都被证明是和图灵机有 相同计算能力的，而且另一个重要的特点是，这些模型都和图灵机是多项式 等价的。因此，多项式时间可解的问题在各种其他已经发现的计算模型下 也都是多项式时间可解的。另外，多项式可解在某种程度上意味着高效率。 我们常见的时间复杂度，如指数的时间复杂度，在输入规模增加的情况下， 其增长速度要远远高于多项式时间的增长。所以，理论上，我们将多项式时 间作为问题是否难解的分水岭。 我们所说的复杂性类一般指判定问题，就是只要求回答”y e s ”和”n o 的 问题。不严格的来讲，p 类就是那些有多项式时问确定性图灵机可以判定的 的问题集合。n p 类就是那些有多项式时间非确定性图灵机解决该问题的问 题集合我们已经知道p 尸，但是不是有p = n p ，至今尚不清楚。这 个问题是目前理论计算机领域最核心的未解决问题。当前理论计算机科学 中，大家普遍认为的一个观点是p p ，即存在不可多项式求解的n p 问 题当代复杂性理论中有很多证据都支持( 而非证明) 了以上观点。 1 2 复旦大学硕士学位论文 n p 类中有这样一些问题，这类问题有一个重要的特点是：如果其中任 何一个有确定性多项式时问算法，那么n p 中的所有问题都可以在多项式 时间内解决，即p = n p 。因此，如果我们相信p p ，那么n p c 问题就 不可能有多项式时间算法。这类问题就是著名的n p 完全问题( n p c ，n p - c o m p l e t e ) 。c o o k 【7 】、k a r p 1 9 和l e v i n 2 3 等分别提出t n p 完全性理论。 假设和，是两个判定性问题，如果存在多项式确定性算法a ，使得对 问题的任意一个实例，算法a 都可以将，转化到问题，的一个实例，并 且，的输出结果为y e s 当且仅当门均输出结果为y e s ，我们称多项式