双会议服务器选址问题研究

徐 弈, 陈 莹

(1.西安理工大学 经济与管理学院,陕西 西安 710054; 2.西安交通大学 管理学院,陕西 西安 710049)

0 引言

中心选址问题(Center problem)[1,2]与中位选址问题(Median problem)[3,4]一直是选址问题中的研究热点与难点。中心选址问题可以等价于求解最小最大问题,以欧氏距离下的平面点集k中心选址问题为例,其选址目标为寻找k个选址设施的位置,要求点集中每个点到这k个选址设施的最近距离的最大值最小[5,6]。记P为平面上含有n个点{a1,a2,…,an}的点集,d(x,y)为平面上任意两点{x,y}的欧氏距离,所要寻找的k个选址设施为S={s1,s2,…,sk},则中心选址问题优化模型如下:

直观地,k中心选址问题等价于求解k个全等的圆覆盖整个点集P,并且要求这些圆的半径最小，而最优解对应的k个圆心即为设施的选址位置。

而对中位选址问题而言,该问题所对应的几何结构则没有中心选址问题那么直观。仍旧以欧式距离下的平面点集k中位选址问题为例,其选址目标为寻找k个选址设施的位置,要求点集中每个点到这k个选址设施的最近距离和最小,对应选址问题优化模型如下:

无论是k中心选址问题还是k中位选址问题,都已经被证明问题是NP难的[7],故很难给出最优解,因此学者往往考虑如下几个问题:针对这两个问题的近似算法或者启发式算法[8,9];在某些特殊距离或者特殊网络结构下的中心或k中位选址问题[10];考虑当k的值比较小时的中心或中位选址问题的最优算法[11];以及考虑k中心或中位选址问题的衍生问题,例如要求k个设施之间的距离满足某些关系,或者k个设施的位置带有一定的约束(限制在某些点处或者某些区域内)[12,13]。

本文考虑平面内欧氏距离条件下的2中位选址问题的衍生问题。2中心或中位选址问题直到现在还有许多学者在研究,2017年,Tan给出了2中心选址问题的O(nlog2n)时间算法[14],该算法的复杂性已经非常接近该问题的下界O(nlogn),这改进了1999年Chan设计的并行计算算法[15]。而最新的与2中心选址问题相关的文献是由Xu等人提出的最小最大2中心选址问题,该问题不仅要求两个圆的半径尽可能小,同时要求两个圆心之间的距离也不能超过两个圆的半径。2019年他们给出该问题的混合(两个圆心均在点集内部)与离散(只要求一个圆心在点集内部)的情况分别可以在O(n2log2n)和O(n2logn)的时间进行求解[16]。针对连续的情况(即对两个圆的圆心位置没有限制),Bhattacharya等人于2022年给出O(n2logn)时间的最优算法[17]。

1 研究动机与问题

1.1 研究动机

在网络中,双会议服务器选址问题的实际背景可以看成在平面点集结构中,寻找两个服务器,要求其他终端均连接这两个服务器中的一个,最终形成一个网络结构(树结构),而寻找目的是使得这个网络的花费最小。此时网络的花费为网络中所有两点的网络距离和(不包含两服务器)。双会议服务器选址问题不仅需要考虑如何寻找两个服务器位置,同时还需要考虑如何将点集中的点与这两个服务器相连接。如果不限制这两个服务器的位置,那么该问题与Weber问题一样[18],只能通过设计启发式算法或者近似算法进行求解,不存在最优算法。类似地,如果要求这两个服务器在点集内部,则可以证明该问题是多项式时间内可解的。本文的主要工作就是对这种情况,通过讨论其几何结构,给出多项式时间的算法。

1.2 问题描述

首先介绍只针对一个服务器(单服务器)进行选址的情况。记P为平面上含有n个点{a1,a2,…,an}的点集,每点的平面坐标对应记为(aix,aiy)(i=1,2,…,n),单会议服务器选址目标为p,其平面坐标对应记为(px,py),则单会议服务器选址问题定义如下:

问题1单会议服务器选址问题指最小化点集张成的一星树上所有叶子之间的距离和。其中点集的一星树是指由这n个点生成的一棵树,并且满足这n个点仅连接某一个点(不一定属于P)。

如果要求p∉P,该问题等价于著名的Weber问题并且可以证明该问题无法求得最优解[18]。如果要求p∈P,则可以通过遍历的方法求解,其时间复杂性为O(n2)。

类似的同样可以定义点集的二星树,二星树是指由这n个点生成的一棵树,同时满足这n个点仅连接某两个点{p,q}中的一个,并且这两个点{p,q}之间相互连接。其中这棵树上任意两叶子之间的距离可以写成f(ai,aj)=d(ai,p)+d(p,q)+d(p,aj),如果{ai,aj}同时连接p或者q,这时上式可以看成点p与点q重合,即d(p,q)=0。若要求{p,q}∈P,此时可以定义双会议服务器选址问题如下:

问题2双会议服务器选址问题指最小化点集二星树上所有两点之间的距离和。

与双会议服务器选址问题强相关的是2中心选址问题与最小直径树问题[19～21]。其中2中心选址问题用两个圆覆盖某个平面点集,并且要求两个圆的半径都尽可能小; 而最小直径树问题是指求解给定点集的一个生成树,使得该树的直径最小,其中树的直径是指这棵树上最远两点之间的距离。对于该问题曾证明,一定存在一棵一星树或者二星树是该点集的最小直径树[19]。而双会议服务器选址问题可以看成是二星最小直径树的衍生,它不仅仅要求这棵树最远两点之间的距离最小,同时要求这棵树所有叶子之间的距离总和最小。

本文结构如下,第2节给出最优解所对应的几何结构,以及该几何结构的构造思路,第3节给出最优解的求解算法并分析其算法复杂性,第4节给出结论与展望。

2 几何结构

d(q2,q)+…+d(pk1,p)+d(p,q)+d(q1,q)+d(pk1,p)+d(p,q)+d(q2,q)+…+

d(pk1,p)+d(p,q)+d(pk2,q)

这时考虑作{p,q}两点连线的垂直平分线,得到两个半平面,记包含点p的半平面内所包含的点为集合S1={u1,u2,…,uh1},其点的个数为h1,记包含点q的半平面H2内所包含的点为集合S2={v1,v2,…,vh2},个数为h2。此时分两种情况考虑:点集P中没有点在{p,q}连线的垂直平分线上和至少有一个点在{p,q}连线的垂直平分线上。

情况1没有点在{p,q}连线的垂直平分线上。

情况1.1h2

此时有k1k2>h1h2,对给定k1,k2,以得到如下引理:

情况1.2k1≥h1≥h2≥k2或k2≥h1≥h2≥k1。

这时k1k2≤h1h2,为了计算最优解,需要以下引理。不失一般性,考虑k2≤h2≤h1≤k1的情况:

引理2如果k2≤h2≤h1≤k1,此时最优解结构一定满足:如果K1中有x′个点属于S1,K2中有y′个点属于S2,则一定有k1-x′≥k2-y′。

证明由于k1-h1=h2-k2,由假设K1中有x′个点属于S1,K2中有y′个点属于S2,则K1中剩余点一定属于S2,K2中剩余点一定属于S1,即h2-y′=k1-x′=k2-y′。假设k1-x′

综上，得到最优解结构如下:

其中wi∈S2(i=1,2,…,h2-k2),并且这些点是S2中距离p最近的h2-k2个点。

证明由k1+k2=h1+h2,可以得到下式:

其中pi∈S2(i=1,2,…,k1-x′),qj∈S1(j=1,2,…,k2-y′)。对i=1,2,…,k-x′,j=1,2,…,k2-y′,由于d(pi,p)>d(pi,q),pi∈S2,d(qj,q)>d(qj,p),qj∈S1,有

图1 连接图例

同理,对于k1≤h2≤h1≤k2的情况,同样可以得到:

推论如果k1≤h2≤h1≤k2,有:

其中wi∈S1,i=1,2,…,h2-k1是S1中距离q最近的h2-k1个点。

情况2P中至少有一个点在{p,q}连线的垂直平分线上。

F2=k1k2(d(p,q))

与引理1类似地,可以得到:

引理4若h2

(h1+j)h2(d(p,q))

定理1令P为平面上包含n个点的点集,对P中固定的两点{p,q}并给定两个常数k1和k2,如果k2≤h2

k1k2(d(p,q))

其中wi∈S2(i={1,2,…,h2-k2})是S2中距离p最近的h2-k2个点。

如果k1≤h2

k1k2(d(p,q))

其中wi∈S2(i={1,2,…,h2-k1})是S1中距离q最近的h2-k1个点(见图2和图3示例,图2中h1=5,h2=3,j=2,k1=8,k2=2,图3中h1=5,h2=3,j=2,k1=2,k2=8)。

图2 h1=5,h2=3,j=2,k1=8,k2=2时的最优解

图3 h1=5,h2=3,j=2,k1=2,k2=8时的最优解

3 算法设计

定理2对给定包含n个点的点集P,双会议服务器选址问题可以在O(n3logn)的时间内求解。

4 结论与展望

本文考虑平面点集选址问题中的双会议服务器选址问题,即寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并给出时间复杂性为O(n3logn)的最优时间算法。双会议服务器选址问题以看成是2中位问题的衍生问题。目前,双会议服务器选址问题和最小直径树问题还没有学者给出时间复杂性小于O(n3)的最优时间算法,寻找这两个问题更深入的最优几何结构和性质将是改进这两问题算法复杂性的研究重点。

Algorithm 1 双会议服务器选址问题算法设计1:Initialization e=∞,c=Ø,cØ,A=ØB=Ø,a=Ø,b=Ø;2.for each p∈P do3. for each q∈Pp do4. for each si∈Pp,q do5. if d(si,p)