設施選址問題的研究與應用.pdf

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

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

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