最小Manhattan网络的算法复杂性研究.doc

最小Manhattan网络的算法复杂性研究计算机学院 郭泽宇指导教师 孙贺摘要：本文研究了最小Manhattan网络的复杂性和近似算法。通过给出3-可满足问题的基于部件的归约，本文证明了最小Manhattan网络是强NP-完全的，从而解决了这一长达十年的未知问题。此外，本文描述了一个时间复杂度为O(nlogn)的2-近似算法。该算法在运行时间和近似度上都达到目前最优。关键词：NP完全性 近似算法 计算几何Abstract: In this paper, we have studied the complexity of Minimum Manhattan Network and its approximations. Using a gadget-based reduction from 3-SAT, we showed that Minimum Manhattan Network is strongly NP-complete, which was open for ten years. Moreover, we have described a 2-approximation algorithm with time complexity O(nlogn), which has the best time complexity and approximation ratio up to now.Keywords: NP-completeness, Approximation Algorithm, Computational Geometry引言由于在城市规划，网络路由，分布式计算，大规模集成电路设计以及计算生物学8等众多领域的应用，J. Gudmundsson等人在文献5中首先提出了最小Manhattan网络(MMN)问题。该问题的描述为：对于平面上给定的若干个点，设计出由直线段构成的网络，使得任意两点间存在Manhattan路径（即由直线段构成且长度最短的路径），并在满足此条件的前提下使得网络总长度达到最短。由于两点间Manhattan路径的长度同时也是L1范数下两点间的距离，可以看出，最小Manhattan网络问题等价于求L1范数下最小1-spanner的问题。更一般的t-spanner问题参见4。在文献5中，作者提出了如下的三个重要问题：(1) MMN是否是NP-难的；(2) 是否存在该问题的PTAS近似方案；(3) 是否存在该问题的2-近似算法。同时，作者提出了一个时间复杂度为O(n3)的4-近似算法和一个时间复杂度为O(nlogn)的8-近似算法。此后，研究者们提出了一系列具有更优近似度和更低时间复杂度的近似算法1,2,3,9,10,11，其中9,10的证明是有缺陷的。本文作者也提出了基于动态规划的时间复杂度为O(n2)的2-近似算法6和基于贪心策略的时间复杂度为O(nlogn)的2-近似算法7，后者在近似度和时间复杂度上都达到了已知的最优。本文作者通过给出从3-SAT到MMN的归约，证明了这一问题是强NP-完全的，从而解决了它的复杂性问题。本文的前半部分将着重介绍这一归约，后半部分则用于描述7中的2-近似算法。1 预备知识对于平面上两点p, q，p.xq.x定义R(p, q)为以p, q为对角顶点的矩形区域（矩形可能退化成一条线）。定义垂直无限区域BV(p, q)为p,q间的垂直无界区域(x,y)|p.x=x=q.x。类似地，我们将BH(p,q)定义为p,q间的水平无限区域。记输入点集为T，对于T中的两点p,q, p.yq.y，如果在区域BV(p,q)-(x,y)|x=p.x,y=q.y中不含T中的任何点，则称R(p,q)为一个垂直带。类似地可给出水平带的定义。特别地，当p.x=q.x或p.y=q.y时，我们称这个带是退化的。图1给出了一个水平带的实例。图中点t位于q的右侧，因而不违反水平带的定义。图1 水平带对于平面中的点p，记Qk(p)为平面上以p为原点，代表第k象限的区域（含坐标轴）。 例如Q1(p)=(x,y)| p.x=x,p.y=y。2 归约框架我们的主要目标是将一个由n个变量、m个子句组成的布尔公式转换成顶点集T，使得是可满足的当且仅当存在一个T上的最小Manhattan网络G，其总长度不超过一个多项式时间可计算的函数Q。首先，在Manhattan网络中，我们可以用垂直和水平的带上的Manhattan路径来表示变量的赋值。如图2所示，实线代表赋值为1，虚线代表赋值为0。图2 Manhattan路径与变量的赋值其次，我们使用了若干部件(gadget)来完成归约。归约后得到的输入点集T的整体结构如图3所示，两个标号为2i-1,2i(1=i=n)的相邻垂直线段分别用来表示文字xi和它的否定。每个垂直线段的上部与部件DUMMY连接，下部与部件NEGATOR或TURN连接。变量的赋值通过部件SPLITTER间接地到达部件CLAUSE。部件CLAUSE连接的三条边分别表示一个子句中的三个文字。在部件CLAUSE中，三个变量的七种赋值(23-1)可以使部件内的局部网络最小化。图3 输入点集的整体结构3 部件的一般结构我们的构造依赖于六个不同的部件，分别称为NEGATOR， TURN，SPLITTER， CLAUSE， ADAPTOR和DUMMY。一般来讲，每个部件中含有T中的6个点，其相对位置如图4所示。图4 部件的一般结构其中中间的两对点w1,g1以及w2,g2之间的距离极短，以至于可忽略不计。在对部件的讨论中，我们按照特定的方式来摆放部件使得一个部件的b1和其他某一部件的b2形成一个带。由于b1位于一个带的左下端，b2位于一个带的右上段，所有的带将依据这种依赖关系形成图3。设B是一个边与坐标轴平行、且包含所有部件和带的大矩形。将其顶点加入集合T。对每个部件，再加入如图5所示的点。图中实线代表的线段必然被包含在任何T上的Manhattan网络中，这些线段的集合称为EF。图5 输入点集T中额外的点进一步，对任一部件，Manhattan网络必须包含该部件内部任意两点的路径。对于不同的部件，这些点间的相对距离存在差异，并代表赋值间相应的关系。在下面，我们将给出各类部件的设计思路。其中连接w1,g1和w2,g2的线段长度忽略不计。4 部件的具体结构为了独立地考察不同的部件，我们引入与每个带相关的潜在代价(potential cost) ，其值固定地设为10。每个部件得到与之相邻的带的潜在代价当且仅当带上的Manhattan路径位于部件的内部。如图6所示，部件NEGATOR由两个相交的带组成。部件中顶点的连接由与带对应的变量v1和v2的赋值决定。NEGATOR的构造满足，当v1和v2的赋值不同时，部件中局部的Manhattan网络的代价最小，如表1所示。图6 部件NEGATOR表1 部件NEGATOR的代价函数表v1v2线段长度潜在代价总代价001002012001100101101010010110111200120部件SPLITTER提供了一种传输信息（0-1赋值）的方法，使得代价取得最小值当且仅当部件里的三条带表示相同的赋值。参见图7和表2。图7 部件SPLITTER表2 部件SPLITTER的代价函数表v1v2v3线段长度潜在代价总代价0007710870017220920106920890116730971001070107101871097110871097111672087由于初始时变量的赋值由垂直带来表示，部件TURN的作用是转换信息流的方向，使得代价取得最小值当且仅当部件中的两个交叉的带表示相同的赋值，参见图8和表3。图8 部件TURN表3 部件TURN的代价函数表v1v2线段长度潜在代价总代价0040105001402060106006011401050部件CLAUSE用于在可满足的赋值和不可满足的赋值所对应的代价函数间形成一个间隙。即在该部件中，代价可以对8种可能赋值中的7种赋值获得同样的最小值。参见图9和表4。图9 部件CLAUSE表4 部件CLAUSE的代价函数表v1v2v3线段长度潜在代价总代价000702090001801090010703010001170209010080109010190090110702090111801090然而，为了达到这样的目的，部件CLAUSE中的两个带的宽为10，小于标准带的宽度20。为了构造我们所需要的网络，我们引入部件ADAPTOR（参见图10，表5）来连接两个不同宽度的带。图10 部件ADAPTOR表5 部件ADAPTOR的代价函数表v1v2线段长度潜在代价总代价0055106501680681047206711551065为了给出每个垂直带的上界，我们引入部件DUMMY（参见图11，表6）。图11 部件DUMMY表6 部件DUMMY的代价函数表v1线段长度潜在代价总代价055106515510655 分析对于含有n个变量，m个子句的布尔公式，在归约后的网络中有m个CLAUSE部件，2m个 ADAPTOR部件，m+n个TURN部件，m+n个 NEGATOR部件，3m个SPLITTER部件和2n个DUMMY部件。在归约后的顶点集合中，部件总数nG=8m+4n，带的总数nS=10m+3n。下面的定理给出了T上的网络G是Manhattan网络的充要条件。定理1：一个顶点集合T上的网络G是Manhattan网络当且仅当G包含：(1)线段集合EF； (2) 所有带上的Manhattan路径； (3) 任意部件的局部Manhattan网络。在下面的分析中，令LF为EF中线段的总长度，LS为所有带的总长度。容易看到上述这些量都是n与m的多项式函数。令Q=LF+LS+costmin-10nS+1，则：定理2：可满足当且仅当存在T上的Manhattan网络G，总长不超过Q。由于3-SAT问题是NP-完全的，结合这一性质和定理2的证明，我们得到定理3：MMN问题是强NP-完全的，并且在PNP的假设下不存在FPTAS。6 Pareto包和楼梯元件在文献3中，Chepoi等人首先引入了Pareto包的概念。在MMN的近似算法设计中，Pareto包发挥着重要的作用。下面，我们对Pareto包加以简单的介绍。对于平面上任意两点p,q，若q到T中任意一点的距离不超过p到该点的距离，且q到T中某一点的距离比p到该点的距离短，则称p被q控制。不被平面上任何点控制的点称为有效点(efficient point)。Pareto包P(T)是由平面上所有有效点组成的集合。图12给出了一个Pareto包P(T)的实例。图12 点集T及对应的Pareto包P(T)进一步，我们可以发现Pareto包是若干直线型凸多边形(ortho-convex rectilinear polygons)的并集，每一个直线型凸多边形称为一个块(block)。在文献3中，V. Chepoi等人将块的概念进一步区分为平凡块和非平凡块。平凡块的最小Manhattan网络是可以轻易构造出的。另一方面，他们证明了：选取非平凡块的边界作为Manhattan网络的一部分一定是最优的。因而，原问题可被归约为：对每个非平凡块，设计其上的最小Manhattan网络。并且对于归约后的问题，我们可以通过计算Pareto包得到最优网络的一部分，即非平凡块的边界。在我们的近似算法设计中需要用到的另一概念被称为楼梯元件。首先，对于T中任一点p，定义fxk (p)为Qk (p)中除p外水平坐标最接近p.x的输入点，类似地定义fyk (p)为Qk (p)中除p外垂直坐标最接近p.x的输入点。特别地，如果不存在这样的点，则置其值为NULL。不难给出对T中所有点计算fxk和fxk的O(nlogn)时间算法，分别用CreateCandidatesxk和CreateCandidatesyk来表示。对相交的垂直带R(p,q)和水平带R(p,q)，第三象限对应的楼梯元件Tpp|qq 被定义为除q,q外满足fx3(t)=p或fy3(t)=p的点t的集合，如图13所示。类似地可给出其它三个象限相应的楼梯元件的定义。图13 第三象限对应的楼梯元件Tpp|qq7 近似算法描述下面我们给出近似算法的描述：首先，计算Pareto包P(T)，然后对不同的块独立地构造Manhattan网络。对非平凡块，我们可以简单地将其中的两点用Manhattan路径相连，从而得到最优的Manhattan网络。对非平凡的块，我们首先运行一个分解过程Decompostion，将点集T分解为水平带和垂直带中的点和楼梯元件中的点。之后，我们分别地对水平和垂直带以及楼梯元件这两部分构造Manhattan网络。在水平带和垂直带中，构造过程是迭代的，如图14所示。在该过程第一阶段，每次选取非平凡块边界上的一条线段，将该线段加入网络中，同时添加新的点，并将水平带和垂直带用添加了点后的带来替换。在第二阶段，每次选取一条水平带或垂直带，添加其边界上平行的两条线段，类似地添加新的点，并更新水平带和垂直带。最后，我们在平行线段间添加转换线段(switch segment)将其桥接起来。可以证明在这样的构造下，水平和垂直带中Manhattan路径总长度不会超过最优解的2倍。图14 构造水平带和垂直带上Manhattan路径的过程在对楼梯元件中的点建立Manhattan网络时，出于方便，我们首先定义楼梯(staircase)的概念。由于对每个楼梯元件Tpp|qq ，其水平和垂直带R(p,q)以及R(p,q)中的Manhattan路径已经得到，对应的楼梯Spp|qq可定义为由这两条路径以及楼梯元件中的点所界定的平面区域，如图15所示。其中所有已加入网络的Manhattan 路径都已从该区域中去掉，在图中用虚线表示。图15 楼梯的定义网络的具体构造运用了贪心和递归的思想，其大致过程为：对于每一个楼梯S（不失一般性，假设该楼梯是关于第三象限的），每次选取楼梯元件中相邻的两点ti,ti+1，并添加水平线段hi和垂直线段vi+1，将楼梯划分为具有相同性质但更小的楼梯Topi(S)和Righti+1(S)。由于新的楼梯保持了原有的不变量，这个过程可以递归地进行下去。ti,ti+1的选取采用贪心策略，目标为：hi,vi+1中较短的线段长度达到最大。可以证明在这样贪心策略下，构造出的局部网络是2-近似的。这里线段hi,vi以及区域Topi,Righti的定义见图16。经过以上两步构造过程，算法成功地给出了可行解，即T上的一个Manhattan网络。如前所述，在楼梯和带中，我们构造的网络都是2-近似的。并且，由于楼梯和带之间是不相交的，没有线段会被重复计算，从而整个可行解也是2-近似的。图16 hi,vi,Topi,Righti的定义定理4：对于给定包含n个点的输入点集T，存在算法在O(nlogn)的时间内计算出T上的一个Manhattan网络，其总长度不超过最优网络的2倍。参考文献1. M. Benkert, A. Wolff, and F. Widmann. The minimum Manhattan network problem: a fast factor-3 approximation. Proceedings of the 8th Japanese Conference on Discrete and Computational Geometry, 2005, pages 16-28.2. M. Benkert, T. Shirabe, and A. Wolff. The minimum Manhattan network problem: approximations and exact solution. Proceedings of the 20th European Workshop on Computational Geometry, 2004, pages 209-212.3. V. Chepoi, K. Nouioua, and Y. Vaxs. A rounding algorithm for approximating minimum Manhattan networks. Theoretical Computer Science, 390(2008):56-69.4. D. Eppstein, Spanning trees and spanners, J.R. Sack, J. Urrutia (Eds.), Handbook of Computational Geometry, Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000, pages 425-461.5. Gudmundsson, C. Levcopoulos, and G. Narasimhan. Approximating a minimum Manhattan network. Nordic Journal of Computing, 8(2001):219-236. Z. Guo, H. Sun, and H. Zhu. A fast 2-approximation algorithm for the minimum Manhattan network Problem. Proceedings of 4th International Conference on Algorithmic Aspects in Information Management, 2008, pages 212-223.7. Z. Guo, H. Sun, and H. Zhu. Greedy construction of 2-approximation minimum Manhattan network. Proceedings of the 19th International Symposium on Algorithms and Computation, 2008, pages 4-15.8. F. Lam, M. Alexandersson, and L. Pachter. Picking alignments from (Steiner) trees. Journal of