限制版本瓶頸斯坦納樹問題算法研究.pdf_第1頁
已閱讀1頁,還剩44頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、傳統(tǒng)Steiner樹問題在VLSI設(shè)計、無線通訊網(wǎng)絡(luò)設(shè)計和生命演化樹重建等領(lǐng)域的新應(yīng)用被逐漸發(fā)現(xiàn)和深入研究,但是這些應(yīng)用通常需要對傳統(tǒng)Steiner樹問題作某些修改,因此研究Steiner樹問題的變種問題成為近些年來的熱點。這些變種問題包括瓶頸Steiner樹問題和在邊長限定情況下求最小化Steiner節(jié)點個數(shù)問題。
  本文研究的主要內(nèi)容是瓶頸Steiner樹問題,定義如下:給定一個必需節(jié)點集合,它的大小為n,我們至多使用k個S

2、teiner節(jié)點,來構(gòu)建一棵Steiner樹,使得在這棵樹中最長邊的長度相對其它在同樣條件下構(gòu)造的Steiner樹的最長邊是最短的。
  在對瓶頸Steiner樹問題的研究中,L.Wang和D.-Z Du證明除非P=NP,否則在多項式時間內(nèi)這個問題在網(wǎng)格平面中不能被近似到2以內(nèi),在歐幾里得平面中不能被近似到2以內(nèi),然后他們僅利用在平面空間上節(jié)點之間距離的三角不等式性質(zhì),構(gòu)造了2-限制Steiner樹,得到了這個問題近似性能比為2的

3、適用于這兩個空間的多項式時間近似算法。
  Z. Li和D.-Z Du考慮了最優(yōu)解中一些節(jié)點之間的幾何關(guān)系,構(gòu)造出3-限制Steiner子樹,兩人分別得到了在歐幾里得平面上近似性能比為1.866+ε和3+ε的近似算法,這里ε為任意正數(shù),但這仍與不可近似結(jié)果2有較大的差距。
  隨后Z. Li等考慮可以通過施加限制條件先簡化問題再進(jìn)行求解,然后提出了該問題的限制版本,也就是沒有一條邊連接任意兩個Steiner節(jié)點,根據(jù)2-限制

4、Steiner樹和3-限制Steiner樹的存在性,分別證明了近似性能比3和2的存在性,并且完成了兩個近似算法的設(shè)計。
  本文提出了兩種限制情況:(1)在最優(yōu)解中只有度等于2的Steiner節(jié)點才能夠相互鄰接,(2)在最優(yōu)解中只有度大于等于3的Steiner節(jié)點不能夠鄰接。這兩種限制情況相對于Z. Li等提出的版本更加平凡,同時證明了第二種限制情況相對于第一種更加平凡,更加接近原始的瓶頸Steiner樹問題。
  我們通過

5、一個限制版本的平面節(jié)點覆蓋問題證明了這兩個新的限制問題是NP-hard。隨后對于第一種限制情況的問題,我們證明了近似性能比3和2的存在性,并分別給出多項式時間3近似算法和多項式時間隨機2+ε近似算法,最后借助于二叉樹最大堆和二分搜索技術(shù),分別對這兩個近似算法的運行時間復(fù)雜度進(jìn)行了改進(jìn);對于第二種限制情況的問題,我們也證明了近似性能比3和2的存在性,并且證明了適用于第一種限制情況的確定型近似算法也適用于第二種限制情況,在分析兩種限制情況的

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論