• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      樹上具有懲罰費(fèi)用的限制性node multicut問題的近似算法

      2024-03-08 03:50:50楊惠娟段江梅楊子蘭
      關(guān)鍵詞:對偶限制性頂點(diǎn)

      楊惠娟,段江梅,楊子蘭

      (1.昭通學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,云南 昭通 657000; 2.麗江文化旅游學(xué)校信息學(xué)院,云南 麗江 674199)

      0 引言

      multicut問題是圖論與組合優(yōu)化中非常著名的問題,它具有邊和點(diǎn)兩種形式,點(diǎn)形式的multicut問題是指:給定賦權(quán)圖G=(V,E;w)及一個(gè)終端點(diǎn)對集合H?V×V,其中w:V→R+,求G的一個(gè)頂點(diǎn)子集D,使得H中的所有頂點(diǎn)對在G-D中不連通,目標(biāo)是使得D的權(quán)重盡可能小.

      限制性node multicut問題是點(diǎn)形式multicut問題的一類子問題,該問題要求所求的頂點(diǎn)子集中不允許有終端點(diǎn).GUO等[1]研究了完全圖、分裂圖、區(qū)間圖上的點(diǎn)multicut 問題,并證明了該問題限制在這三類特殊圖上時(shí)也是NP難問題.PAPADOPOULOS[2]證明了置換圖上的無限制性 node multicut問題是多項(xiàng)式可解的,且設(shè)計(jì)了時(shí)間復(fù)雜度為O(n3)的算法,其中n為圖的頂點(diǎn)數(shù).

      一般的multicut問題是要求所有頂點(diǎn)對被斷開,而有些頂點(diǎn)對在斷開時(shí)可能會出現(xiàn)選取的邊的權(quán)重很大的情況,這時(shí)需要考慮拒絕斷開這些頂點(diǎn)對,同時(shí)支付部分懲罰費(fèi)用,這就將multicut問題拓展到了具有懲罰費(fèi)用問題的層面.LIU等[6]將帶線性懲罰推廣到帶次模懲罰,引入了帶次模懲罰的樹上的多割問題,并且基于原始對偶方案給出了帶次模懲罰的樹上的多割問題的一個(gè)3-近似算法.HOU等[7]研究了樹上具有懲罰費(fèi)用的k-edge multicut問題,該問題推廣了樹上邊multicut問題,并運(yùn)用線性規(guī)劃理論和拉格朗日松弛技巧設(shè)計(jì)了近似值為(4+ε)的算法,其中ε為任意固定正數(shù).侯鑫[8]研究了樹上的k-獎(jiǎng)勵(lì)收集多割問題和樹上的P獎(jiǎng)勵(lì)收集多割問題,對于樹上k-獎(jiǎng)勵(lì)收集多割問題和樹上的P獎(jiǎng)勵(lì)收集多割問題,設(shè)計(jì)了求解其近似值為(4+ε)的算法,其中ε為任意固定正數(shù).侯晨菲[9]主要研究了與次模函數(shù)有關(guān)的樹上多割問題.這些文獻(xiàn)重點(diǎn)研究了不同類型的具有懲罰費(fèi)用的邊multicut 問題,但對于圖而言,要分離圖上的頂點(diǎn),可以去掉圖上的邊,也可以去掉圖上的頂點(diǎn),而這些文獻(xiàn)對于具有懲罰費(fèi)用的點(diǎn)multicut 問題的研究較少.本文提出具有懲罰費(fèi)用的限制性node multicut問題,為了得到很好的結(jié)果,將問題限制在樹上進(jìn)行研究.

      1 樹上具有懲罰費(fèi)用的限制性node multicut問題

      樹上具有懲罰費(fèi)用的限制性node multicut問題是指:給定頂點(diǎn)賦權(quán)樹T=(V,E;w)及頂點(diǎn)V的k個(gè)頂點(diǎn)對構(gòu)成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,且S中的每個(gè)終端點(diǎn)對{si,ti}都有一個(gè)非負(fù)的懲罰費(fèi)用pi,求T的一個(gè)頂點(diǎn)子集D,使得D滿足D中不含S中的點(diǎn)且對?i∈{1,2,…,k},{si,ti}在T[V-D]中不連通,其中T[V-D]表示T的由頂點(diǎn)集V-D導(dǎo)出的子圖.目標(biāo)是使D中頂點(diǎn)的權(quán)重之和與在T[V-D]中未斷開的頂點(diǎn)對的懲罰費(fèi)用之和最小.

      樹上限制性node multicut問題是指:給定頂點(diǎn)賦權(quán)的樹T=(V,E;w)及頂點(diǎn)V的k個(gè)頂點(diǎn)對構(gòu)成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,求T的一個(gè)頂點(diǎn)子集D,使得D滿足D中不含S中的點(diǎn)且對?i∈{1,2,…,k},{si,ti}在T[V-D]中不連通.目標(biāo)是使D中頂點(diǎn)的權(quán)重之和最小.

      S中的點(diǎn)稱為終端點(diǎn),若S中的點(diǎn)對{si,ti}的懲罰費(fèi)用非常大,超過斷開此點(diǎn)對所選非終端頂點(diǎn)的權(quán)重之和,此時(shí)只能斷開S中所有點(diǎn)對,則樹上具有懲罰費(fèi)用的限制性node multicut問題化為樹上限制性node multicut問題,因此該問題作為樹上限制性node multicut問題的推廣形式是NP完備的.

      下面介紹如何將樹上具有懲罰費(fèi)用的限制性node multicut問題歸約到樹上限制性node multicut問題,并利用線性規(guī)劃及對偶理論設(shè)計(jì)算法進(jìn)行求解.

      任給樹上具有懲罰費(fèi)用的限制性node multicut問題的一個(gè)實(shí)例I:給定頂點(diǎn)賦權(quán)的樹T=(V,E;w)及頂點(diǎn)V的k個(gè)頂點(diǎn)對構(gòu)成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,且S中的每個(gè)終端點(diǎn)對{si,ti}都有一個(gè)非負(fù)懲罰費(fèi)用pi,求T的一個(gè)頂點(diǎn)子集D,使得D滿足不含S中的點(diǎn)且對?i∈{1,2,…,k},{si,ti}在T[V-D]中不連通.目標(biāo)是使D中頂點(diǎn)的權(quán)重之和與在T[V-D]未斷開的頂點(diǎn)對的懲罰費(fèi)用之和最小.

      下面證明實(shí)例I與實(shí)例τ(I)的解是等價(jià)的,若D是實(shí)例I的解,在T[V-D]中未被斷開的頂點(diǎn)對要支付懲罰費(fèi)用,假設(shè)被懲罰的所有頂點(diǎn)對的下標(biāo)構(gòu)成的集合為N,即N={i|?pi∈T[V-D],si,ti∈pi, ?{si,ti}∈S},其中

      與實(shí)例I的目標(biāo)函數(shù)值一致.

      反之,若D′是實(shí)例τ(I)的解,即S′中所有頂點(diǎn)對在T′[V′-D′]中都不連通,令D=D′∩(V-S),D″=D′∩{t1″,t2″,…,tk″},則N={i|ti″∈D″},則D是實(shí)例I的解,下標(biāo)在N中的頂點(diǎn)對集合是在T[V-D]中未斷開的集合,此時(shí)實(shí)例I與實(shí)例τ(I)的目標(biāo)函數(shù)值一樣,因此根據(jù)上述描述任給樹上具有懲罰費(fèi)用的限制性node multicut問題的一個(gè)實(shí)例I都可以轉(zhuǎn)化成樹上限制性node multicut問題的一個(gè)實(shí)例τ(I),它們的解可以相互轉(zhuǎn)換,且目標(biāo)函數(shù)值相同.

      下面介紹如何利用線性規(guī)劃的相關(guān)理論知識設(shè)計(jì)求解實(shí)例τ(I)的算法,并將算法求得的解轉(zhuǎn)化為實(shí)例I的解,并證明轉(zhuǎn)化回來的解的近似值.

      2 原始-對偶算法

      用0-1整數(shù)規(guī)劃來描述實(shí)例τ(I).

      對V′-S′中的每一個(gè)頂點(diǎn)引入布爾變量xv,用來表示頂點(diǎn)v是否在集合D′中,若v?D′,則令xv=0,若v∈D′,則令xv=1.P′i表示在樹T′中si到t′i之間的路,因?yàn)門′是樹,因此si到t′i之間的路是唯一的,此時(shí)得到實(shí)例τ(I)的0-1整數(shù)規(guī)劃,記為IP.

      因?yàn)檎麛?shù)規(guī)劃的求解是NP難的,因此對上述整數(shù)規(guī)劃進(jìn)行松弛,就得如下的線性規(guī)劃記為LP.

      算法的思想:從原始線性規(guī)劃的一個(gè)不可行解?v∈V′-S′,xv=0及對偶線性規(guī)劃的一個(gè)平凡可行解fi, ?i∈{1,2,…,k}開始,在每一次迭代過程中保證對偶線性規(guī)劃的解的可行性,然后逐步調(diào)整原始線性規(guī)劃的解和對偶線性規(guī)劃的解,使得原始線性規(guī)劃的解盡可能滿足可行性,而對偶規(guī)劃的解盡可能滿足最優(yōu)性,直到調(diào)整到原始線性規(guī)劃的解滿足可行性.

      算法具體步驟如下:

      輸出:斷開頂點(diǎn)對所選的非終端點(diǎn)構(gòu)成的集合D′

      步驟1 令fi=0, ?i∈{1,2,…,k},D′=?.

      步驟2 任取T′的一個(gè)頂點(diǎn)作為根節(jié)點(diǎn),假設(shè)為v0.

      步驟3 計(jì)算V′中每一個(gè)頂點(diǎn)的深度,即對?v∈V′(T′)計(jì)算頂點(diǎn)v的深度d(v),d(v)表示v到v0的唯一路上邊的數(shù)目.

      步驟4 將步驟3計(jì)算得到的所有頂點(diǎn)的深度d(v)從大到小進(jìn)行排序,d(vn)≥d(vn-1)≥…≥d(v0).

      輸出:fi,?i∈{1,2,…,k}及集合D′.

      若v∈D′,令xv=1,否則令xv=0,于是上述算法輸出的解xv,?v∈V′-S′及fi,?i∈{1,2,…,k}分別為松弛線性規(guī)劃和對偶規(guī)劃的可行解,于是得到如下結(jié)論:

      根據(jù)文獻(xiàn)[10]的性質(zhì)5得出上述原始線性規(guī)劃和對偶線性規(guī)劃的可行解,滿足的互補(bǔ)松弛條件是:

      (5)

      圖1 si0到的路及si到ti的路

      將上述算法求得的實(shí)例τ(I)的解D′,轉(zhuǎn)化成實(shí)例I的解,轉(zhuǎn)化方式為:令D=D′∩(V-S),D″=D′∩{t1″,t2″,…,tk″},則N={i|ti″∈D″}.于是得到如下定理.

      證明

      (6)

      (7)

      (8)

      (9)

      定理5令OPT,O′PT分別是實(shí)例I和實(shí)例τ(I)的最優(yōu)解的值,調(diào)用原始-對偶算法求解的實(shí)例τ(I)的解轉(zhuǎn)化成實(shí)例I的解,則所得的解的近似值為2.

      證明 算法求得的實(shí)例τ(I)的解為D′,轉(zhuǎn)化成實(shí)例I的解為D,N,其中,D為斷開終端點(diǎn)對所選的非終端點(diǎn)集合,N為在T-D中未斷開的頂點(diǎn)對的下標(biāo)構(gòu)成的集合,因此實(shí)例τ(I)的最優(yōu)解可以轉(zhuǎn)化成實(shí)例I的一個(gè)可行解,故O′PT≤OPT,于是,再由定理3和定理4得到:

      綜上所述,D中頂點(diǎn)的權(quán)重之和與在T[V-D]未斷開的頂點(diǎn)對的懲罰費(fèi)用之和小于等于最優(yōu)解的2倍,因此這樣求得的解D,N的近似值為2.

      3 結(jié)語

      本文研究了樹上具有懲罰費(fèi)用的限制性node multicut 問題,將該問題轉(zhuǎn)化成樹上限制性node multicut 問題,并利用線性規(guī)劃和對偶規(guī)劃的相關(guān)理論設(shè)計(jì)了近似值為2的算法.下一步將重點(diǎn)研究更多特殊圖上的具有懲罰費(fèi)用的限制性node multicut 問題及其各種推廣問題.

      猜你喜歡
      對偶限制性頂點(diǎn)
      過非等腰銳角三角形頂點(diǎn)和垂心的圓的性質(zhì)及應(yīng)用(下)
      因“限制性條件”而舍去的根
      關(guān)于頂點(diǎn)染色的一個(gè)猜想
      骨科手術(shù)術(shù)中限制性與開放性輸血的對比觀察
      髁限制性假體應(yīng)用于初次全膝關(guān)節(jié)置換的臨床療效
      對偶平行體與對偶Steiner點(diǎn)
      對偶均值積分的Marcus-Lopes不等式
      對偶Brunn-Minkowski不等式的逆
      論房屋承租人優(yōu)先購買權(quán)的限制性保護(hù)
      關(guān)于Hadamard矩陣的一類三元自對偶碼構(gòu)造
      沙坪坝区| 绵竹市| 横山县| 南丰县| 化州市| 黎城县| 绥阳县| 弥渡县| 孟村| 东光县| 杭锦旗| 芒康县| 冷水江市| 葵青区| 湖南省| 崇文区| 平塘县| 永济市| 太和县| 建阳市| 金门县| 望江县| 库伦旗| 海口市| 海南省| 辛集市| 左云县| 腾冲县| 通江县| 建昌县| 长治市| 罗江县| 灵宝市| 赤峰市| 探索| 万宁市| 苏尼特右旗| 绥中县| 沂源县| 泽库县| 申扎县|