反瓶頸Steiner樹問題.pdf

1、本文主要研究反瓶頸steiner樹問題，Steiner樹問題是組合最優(yōu)化的重要組成部分。Steiner樹的一系列問題來源于生活的實(shí)踐，因此越來越多的人關(guān)注這個(gè)問題。Steiner樹問題是網(wǎng)絡(luò)設(shè)計(jì)的一個(gè)重要研究?jī)?nèi)容，它及與它相關(guān)的問題在油氣管線鋪設(shè)、電力電纜架設(shè)、通訊網(wǎng)絡(luò)設(shè)計(jì)等領(lǐng)域有廣泛應(yīng)用。當(dāng)要求steiner樹中最大邊最小時(shí)，這就是瓶頸steiner樹問題，瓶頸steiner樹問題已經(jīng)有很多重要的結(jié)果，并有非常廣泛的應(yīng)用。近幾年來，人

2、們開始轉(zhuǎn)向反組合最優(yōu)化的研究，它的興起來源于道路設(shè)計(jì)。隨著對(duì)反問題的深入研究，反問題有了更廣泛的應(yīng)用。
　　 反瓶頸steiner樹問題是給定一個(gè)可行解，修改邊權(quán)使其成為瓶頸steiner樹問題的最優(yōu)解，并在要求的范數(shù)下邊權(quán)的修改費(fèi)用最小。若瓶頸steiner樹有多項(xiàng)式算法，反瓶頸steiner樹也有多項(xiàng)式算法。
　　 L1范數(shù)下，研究目標(biāo)為定值的反瓶頸steiner樹問題，將定值擴(kuò)展到任意值給出l1范數(shù)下的反瓶頸ste

3、iner樹問題，給出多項(xiàng)式時(shí)間算法。 L∞范數(shù)下，研究目標(biāo)為定值的反瓶頸steiner樹問題，將定值擴(kuò)展到任意值給出l∞范數(shù)下的反瓶頸steiner樹問題，給出算法，算法的時(shí)間復(fù)雜性歸結(jié)為求瓶頸切的時(shí)間復(fù)雜性。Hamming距離下，討論最優(yōu)目標(biāo)值的范圍，研究目標(biāo)為定值的反瓶頸steiner樹問題，將定值擴(kuò)展到任意值給出Hamming距離下的反瓶頸steiner樹問題，給出多項(xiàng)式時(shí)間算法。
　　 在本文中，通過對(duì)反瓶頸steine