限制版本瓶頸斯坦納樹(shù)問(wèn)題算法研究.pdf

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

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

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

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

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