徐 弈, 陳 瑩

(1.西安理工大學(xué) 經(jīng)濟與管理學(xué)院,陜西 西安 710054; 2.西安交通大學(xué) 管理學(xué)院,陜西 西安 710049)

0 引言

中心選址問題(Center problem)[1,2]與中位選址問題(Median problem)[3,4]一直是選址問題中的研究熱點與難點。中心選址問題可以等價于求解最小最大問題,以歐氏距離下的平面點集k中心選址問題為例,其選址目標(biāo)為尋找k個選址設(shè)施的位置,要求點集中每個點到這k個選址設(shè)施的最近距離的最大值最小[5,6]。記P為平面上含有n個點{a1,a2,…,an}的點集,d(x,y)為平面上任意兩點{x,y}的歐氏距離,所要尋找的k個選址設(shè)施為S={s1,s2,…,sk},則中心選址問題優(yōu)化模型如下:

直觀地,k中心選址問題等價于求解k個全等的圓覆蓋整個點集P,并且要求這些圓的半徑最小，而最優(yōu)解對應(yīng)的k個圓心即為設(shè)施的選址位置。

而對中位選址問題而言,該問題所對應(yīng)的幾何結(jié)構(gòu)則沒有中心選址問題那么直觀。仍舊以歐式距離下的平面點集k中位選址問題為例,其選址目標(biāo)為尋找k個選址設(shè)施的位置,要求點集中每個點到這k個選址設(shè)施的最近距離和最小,對應(yīng)選址問題優(yōu)化模型如下:

無論是k中心選址問題還是k中位選址問題,都已經(jīng)被證明問題是NP難的[7],故很難給出最優(yōu)解,因此學(xué)者往往考慮如下幾個問題:針對這兩個問題的近似算法或者啟發(fā)式算法[8,9];在某些特殊距離或者特殊網(wǎng)絡(luò)結(jié)構(gòu)下的中心或k中位選址問題[10];考慮當(dāng)k的值比較小時的中心或中位選址問題的最優(yōu)算法[11];以及考慮k中心或中位選址問題的衍生問題,例如要求k個設(shè)施之間的距離滿足某些關(guān)系,或者k個設(shè)施的位置帶有一定的約束(限制在某些點處或者某些區(qū)域內(nèi))[12,13]。

本文考慮平面內(nèi)歐氏距離條件下的2中位選址問題的衍生問題。2中心或中位選址問題直到現(xiàn)在還有許多學(xué)者在研究,2017年,Tan給出了2中心選址問題的O(nlog2n)時間算法[14],該算法的復(fù)雜性已經(jīng)非常接近該問題的下界O(nlogn),這改進(jìn)了1999年Chan設(shè)計的并行計算算法[15]。而最新的與2中心選址問題相關(guān)的文獻(xiàn)是由Xu等人提出的最小最大2中心選址問題,該問題不僅要求兩個圓的半徑盡可能小,同時要求兩個圓心之間的距離也不能超過兩個圓的半徑。2019年他們給出該問題的混合(兩個圓心均在點集內(nèi)部)與離散(只要求一個圓心在點集內(nèi)部)的情況分別可以在O(n2log2n)和O(n2logn)的時間進(jìn)行求解[16]。針對連續(xù)的情況(即對兩個圓的圓心位置沒有限制),Bhattacharya等人于2022年給出O(n2logn)時間的最優(yōu)算法[17]。

1 研究動機與問題

1.1 研究動機

在網(wǎng)絡(luò)中,雙會議服務(wù)器選址問題的實際背景可以看成在平面點集結(jié)構(gòu)中,尋找兩個服務(wù)器,要求其他終端均連接這兩個服務(wù)器中的一個,最終形成一個網(wǎng)絡(luò)結(jié)構(gòu)(樹結(jié)構(gòu)),而尋找目的是使得這個網(wǎng)絡(luò)的花費最小。此時網(wǎng)絡(luò)的花費為網(wǎng)絡(luò)中所有兩點的網(wǎng)絡(luò)距離和(不包含兩服務(wù)器)。雙會議服務(wù)器選址問題不僅需要考慮如何尋找兩個服務(wù)器位置,同時還需要考慮如何將點集中的點與這兩個服務(wù)器相連接。如果不限制這兩個服務(wù)器的位置,那么該問題與Weber問題一樣[18],只能通過設(shè)計啟發(fā)式算法或者近似算法進(jìn)行求解,不存在最優(yōu)算法。類似地,如果要求這兩個服務(wù)器在點集內(nèi)部,則可以證明該問題是多項式時間內(nèi)可解的。本文的主要工作就是對這種情況,通過討論其幾何結(jié)構(gòu),給出多項式時間的算法。

1.2 問題描述

首先介紹只針對一個服務(wù)器(單服務(wù)器)進(jìn)行選址的情況。記P為平面上含有n個點{a1,a2,…,an}的點集,每點的平面坐標(biāo)對應(yīng)記為(aix,aiy)(i=1,2,…,n),單會議服務(wù)器選址目標(biāo)為p,其平面坐標(biāo)對應(yīng)記為(px,py),則單會議服務(wù)器選址問題定義如下:

問題1單會議服務(wù)器選址問題指最小化點集張成的一星樹上所有葉子之間的距離和。其中點集的一星樹是指由這n個點生成的一棵樹,并且滿足這n個點僅連接某一個點(不一定屬于P)。

如果要求p?P,該問題等價于著名的Weber問題并且可以證明該問題無法求得最優(yōu)解[18]。如果要求p∈P,則可以通過遍歷的方法求解,其時間復(fù)雜性為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,此時可以定義雙會議服務(wù)器選址問題如下:

問題2雙會議服務(wù)器選址問題指最小化點集二星樹上所有兩點之間的距離和。

與雙會議服務(wù)器選址問題強相關(guān)的是2中心選址問題與最小直徑樹問題[19～21]。其中2中心選址問題用兩個圓覆蓋某個平面點集,并且要求兩個圓的半徑都盡可能小; 而最小直徑樹問題是指求解給定點集的一個生成樹,使得該樹的直徑最小,其中樹的直徑是指這棵樹上最遠(yuǎn)兩點之間的距離。對于該問題曾證明,一定存在一棵一星樹或者二星樹是該點集的最小直徑樹[19]。而雙會議服務(wù)器選址問題可以看成是二星最小直徑樹的衍生,它不僅僅要求這棵樹最遠(yuǎn)兩點之間的距離最小,同時要求這棵樹所有葉子之間的距離總和最小。

本文結(jié)構(gòu)如下,第2節(jié)給出最優(yōu)解所對應(yīng)的幾何結(jié)構(gòu),以及該幾何結(jié)構(gòu)的構(gòu)造思路,第3節(jié)給出最優(yōu)解的求解算法并分析其算法復(fù)雜性,第4節(jié)給出結(jié)論與展望。

2 幾何結(jié)構(gòu)

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的半平面內(nèi)所包含的點為集合S1={u1,u2,…,uh1},其點的個數(shù)為h1,記包含點q的半平面H2內(nèi)所包含的點為集合S2={v1,v2,…,vh2},個數(shù)為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,為了計算最優(yōu)解,需要以下引理。不失一般性,考慮k2≤h2≤h1≤k1的情況:

引理2如果k2≤h2≤h1≤k1,此時最優(yōu)解結(jié)構(gòu)一定滿足:如果K1中有x′個點屬于S1,K2中有y′個點屬于S2,則一定有k1-x′≥k2-y′。

證明由于k1-h1=h2-k2,由假設(shè)K1中有x′個點屬于S1,K2中有y′個點屬于S2,則K1中剩余點一定屬于S2,K2中剩余點一定屬于S1,即h2-y′=k1-x′=k2-y′。假設(shè)k1-x′

綜上，得到最優(yōu)解結(jié)構(gòu)如下:

其中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}并給定兩個常數(shù)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時的最優(yōu)解

圖3 h1=5,h2=3,j=2,k1=2,k2=8時的最優(yōu)解

3 算法設(shè)計

定理2對給定包含n個點的點集P,雙會議服務(wù)器選址問題可以在O(n3logn)的時間內(nèi)求解。

4 結(jié)論與展望

本文考慮平面點集選址問題中的雙會議服務(wù)器選址問題,即尋找由該點集構(gòu)成的一棵二星樹,使得這棵樹上所有葉子之間的距離和最小。本文給出求解該問題的關(guān)鍵幾何結(jié)構(gòu)和最優(yōu)解算法設(shè)計,并給出時間復(fù)雜性為O(n3logn)的最優(yōu)時間算法。雙會議服務(wù)器選址問題以看成是2中位問題的衍生問題。目前,雙會議服務(wù)器選址問題和最小直徑樹問題還沒有學(xué)者給出時間復(fù)雜性小于O(n3)的最優(yōu)時間算法,尋找這兩個問題更深入的最優(yōu)幾何結(jié)構(gòu)和性質(zhì)將是改進(jìn)這兩問題算法復(fù)雜性的研究重點。

Algorithm 1 雙會議服務(wù)器選址問題算法設(shè)計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)