（计算机系统结构专业论文）设施选址问题的研究与应用.pdf

摘要 摘要 设施选址问题是一类被广泛研究和应用的优化问题，在互联网、分布式计 算、数据挖掘和运筹规划等领域有广泛应用，所以对设施选址问题各种形式的 研究有着重要的实际意义。设施选址问题的一般形式是从一个对象集合中选择 若干对象作为设施来服务其它对象，优化的目标是服务费用最小，比如从一个 局域网中选择若干主机作为代理服务器使得其它主机通过代理服务器访问外部 网络的时间尽量短。围绕设施选择问题的一些形式，本文开展了以下研究工作： 提出并研究了无向树全覆盖问题及其应用。该问题是已有的无向树上l 覆 盖问题的一个限定形式，也是已有的无向树1 中心问题的一个推广形式。设计 了一个时间复杂度为o ( n l o g n ) 的简洁算法来解决该问题。这一算法可以用来解 决树形网络的代理服务器和网页缓存服务器的选择问题。 改进了直线上p 覆盖问题的已有算法。该问题是设施选址问题中较早被研 究的形式之一。改进算法利用高效的数据结构和优化技术将已有动态规划算法 的时间复杂度改进为o ( n p l o g n ) ，空间复杂度改进为o ( n l o g n ) ，而原算法的 时间复杂度和空间复杂度均为o ( n 。) 。 提出并研究了无向树上k 节点子树核心问题及其应用。该问题是已有的无 向树p 中心问题的一个限定形式，可以应用于树形网络上的分布式数据库数据 副本最优安置问题。设计了两个不同的动态规划算法来解决这一问题，一个具 有编程实现简单实用性强的特点，另一个具有时间复杂度低时间效率高的特点， 两个算法可分别适用于不同的应用环境。 研究了无向树l 中心问题的动态形式。该问题需要在树节点权值动态改变 的情况下多次求解无向树的l 中心。提出- f n 用简单的动态树数据结构在对数 时间内维护动态无向树的l 中心的算法，从而解决了已有算法不能处理树节点 权值变小的情况这一问题。 研究了无向树上的p 中心问题。在已有无向树上无容量限制的设施选址问 题算法的基础上提出了一个时间复杂度较低的实用算法。这一算法并不能求解 所有的输入实例，即一些特殊的输入实例会导致该算法失败，但是验证实验表 明该算法能够求解绝大部分输入实例。 关键词：设施选址问题；树形网络；p 中心问题；p 覆盖问题；k 子树核心问题； 动态规划；s p l a y 树；动态树i 均摊分析 a b s 仃a c t a b s t r a c t f a c i l i t yl o c a t i o np r o b l e m sa r eac o l l e c t i o no fo p t i m i z a t i o np r o b l e m sa n dt h e ya r e w i d e l y s t u d i e da n da p p l i e di nv a r i a b l ea r e a ss u c ha sn e t w o r k s ，d i s t r i b u t e d c o m p u t a t i o n ，o p e r a t i o nr e s e a r c ha n d d a t am i n i n g i ti so fg r e a tp r a c t i c a ls i g n i f i c a n c e t os t u d yk i n d so ff a c i l i t yl o c a t i o np r o b l e m s t h ec o m m o nf o r mo ff a c i l i t yl o c a t i o n p r o b l e m si st os e l e c tas u b s e to fo b j e c t sf r o mag i v e ns e tt os e r v ea l lo t h e ro b j e c t s t h eg o a lo fo p t i m i z a t i o ni st om i n i m i z et h es e r v i c ec o s t f o re x a m p l e ，s o m ep r o x i e s a r es e l e c t e df r o mal a nt om i n i m i z et h ed e l a yt i m ei n c c u r e db yo t h e rn e t w o r kh o s t s w h e na c c e s s i n gt h ee x t e r n a ln e t w o r k t h ef o l l o w i n gr e s e a r c hw o r ko ns o m ef o r mo f f a c i l i t yl o c a t i o np r o b l e m si sp r e s e n t e d t h ec o m p l e t ec o v e r a g ep r o b l e mi nu n d i r e c t e dt r e e sa n di t sa p p l i c a t i o nw a s s t u d i e d ，w h i c hi sar e s t r i c t e df o r mo ft h e1 - c o v e r a g ep r o b l e mi nu n d i r e c t e dt r e e sa n d a l s oag e n e r a l i z e df o r mo ft h e1 - m e d i a np r o b l e mi nu n d i r e c t e dt r e e s a ne l e g a n t o ( nl o gn ) t i m ea l g o r i t h mw a sp r o p o s e dt os o l v et h i sp r o b l e m t h ea l g o r i t h mc a n b ea p p l i e dt os e l e c tt h eb e s tp r o x yo rw e bc a c h es e r v e ri nat r e eb a s e dn e t w o r k a ni m p r o v e da l g o r i t h mf o rp - c o v e r a g ep r o b l e mo nal i n ew a sp r o p o s e d ，w h i c h w a sb a s e do nt h ee x i s t i n gd y n a m i cp r o g r a m m i n ga l g o r i t h ma n dm a k eu s eo fe f f i c i e n t d a t as t r u c t u r ea n dq u e r yo p t i m i z a t i o nt e c h n i q u e s t h ei m p r o v e dt i m ec o m p l e x i t ya n d s p a c ec o m p l e x i t ya r eo ( n pl o gn ) a n do ( nl o gn ) ，r e s p e c t i v e l y , w h i l et h et i m e c o m p l e x i t ya n ds p a c ec o m p l e x i t yo fo r i g i n a la l g o r i t h ma r eb o t ho ( n 2 ) t h ek n o d e sc o r eo fa nu n d i r e c t e dt r e ea n di t sa p p l i c a t i o n sw e r ep r o p o s e da n d s t u d i e d t h i sp r o b l e mi sar e s t r i c t e df o r mo ft h ek - t r e ec o r eo fa nu n d i r e c t e dt r e ea n d i sm o t i v a t e df r o mt h ea p p l i c a t i o ni nt h ed e s i g no fd i s t r i b u t e dd a t ab a s ei nt r e eb a s e d n e t w o r k t w od y n a m i cp r o g r a m m i n ga l g o r i t h m sw e r ep r o p o s e dt o s o l v et h i s p r o b l e m ，o n eo fw h i c hw a se a s yt oi m p l e m e n ta n dt h eo t h e rw a so fg r e a tt i m e e f f i c i e n c yb u tm o r ec o m p l e x t w oa l g o r i t h m s c a nb ea p p l i e du n d e rd i f f e r e n t c i r c u m s t a n c e s t h ed y n a m i cf o r mo ft h e1 - m e d i a np r o b l e mi na nu n d i r e c t e dt r e ew a ss t u d i e d t h i sd y n a m i cf o r mr e q u i r e st h a tt h e1 - m e d i a no fa nu n d i r e c t e dt r e eb em a i n t a i n e d s u b j e c tt oc h a n g i n gt h ew e i g h t so f t h et r e en o d e s as i m p l ea l g o r i t h mm a k i n gu s eo f d y n a m i ct r e ed a t as t r u c t u r e sa n dm a i n t a i n i n g1 - m e d i a no fa nu n d i r e c t e dt r e es u b j e c t t oc h a n g e so fn o d ew e i g h t si nl o g a r i t h m i ct i m ew a sp r o p o s e d ，a n ds o l v et h ep r o b l e m t h a tt h ee x i s t i n ga l g o r i t h mc a n th a n d l et h ec a s ew h e r ean o d ew e i g h ti n c r e a s e s a b s t r a c t t h e p m e d i a no fa nu n d i r e c t e dt r e ep r o b l e mw a ss t u d i e d a na l g o r i t h mo fm u c h l o w e rt i m ec o m p l e x i t yt h a nt h ee x i s t i n ga l g o r i t h m sw a sp r o p o s e d a l t h o u g ht h e p r o p o s e da l g o r i t h mw a su n a b l et os o l v ea l li n p u ti n s t a n c e sa n ds o m es p e c i a li n p u t i n s t a n c e sm a k ei tf a i l ，e x p e r i m e n t ss h o wt h a ti tw a sa b l et os o l v em o s to fi n p u t i n s t a n c e s k e yw o r d s ：f a c i l i t yl o c a t i o np r o b l e m s ，t r e eb a s e dn e t w o r k ，p m e d i a np r o b l e m ， 一p c o v e r a g ep r o b l e m ，k t r e ec o r ep r o b l e m ，d y n a m i cp r o g r a m m i n g ， s p l a yt r e e s ，d y n a m i ct r e e s ，a m o r t i z e da n a l y s i s 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除己特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 i i i 作者签名：苤主塾垂 沙文年s 只司日 第一章绪论 第一章绪论 设施选址问题( f a c i l i t yl o c a t i o np r o b l e m s ) 是一类最优化问题的集合，它的一 般形式是在一些已知位置对象( 客户，仓库等) 的基础上来安置另一些对象( 设 施，工厂等) ，使得安置代价和两类对象间的交互代价尽量小，交互的代价通 常用对象间的相对位置来衡量。由于其在物流运输、规划设计、运筹管理等传 统领域内的重要应用，设施选址问题从2 0 世纪初开始就得到了广泛而深入的研 究【l 】o 近年来，由于互联网、分布式计算、机器学习等新技术的蓬勃发展，设施 选址问题在这些新领域内也找到了重要应用，比如局域网代理服务器的选择问 题【2 】，分布式数据库数据副本安置问题【3 】，机器学习中的聚类算法等。为设施选 址问题设计更快更好的算法仍然是当前计算机算法研究的一个活跃领域。 本章先介绍一般形式的设施选址问题，然后介绍已有的相关工作，最后给 出本文的研究内容和组织结构。 1 1 设施选址问题概述 参考文献【1 】和 4 e p 的描述，本节给出一个设施选址问题一般形式的简单定 义。 设施选址问题的一般形式定义为，给出一个度量空间( m e t r i c ) m 和其中 的点集尸，这里的度量空间在大多数时候可以用一个边带权的有向或无向图g 来表示，点集尸对应图g 的节点，尸中任意两点在m 中的距离即为g 中对应节 点之间的最短路径长度。对于任意点x p ，存在设施建立费用白和服务费用函 数f x ：r + 专r + 。设施选址问题的目标是选择p 的一个子集s 建立设施并服务 尸中的所有点，使得总费用最小。总费用定义如下： c o s t ( s ，p ) - - - c ，+ 六( d ( x ，s ) ) ( 1 1 ) x e s x p 其中d ( x ，s ) 为点x 到点集s 的距离，定义为 d ( x ，s ) = m i n d ( x ，y ) ( 1 - 2 ) j ，j 这g s _ d ( x ，少) 为点x 到点y 的距离。 有些形式的设施选址问题会增加对选取的设施点集合大小的约束， isi p ( 1 3 ) 设施选址问题的以下三种形式被研究得较多。 第一章绪论 1 无约束( 1 3 ) ：这一形式被称为无容量限制设施选址问题( u n c a p a c i t i e d f a c i l i t yl o c a t i o np r o b l e m ) 。 2 设施建立费用为0 ，疋为线性函数，带有约束( 1 3 ) ：这一形式被 称为p 中心问题( p m e d i a n ) 1 4 ，它是著名的k m e a n 聚类算法的基础。 3 疋为阶梯函数，即到服务点集的距离在某个范围内时点x 的服务费用为 0 ，否则为某个依赖于x 的常数，并且带有约束( 1 3 ) ：这一形式被称 为p 覆盖问题( p c o v e r a g e ) 1 4 。 1 2 相关工作 一般形式的设施选址问题，包括p 中心和p 覆盖问题，是n p 完全问题，即 使度量空间m 建立在节点度数不超过3 的平面图的基础上吼欧几里德度量空 间下的设施选址问题仍然是n p 完全闯题【6 】。已有的研究工作主要集中在近似算 法和特殊度量空间下的精确算法。 在近似算法方面，般度量空间下的无容量限制的设施选址问题和p 中心 问题的常数近似的难度不小于最小支配集问题和最小集合覆盖问题的常数近似 问题【7 1 ，这意味这两个问题很可能不存在常数近似算法，因为除非n p = p ，否则 后两者不存在常数近似算法【5 】。但是在可用图表示的度量空间上，p 中心问题和 无容量限制的设施选址问题存在常数近似算法【8 , 9 , 1 0 。第一个p 中心问题的常数 近似比的近似算法在1 9 9 9 年被提出鲫，其近似比为2 0 3 。之后的文献【2 5 】给出 了一个近似比为6 的p 中心算法，其时间复杂度是o ( n l o g n ( l + l o g n ) ) ，这里 的l 是度量空间内任意两点之间距离的最大值的二进制表示的长度。文献 2 6 】 通过应用拉格朗日松弛法改进文献 2 5 】中的近似算法得到了所谓的解的连续性， 从而把近似比改进为3 。还有研究者证明了任何p 中心问题的近似算法的近似比 都不可能低于某个常数【4 l 】。同时较多的针对p 中心问题的启发式算法t 2 7 , 2 8 , 2 9 , 3 0 被提出，这些启发式算法被实验证明有一定的实用性。分支限界搜索 ( b r a n c h a n d b o u n d ) ，分支定价搜索( b r a n c h a n d p r i c e ) ，拉格朗日松弛法 ( l a g r a n g i a nr e l a x a t i o n ) ，整数规划( i n t e g r a lp r o g r a m m i n g ) ，线性规划松弛法 ( 1 i n e a rp r o g r a m m i n gr e l a x a t i o n ) ，随机取整法( r a n d m i z e dr o u n d i n g ) 等近似算 法领域内的通用技术被广泛应用于p 中心问题和无容量限制设施选址问题的求 解中 3 3 3 4 , 3 5 1 。另外遗传算法( g e n e r i ca l g o r i t h m s ) ，神经网络算法( n e u r a ln e t w o r k ) ， 蚁群算法和模拟退火算法( s i m u l a t e da n n e a l i n g ) 也被应用于求解大规模p 中心 问题 31 , 3 2 , 3 6 , 3 8 , 3 9 , 4 0 , 4 2 1 。 在特殊度量空间方面，研究得较多的是直线和树。在这两个度量空间下， 第一章绪论 设施选址问题的各种形式都存在多项式算法。直线上的p 中心问题和p 覆盖问 题分别有o ( p n ) 和o ( n 2 ) 时间复杂度的动态规划算法【4 1 ，直线上的无容量限制设 施选址问题有接近线性的动态规划算法【4 】。直线上p 中心f - j 题和p 覆盖问题的在 线算法也得到了关注和研究，在线算法是能够在直线的一端增加点的情况下快 速计算出新的p 中心或者p 覆盖的算法。相对于设计离线算法，设计在线算法 的难度更大。文献【2 3 】通过改进并推广文献 2 4 1 5 b 的直线上p 中心在线算法设计 了在均摊d ( p ) 时间内计算出在直线一端增加点后新的p 中心，文献 2 3 】也给出 了一个求解直线上p 覆盖问题特殊形式( 所有被服务点的距离闽值都相同) 的 均摊d ( p ) 时间的在线算法，但是设计直线上p 覆盖问题的在线算法仍然是一个 未解决的问题。 无向树上的p 中心问题和p 覆盖问题有历史较久的经典动态规划算法【1 1 1 ， 其时间复杂度是o ( p 2 n 2 ) ，之后的各种改进算法几乎都建立在文献 1 l 】的动态规 划基础之上。文献【1 2 】对文献【1 1 】中的动态规划做了少许改进并通过更加细致的 时间复杂度分析得到了一个时间复杂度为o ( p n 2 ) 的算法。文献 1 3 】对无向树上 的无容量限制设施选址问题提出了高效的o ( n l o g n ) 的算法，其方法是将动态规 划的状态函数反离散化，即用一个连续函数来表示若干个状态，从而突破了状 态个数的计算下界。受到这一算法的启发，文献【1 4 】设计了一个o ( n l o g p 2 厅) 的 反离散化动态规划算法，这一算法虽然在p 是输入的情形下并不是多项式算法， 但是在p 是常数的情况下该算法是目前唯一的时间复杂度低于平方的无向树p 中心问题算法。有向树上的p 中心闯题由于其在互联网代理服务器和网页缓存 服务器的选取问题上的应用也得到了一定的研究【2 】，文献【1 2 】中的无向树下的算 法可以简单的转化为有向树下的同样时间复杂度的算法，不过由于其较高的空 间复杂度，文献 1 5 】提出了一个空间复杂度较低的动态规划算法。 另外当p 为较小常数的时候，树度量空间下的p 中心问题和p 覆盖问题有 更加高效的算法。无向树上的l 中心( 1 - m e d i a n ) 问题是一个历史非常悠久的经 典问题，该问题简洁的线性算法在上世纪7 0 年代被提出【1 6 朋，并且该算法和相 关的引理对以后的研究有着重要的影响。无向树上的2 中心问题存在o ( n l o g n ) 时间的算法【1 s , 1 9 1 ，这些算法都是基于经典的l 中心算法。有向和无向树上的3 中心也有o ( n l 0 9 3 ，z ) 时间的算法【1 4 挪】。除此之外，在更改树节点权值，增加或 删除树边等操作下动态维护树的p 中心的动态算法也得到了一定程度的研究。 文献 2 1 给出了一个利用动态树1 2 2 j 数据结构在树节点权值动态增加的情况下在 对数时间内维护1 中心的算法，但是这个算法不能处理树节点权值变小的情况。 文献【4 3 】应用比动态树更加复杂的拓扑树( t o pt r e e ) 4 4 , 4 5 】实现了在更改树节点权 值，增加或删除树边的情况下对数时间内维护l 中心的数据结构和算法。一些 第一章绪论 带约束的无向树上2 中心问题也被提出和研究，文献 4 7 】对带距离约束( 2 个中 心之间的距离不超过某个给定的闽值) 和带半径约束( 树节点到中心的最远距 离不超过某个给定的阈值) 的2 中心问题都给出了接近线性的算法。无向树上 的l 覆盖问题比l 中心问题要困难许多，直到最近才有低于平方时间复杂的算 法被提出1 4 6 1 ，而且相对于无向树上的1 中心算法该算法非常复杂。 由于在互联网，局域网，分布式计算等方面的应用【5 ”2 l ，无向树p 中心问 题的一些限定形式也得到了研究。最早被研究的是树核心( t r e ec o r e ) 问题，即 在给定的树上找到一条路径使得所有树节点到这条路径的距离加权和最小，这 样的路径被称为树的核心( c o r e ) ，存在线性时间算法【4 8 】找到树的核心。树核 心问题的一个限定形式，带长度限制的树核心问题即选取的路径长度不能超过 某个给定的常数，也得到了关注并且有接近线性时间的算法被提出 4 9 , 5 0 1 。树核 心的推广形式k 子树核心( k t r e ec o r e ) 在文献 5 1 】中被提出，k 子树核心问题 要求找到一棵含有最多k 个叶子节点的子树使得所有树节点到这棵子树的加权 距离和最小，树核心即为k 等于2 的k 子树核心，k 子树核心问题存在线性时 间的贪心算法【5 3 1 。由于在分布式数据库中的应用【5 2 1 ，k 子树核心的一个限定形 式，带直径约束的k 子树核心问题，被提出和研究，这个限定形式要求选取的 k 子树核心的直径不能超过某个给定的常数，文献【5 4 】在 5 3 的k 子树核心算法 的基础上提出了平方时间复杂度的算法。 1 3 本文研究内容和研究思路 本文将研究特殊度量空间下的一些设施选址问题，包括p 中心问题和p 覆 盖问题以及它们的某些限定形式，这些问题在互联网，分布式计算等领域有一 定的应用。 1 无向树全覆盖问题的研究与应用。无向树全覆盖问题是无向树上l 覆盖 问题的一个限定形式，增加的限定是要求选取的服务节点能够覆盖所有的树节 点，在有多个选择的情况下选择使所有树节点到服务节点的加权距离和最小的 一个。这个问题的算法可以用来求解树形网络的代理服务器或者网页缓存服务 器的选择问题。本文提出了一个时间复杂度为o ( n l o g n ) 的简洁算法来解决无向 树全覆盖问题。 2 ，直线上p 覆盖问题的改进算法。跟直线上的p 中心问题相比直线上的覆 盖问题可以用几乎相同的动态规划算法解决【们，但是因为p 覆盖问题的服务费 用函数是非线性的阶梯函数，所以其动态规划算法的时间复杂度为o ( n 。) ，高 于直线上p 中心问题动态规划算法的o ( n p ) 时间复杂度。本文在文献 4 1 q b 动态 4 第一章绪论 规划算法的基础上利用高效的数据结构和查询优化技术将该算法的时间复杂度 改进为o ( n p l o g n ) ，空间复杂度改进为o ( n l o g n ) 。改进算法用到的数据结构是 扩展的二分查找树【5 5 1 ，用到的查询优化技术是f r a c t i o a n ic a s c a d i n g t 5 6 5 7 1 。 3 无向树上k 节点子树核心问题的研究与应用。无向树上k 节点子树核 心问题是无向树上p 中心问题的一个限定形式，增加的限定是要求选取的k 个 节点构成一棵联通的子树。k 节点子树核心是针对树形网络上的分布式数据库 数据副本最优安置【5 2 】的应用需要而提出的，相对于文献 5 4 1 中的带直径约束的k 子树核心，k 节点子树核心直接限制了子树核心的节点个数，在分布式数据库 的读操作和写操作之间达到了更好的平衡，本文也通过实验证明了这一点。为 了解决这一问题，本文提出了两个动态规划算法，一个时间复杂度较高但是编 程实现简单，另一个时间复杂度较低但是编程实现比较复杂，不同的应用环境 可以选用不同的算法。 4 动态维护无向树1 中心问题。本文提出了利用简单的动态树 2 2 1 数据结构 在对数时间内维护节点权值可以动态改变的无向树的1 中心的算法，从而改进 了文献 2 1 q h 的算法，文献【2 1 】中的算法不能处理树节点权值变小的情况。虽然 文献 4 3 】中的算法也能解决这一问题，但是它使用了非常复杂的拓扑树【4 4 , 4 5 】，相 对而言本文提出的算法更加简单实用。 5 无向树上的p 中心问题。这一问题是设施选址问题中的难点，迄今为止 最快的算法的时间复杂度是o ( p n 2 ) 和o ( n l o g p “聆) 【1 4 】，远高于无向树上的 无容量限制设施选址问题的最低时间复杂度o ( n l o g n ) 1 3 】。而实际上p 中心问 题是无容量限制的设施选址问题的一个限定形式，即选取的设施数目不能大于 p 。本文研究了p 中心问题和无容量限制设施选址问题两者之间的联系，在文献 【1 3 】的无向树上无容量限制设施选址问题算法的基础上提出了一个基于二分查 找的无向树上p 中心问题的算法。理论上这一算法并不能求解所有的输入实例， 但是大量的验证实验表明算法能够求解绝大部分输入实例。 1 4 本文组织结构 本文分为七章，各章节的内容安排如下： 第一章是绪论。首先对设施选址问题进行概述，然后介绍这一领域内的相 关工作，最后给出本论文的研究内容和组织结构。 第二章研究无向树全覆盖问题。首先描述无向树上的全覆盖问题及其在互 联网中的应用。接下来对这一问题进行了分析，得出若干重要的引理，最后在 这些引理的基础上设计出简单高效的算法。 第一章绪论 第三章研究直线上p 覆盖问题问题。首先描述并分析已有的平方时间复杂 度的动态规划算法，找到算法的时问瓶颈所在，然后提出用子加速算法的数据 结构，最后描述改进算法。 第四章研究无向树k 节点子树核, t i 骑- j 题。首先介绍无向树k 节点子树核心 问题在分布式数据库中的应用以及相关工作，然后严格定义无向树k 节点子树 核心阚题，接着描述求解该淌题豹两个动态规鲻算法，最后秘吊对比实验验证 这一模型在分布式数据库的设计中的优化作用。 第五章研究动态维护无向树1 中心问题。首先介绍经典的无向树l 中心算 法和相关的定理，然后介绍已有的动态算法，最后介绍经典的动态树数据结构 并描述本文设计的基于动态树的算法。 第六章研究无向树上的p 中心问题。首先介绍并分析已有的算法，重点介 绍无向树上的无容量限制设施选址问题的o ( n l o g n ) 时间算法。然后分析p 中心 问题跟无容量限制设旌选址问题之阀的紧密联系并导出重要定理。并在定理基 础上描述一个基于二分查找的求解无向树p 中心问题的实用算法。之后指出算 法的不足之处并分析在哪些情况下算法不能求得最优解，最后通过实验验证算 法在大部分情况下是可以求得最优解的。 第七章是结束语，总结本文的主要工作、贡献和创新点，并展望下一步的 研究工作。 6 第二章无向树全覆盖问题的研究与应用 第二章无向树全覆盖问题的研究与应用 本章研究无向树上l 覆盖问题的一个限定形式，无向树全覆盖问题，这个 问题在互联网技术中有一定应用。本章首先用数学语言严格描述问题定义，然 后介绍该阕题在互联网技术中鲶应用以及已有相关工作，最后详细描述本文提 出的高效算法并严格证明算法的正确性。 2 1 无向撕全覆盖问题定义 无向树全覆盖问题是无向树1 覆盖问题【4 6 】的推广形式，本节在文献 4 6 】中的 无向树l 覆盖问题定义的基础上给出无向树全覆盖问题的定义。 给出一棵无向树丁( 矿，) 。这里矿是节点数哥为嚣的节点集合，e 是边集合， 对于任意边e e ，三( p ) ( 三( p ) 0 ) 表示边e 的长度。对于任意节点y v ，r ( v ) 表 示节点 ，的距离闽值，r v ( v ) ( r e ( v ) 0 ) 表示节点1 ，的权值。无向树全覆盖问题要 求从矿中选择一个满足( 2 1 ) 式约束的节点s 作为服务节点，并且使得( 2 ，2 ) 式定义的距离加权和最小。 v v v , d ( v ，s ) 尺( v ) ( 2 1 ) w d ( v ，j ) = d ( v ，s ) r v o , ) ( 2 ，2 ) k r 这里d ( v ，5 ) 表示节点 ，和s 之间的路径长度。( 2 1 ) 式的意义是所有树节点都 被服务节点s 覆盖，节点1 ，被覆盖当且仅当1 ，跟服务节点j 之间的距离不大于1 ， 的距离闽值r ( v ) 。满足约束( 2 1 ) 的服务节点称为可行服务节点。使得( 2 2 ) 式定义的距离加权和最小的可行服务节点称为最优可行服务节点。按照问题定 义可行服务节点可能不存在，所以问题要求找出一个可行的最优服务节点或者 报告不存在可行的服务节点。 2 2 无向树全覆盖问题的应用 无向树全覆盖问题的应用跟文南t 2 l e p 网页代理服务器选择问题类似，本节 在文献【2 】中应用的基础上描述无向树全覆盖问题在树形局域网中的一个应用， 随着互联网的普及，公司和大学通常都有自己的局域网，局域网中的主机 通过一台代理服务器跟i n t e r n e t 相连。通过代理服务器的配置可以方便的进行 i n t e r n e t 访问控割，建立局域网防火墙等，从而保证内部局域网的安全。树形网 第二章无向树全覆盖问题的研究与应用 络是由于其结构简单费用较低而被广泛应用于局域网的构建中，无向树全覆盖 问题可以应用于在树形网络中选择合适的代理服务器。在己知树形局域网中每 条链路的数据传输时间的情形下，合适的代理服务器首先要满足一个硬性条件， 局域网中的每台主机跟代理服务器之间的数据传输时间不能超过某个依赖于该 主机的阈值，这个阈值即为该主机上的应用程序访问i n t e m e t 时能忍受的最大延 迟时间，这个时间阈值对应无向树全覆盖问题中树节点的距离阂值r ( ，) 。如果 有多个满足上面硬性条件的候选代理服务器，就选取使得局域网主机的平均延 迟最小的代理服务器，即使得所有主机访问代理服务器的延迟时间的加权和最 小。主机的权值即为该主机访问i n t e m e t 的频率，对应无向树全覆盖问题中树节 点的权值r v ( v ) ，平均延迟时间就对应( 2 2 ) 式定义的距离加权和。所以无向全 覆盖问题的最优可行服务节点就是对应树形局域网最合适的代理服务器。 另外树形网络中网页缓存服务器的选择问题也可以应用同样的模型解决， 网页缓存技术是降低互联网数据流量和减少拥塞的有效手段【2 】。 2 3 无向树1 覆盖问题的相关工作 无向树1 覆盖问题的定义跟无向树全覆盖问题类似，只是优化的目标是最 大化所有被服务节点覆盖的树节点的权值和，严格定义如下】： r v s ( v ，j ) =形( 1 ，) ( 2 3 ) w v ，d ( v ，s ) a a ( v ) 容易看出无向树全覆盖问题是无向树l 覆盖问题的一个限定形式，增加的限定 是所有树节点都被覆盖到。 无向树p 覆盖问题存在o ( p 刀2 ) 时间复杂度的算法【1 1 1 ，但是这个算法不能直 接用来解决无向树的全覆盖问题，而且这个算法的时间复杂度过高。对于无向 树上的l 覆盖问题文献 4 6 1 提出了一个时间复杂度为o ( n l o g zn l o g l o g n ) 的流 程非常复杂的算法，但是这个算法只能用来求得无向树全覆盖问题中的可行服 务节点，不能求得最优可行服务节点。另外无向树全覆盖问题的优化目标( 2 2 ) 式跟无向树l 中心问题的优化目标相同，只是在全覆盖问题中中心节点只能从 可行服务节点中选取，所以也可以说无向树全覆盖问题是无向树l 中心问题的 一个限定形式，但是由于约束( 2 1 ) 式的存在，无向树1 中心问题的算澍1 6 ，1 7 】 也不能用来求解无向树全覆盖问题。 2 4 无向树全覆盖问题的高效算法 本节给出一个解决无向树全覆盖问题的高效算法，该算法的时间复杂度是 第二章无向树全覆盖问题的研究与应用 o ( n l o g n ) ，空间复杂度是线性的。 算法主要由三步组成，第一步找出无根树的中心节点( 1 - m e d i a n ) c 第二 步把无根树转为以c 为根节点的有根树，再利用有根树的特性在o ( n l o g n ) 的时 间内找到每个节点对应的最远可行祖先节点。第三步在所有最远可行祖先节点 中选择深度最大的节点作为候选服务节点，然后检查该节点是否是可行的服务 节点，如果是则返回该节点作为最优可行服务节点，否则报告不存在可行服务 节点。算法的三步分别详细描述如下。 2 4 1 中心节点寻找 无向树的中心定义为使( 2 2 ) 式定义的树节点加权距离和最小的树节点c ， 等价于无向树的l 中心，这个问题有经典的线性算法，这里简单复述如下 t 6 j 刀： 任意选择一个树节点，然后将树丁转为以，为根节点的有根树，记正为有根 树r 中以节点1 ，为根的子树，佤) 为子树z 中所有节点的权值和。从节点，出 发找出满足如下( 2 4 ) 式且深度最大的树节点c ，那么c 就是树丁的中心【1 6 ，1 7 1 。 r r ( t v ) 形( 丁) 一r v ( t v ) ( 2 4 ) 其中w ( z ) 是树丁所有节点的权值和。树节点的深度定义为，根节点，的深度为 0 ，其余节点深度为其父节点深度加1 。 。 寻找满足( 2 4 ) 式且深度最大的节点可以在线性时间内完成，首先在线性 时间内预处理计算出所有的形僻) ，然后以根节点，为当前节点，检查是否存在 当前节点的某个儿子节点满足( 2 4 ) 式，如果存在就更新当前节点为这个儿子 节点并重复上面的检查，否则当前节点就是树的中心，算法停止。这个算法能 够在线性内完成，因为初始的根节点满足( 2 4 ) ，而任意节点最多有一个儿子 节点满足( 2 4 ) 式，而且算法最多检查d ( 刀) 个节点。算法的正确性可参见文献 1 6 ，1 7 】。 2 4 2 最远可行祖先节点寻找 先把树丁转化为以第一步中找到的中心节点c 为根的有根树，这一步可以用 简单的广度优先( b f s ) 或者深度优先( d f s ) 搜索来实现。记有根树中任意节 点v 的父亲节点为p ( v ) ，且令尸( c ) = c 。对任意节点v ，用f ( v ) 表示v 的可行服 务节点集合，即 f ( v ) = ud ( v ，“) r ( v ) ) ( 2 。5 ) 下面要对任意节点1 ，找出其对应的最远可行祖先节点，记为剐( v ) ，f a ( v ) 定 9 第二章无向树全覆盖问题的研究与应用 义为f ( v ) 中距离v 最远且为 ，的祖先的节点。这里祖先节点递归定义为：节点 是节点v 的祖先节点当且仅当掰= ，或者”是尸( v ) 的祖先节点。一个简单可行的 算法是对每个节点1 ，从近到远依次检查1 ，的祖先节点直到找到最远的能服务v 的祖先节点。这个算法虽然简单，但是最坏情况下的时间复杂度是q ( 厅2 ) 的， 效率太低。这里给出一个基于深度优先搜索和二分查找的快速算法，伪代码描 述如下： 算法2 1 ：最远可行祖先节点查找算法一a n c e s t o r ( v ，【v l ，】， d n ，或】，刀) 输入：当前访问节点v ，根节点到1 ，的路径数组【v j9 7 9 k 】，表示，的祖先节 点从近到远依次为， ，h ，距离数8 1 t d n ，以】表示根节点到u ， 的距离。 输出：所有，的最远可行最先节点尉p ) 。 1 在距离数组，或】中二分查找位置p ，使得p 是满足d p 以一r ( v ) 的 最小的p 。 2 令f a ( v ) ：= 1 ，。 3 对v 的所有儿子节点u 递归调用 a n c e s t o r ( u ，n ，屹，甜】， 反，玩，以+ 棚，玎+ 1 ) 这里d 是 ，与甜之间的边长 度。 利用算法2 1 只需要调用一次a n c e s t o r ( c ，【c 】，【0 】，1 ) 就能计算出所有节点的最 远可行祖先节点。在编程实现算法2 1 的时候，路径数组和距离数组实际上是 两个可以随机访问元素的栈，只需要用两个长度跟树节点数目相同的数组来简 单模拟，编程实现的复杂度非常低。 2 4 3 最优可行服务节点寻找 在得到所有节点的最远可行祖先节点f a ( v ) 后，在最远可行祖先节点集合 j v a ( v ) f ，n 中找到深度最大的节点w 。这里节点深度定义为：根节点r 深度 为0 ，其他节点深度为其父节点深度加l 。把w 作为候选服务节点，再检查w 是 否能够覆盖所有节点，即满足( 2 1 ) 式，如果满足则把w 作为最优可行服务节 点返回，否则报告树中不存在可行服务节点。检查w 是否可行的算法可以使用 简单的深度优先算法，算法从节点w 出发历遍所有节点，算法的伪代码描述如 下： 1 0 第二章无向树全覆盖问题的研究与应用 算法2 2 ：可行服务节点检查算法c h e c k ( v ，d ) 输入：当前访问节点，w 到当前节点1 ，的距离d 。 输出：节点w 是否可行的布尔值。 1 标记节点1 ，为已访问。 2 如果r ( ，) 0 ，于是w d ( v ，c ) w d ( v ，毋) ，代入( 2 6 ) 式可得 2 ( 瓦) 一w ( t o ) 0 ( 2 7 ) 又因为x 是y 在乃中的父亲节点，必定存在某个& 是少的祖先节点，所以有 ( 乃) ( 咒) ( 2 8 ) 于是由( 2 7 ) 式和( 2 8 ) 式可得， 2 形( 乃) 一w ( t a 0 ( 2 9 ) 将( 2 9 ) 式代入( 2 6 ) 式可得w d ( v , 曲w d ( v ，y ) ，引理得证。 第二章无向树全覆盖问题的研究与应用 u 引理2 6 对于乃的任意树节点x ，y ，如果x 是y 在瓦中的祖先节点，那么 w d ( v ，功w d ( v ，夕) 。 证明：设在t o 中节点x 到节点y 的路径为工= h ，吃，- l ，y = ，由引理2 5 可知， w d ( v ，m ) w d ( v ，m + i ) ( 1 f p 覆盖问题的目标是选择的一个最多包含p 个点的子集s 来建立设施，使得 总代价尽量小。总代价包括两部分，在s 上建立设施的费用和服务其他点的费 用。在s 上建立设施的费用等于在s 中每个点上建立设施的费用之和，其中在 点上建立设旌的费用已知为c f 。服务费用等于中所有点被s 服务的费用之 和，点 被设施点集合s 服务的费用函数定义如下 粥) = 西0 鳃：岛善 ( 3 2 )