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

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

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

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