設(shè)施選址問題的研究與應(yīng)用.pdf

1、設(shè)施選址問題是一類被廣泛研究和應(yīng)用的優(yōu)化問題，在互聯(lián)網(wǎng)、分布式計算、數(shù)據(jù)挖掘和運籌規(guī)劃等領(lǐng)域有廣泛應(yīng)用，所以對設(shè)施選址問題各種形式的研究有著重要的實際意義。設(shè)施選址問題的一般形式是從一個對象集合中選擇若干對象作為設(shè)施來服務(wù)其它對象，優(yōu)化的目標(biāo)是服務(wù)費用最小，比如從一個局域網(wǎng)中選擇若干主機作為代理服務(wù)器使得其它主機通過代理服務(wù)器訪問外部網(wǎng)絡(luò)的時間盡量短。圍繞設(shè)施選擇問題的一些形式，本文開展了以下研究工作： 提出并研究了無向樹全覆蓋

2、問題及其應(yīng)用。該問題是已有的無向樹上1覆蓋問題的一個限定形式，也是已有的無向樹1中心問題的一個推廣形式。設(shè)計了一個時間復(fù)雜度為O(nlogn)的簡潔算法來解決該問題。這一算法可以用來解決樹形網(wǎng)絡(luò)的代理服務(wù)器和網(wǎng)頁緩存服務(wù)器的選擇問題。 改進了直線上p覆蓋問題的已有算法。該問題是設(shè)施選址問題中較早被研究的形式之一。改進算法利用高效的數(shù)據(jù)結(jié)構(gòu)和優(yōu)化技術(shù)將已有動態(tài)規(guī)劃算法的時間復(fù)雜度改進為O(nplogn)，空間復(fù)雜度改進為O(nlo

3、gn)，而原算法的時間復(fù)雜度和空間復(fù)雜度均為O(n2)。 提出并研究了無向樹上K節(jié)點子樹核心問題及其應(yīng)用。該問題是已有的無向樹p中心問題的一個限定形式，可以應(yīng)用于樹形網(wǎng)絡(luò)上的分布式數(shù)據(jù)庫數(shù)據(jù)副本最優(yōu)安置問題。設(shè)計了兩個不同的動態(tài)規(guī)劃算法來解決這一問題，一個具有編程實現(xiàn)簡單實用性強的特點，另一個具有時間復(fù)雜度低時間效率高的特點，兩個算法可分別適用于不同的應(yīng)用環(huán)境。 研究了無向樹1中心問題的動態(tài)形式。該問題需要在樹節(jié)點權(quán)值動