最大截問題CC改進(jìn)算法研究

強(qiáng)敏

(安徽財(cái)貿(mào)職業(yè)學(xué)院，安徽 合肥 230601）

最大截問題CC改進(jìn)算法研究

強(qiáng)敏

(安徽財(cái)貿(mào)職業(yè)學(xué)院，安徽 合肥 230601）

利用CC算法求解最大截問題，客觀上避免了最終解與初始邊的兩個(gè)端點(diǎn)著色有關(guān)。但是整體算法只有兩種顏色，在計(jì)算過程中，如果出現(xiàn)兩端點(diǎn)均未著色的情況，只有隨機(jī)選取，針對(duì)這種情況，引入了對(duì)立顏色的概念，用多組顏色進(jìn)行著色，并通過變異效果的累加來尋找最大截。

最大截；對(duì)立顏色；變異效果

最大割問題是屬于圖論問題，它是最困難的組合優(yōu)化問題之一，是NP完全的(NP-complete）。然而，它的逆問題(最小割）得到了廣泛的研究[1-2]，利用網(wǎng)絡(luò)流技術(shù)在多項(xiàng)式時(shí)間是可解的[3]。最大割已經(jīng)應(yīng)用在許多領(lǐng)域，包括超大規(guī)模集成(VISI）電路設(shè)計(jì)[4-5]，統(tǒng)計(jì)物理學(xué)[6]，以及其他方面[7-8]。

1 最大截問題及CC算法

設(shè)G=(V，E）是一個(gè)賦權(quán)無向圖，把頂點(diǎn)集V分為2個(gè)子集V0和V1(V1=VV0），稱端點(diǎn)分別在V0和V1中的邊的集合為賦權(quán)無向圖G的一個(gè)截，記作δ(V0，V1），δ(V0，V1）?E。設(shè)u，v∈V，以w(u，v）表示邊(u，v）的權(quán)。最大截問題的模型及約束如下：

式(1）、(2）要求找出一個(gè)最優(yōu)的分劃，使分劃中的邊的權(quán)和最大，且同一條邊僅允許穿越一次。

CC算法描述如下：

step1：找出G中權(quán)值最大的邊，設(shè)此邊為(u，v），將(u，v）置入集合δ；

step2：從u，v中任選一頂點(diǎn)著紅色，而另一頂點(diǎn)著白色，為了方便討論，假定u著紅色，而v著白色；

step3：檢查G有無未著色的頂點(diǎn)，若有，找出Gδ中權(quán)值最大的邊，轉(zhuǎn)step4，否則，stop；

step4：若該邊其中的一個(gè)端點(diǎn)已著色，則另一端點(diǎn)著不同的顏色，并將該邊置入集合δ，轉(zhuǎn)step3，若兩端點(diǎn)均未著色，可任選顏色，并將該邊置入集合δ，轉(zhuǎn)step3。

根據(jù)CC算法，所有紅色頂點(diǎn)構(gòu)成集合V0，所有白色頂點(diǎn)構(gòu)成集合V1，端點(diǎn)為不同顏色的邊集即為所求的分劃。然而算法step4的任選顏色使目標(biāo)函數(shù)值可能差別很大。

例1：有7個(gè)頂點(diǎn)，12條邊組成的賦權(quán)無向圖，各邊權(quán)值如圖1所示意。

依據(jù)CC算法，計(jì)算過程如下：

1）選擇權(quán)值最大的邊(v5，v6），假定v5著紅色，v6著白色，更新δ；

2）在Gδ中選擇權(quán)值最大的邊(v4，v5），v4著白色，更新δ；

3）在Gδ中權(quán)值最大的邊為(v1，v2），v1著白色，v2著紅色，更新δ；

4）在Gδ中權(quán)值最大的邊為(v4，v7），v7著紅色，更新δ；

5）在Gδ中權(quán)值最大的邊為(v4，v3），v3著紅色，更新δ。

由以上5步，計(jì)算截值為73，計(jì)算過程3）中，顏色是隨機(jī)選取的，枚舉另外一種顏色選擇，過程如下：

6）在Gδ中權(quán)值最大的邊為(v1，v2），v1著紅色，v2著白色，更新δ；

7）在Gδ中權(quán)值最大的邊為(v4，v7），v7著紅色，更新δ；

8）在Gδ中權(quán)值最大的邊為(v4，v3），v3著紅色，更新δ。

計(jì)算最大截值為84，顏色的隨機(jī)著色可能導(dǎo)致所求的截與最大截失之交臂，為確保計(jì)算出最大截，須枚舉可能的顏色選擇。

2 CC改進(jìn)算法

針對(duì)CC算法不能一次逼近最大截，需要反復(fù)試算，在試算的過程中，往往會(huì)重復(fù)計(jì)算一些邊的權(quán)，計(jì)算量較大，如果能只計(jì)算不同邊的權(quán)，則會(huì)減少計(jì)算量。為此引入一些概念。

1、對(duì)立顏色(A1，B1），A1的對(duì)立顏色就是B1，反之也是一樣。

2、變異操作就是某一對(duì)立顏色用另一對(duì)立顏色的兩種顏色表示的操作過程，變異規(guī)則：

①變異操作具有普遍性，對(duì)立顏色標(biāo)記的全部頂點(diǎn)必須同時(shí)變異，不可遺漏。

②變異操作具有同色傳遞性，如2個(gè)頂點(diǎn)v1，v2是同色(A1），變異到另一對(duì)立顏色(A2，B2），假設(shè)v1顏色已經(jīng)變異成A2，v2顏色也只能變異成A2。

③變異操作具有異色對(duì)立性，如2個(gè)頂點(diǎn)v1，v2顏色為(A1，B1），若v1已經(jīng)變異成A1色，v2只能變異成A2色。

圖1中，假設(shè)(A1，B1）是一對(duì)立顏色，涉及的頂點(diǎn)為v2、v3、v4、v7，其中v2、v3著A1色，v4、v7著B1色，(A2，B2）為另一對(duì)立顏色組，涉及的頂點(diǎn)有v1、v5、v6，其中v1、v6著A2色，v5著B2色。

3、變異效果衡量變異操作后截的變化。

假設(shè)對(duì)立顏色由(A1，B1）變異到(A2，B2）：

若A1色變異為A2色，B1色變異為B2色，變異操作引起的變化為截中增加了一條邊(v1，v7），變異效果記為6；

若A色變異為B2色，B色變異為A2色，變異操作引起的新的截邊有(v2，v1），(v7，v5），(v4，v5），變異效果12+9+13=34。

根據(jù)相關(guān)概念的定義，設(shè)計(jì)CC改進(jìn)算法步驟如下：

step1：找出G中權(quán)值最大的邊，設(shè)此邊為(u，v），將(u，v）置入集合δ，i=1；

step2：從u，v中任選一頂點(diǎn)著Ai，而另一頂點(diǎn)著Bi；

step3：檢查G有無未著色的頂點(diǎn)，若有，找出Gδ中權(quán)值最大的邊，轉(zhuǎn)step4，否則，stop；

step4：若該邊其中的一個(gè)端點(diǎn)已著色，則另一端點(diǎn)只需著對(duì)立顏色即可，并將該邊置入集合δ，step3；若兩端點(diǎn)均未著色，i=i+1，兩端點(diǎn)分別著顏色Ai+1或Bi+1，并將該邊置入集合δ，step3；

step5：如所有頂點(diǎn)均已著色，轉(zhuǎn)step6；

step6：依據(jù)變異公式計(jì)算變異效果，假設(shè)最終圖中有k組對(duì)立顏色，首先計(jì)算第k組顏色變色到k-1組顏色的變異效果，變異效果的計(jì)算如下：

如果Ak=Ak-1，則Bk=Bk-1，則：

如果Ak=Bk-1，則Bk=Ak-1，則：

式(3）、(4）中：

直至k=1(G中只剩最后兩種顏色），轉(zhuǎn)step7。

step7：計(jì)算從第k組對(duì)立顏色變異到第1組時(shí)的變異效果之和，如表1。變異權(quán)和最大的即為所求的分劃(最大截），Stop。

3 算例

例2：假設(shè)圖G有10個(gè)頂點(diǎn)，20條邊，邊上權(quán)數(shù)如圖2(1）。

依據(jù)CC改進(jìn)算法依據(jù)從圖2中找出權(quán)值最大的邊(v1，v3），將其置入δ，引入第1級(jí)對(duì)立顏色(A1，B1），可令v1著A1色，v3著B1色；G有未著色的頂點(diǎn)，找出Gδ中權(quán)值最大的邊(v2，v5），將其置入δ，兩端點(diǎn)v2和v5均未著色，引入2級(jí)對(duì)立顏色組(A2，B2），令v2著A2色，v5著B2色；依次著色，令v6著A3色，v7著B3色，v8著A4色，v10著B4色；在邊(v5，v9）中，端點(diǎn)v5已著B2色，則v9著B2的對(duì)立色A2色，v4著B4的對(duì)立色A4色；所有頂點(diǎn)均已著色。有六條邊(v1，v3）、(v2，v5）、(v6，v7）、(v8，v10)、(v8，v10）、(v5，v9）、(v4，v10）肯定是截邊，權(quán)值為85，

從4級(jí)對(duì)立顏色組(A4，B4）開始，計(jì)算4級(jí)頂點(diǎn)顏色變異到3級(jí)頂點(diǎn)顏色組(A3，B3）的變異效果，變異方法有兩種，一種是A4色頂點(diǎn)變成A3色，B4色頂點(diǎn)變成B3色，另一種是A4色頂點(diǎn)變成B3色，同時(shí)B4色頂點(diǎn)變成色A3，逐級(jí)計(jì)算頂點(diǎn)顏色變異效果，如表2所示。

從表2可知，圖2的最大截為130。與CC算法相比，避免了枚舉顏色選擇，重復(fù)計(jì)算的問題。

4 結(jié)論

CC算法中，顏色的隨機(jī)著色可能導(dǎo)致所求截與最大截失之交臂，為保證計(jì)算的準(zhǔn)確性，須枚舉可能的顏色選擇。針對(duì)這一問題，本文建立了對(duì)立顏色的概念，克服了原算法中只有兩種顏色，隨機(jī)選取的缺點(diǎn)，引入變異操作和變異效果計(jì)算方法，確保了不同截差異邊的完備性，通過求解變異效果，避免了重復(fù)計(jì)算，大大的減少了計(jì)算量。

[1]張憲超，講賀，陳國(guó)良.節(jié)點(diǎn)和邊都有容量的有向平面網(wǎng)絡(luò)中的最小截和最大流[J].計(jì)算機(jī)學(xué)報(bào)，2006，（4）∶544-551.

[2]張憲超，萬穎瑜，陳國(guó)良.一類實(shí)際網(wǎng)絡(luò)中的最小截算法[J].軟件學(xué)報(bào)，2003，（5）∶885-890.

[3]Barahona，F(xiàn).，Grotschel，M.，Junger M.&Reinelt，G.An Application of Combinatorial Ooptimization to Statistical Physics and Circuit Layout Design[J].Operation Research，1998，（36）∶493-513.

[4]Chang，K.C.&Du，D.Z.Efficient Algorithms for Layer Assignment Problems[J].IEEE Transactions on Computer-Aided Design，1987，（6）∶67-78.

[5]Festa，P.，Resende，M.G.C.&Ribeiro，C.C.Randomized Heuristics for MAX-CUT Problem[J].Optimization Methods and Software，2002，（7）∶1033-1058.

[6]Ahuja，R.K.，Magnanti，T.L.&Orlin，J.B.Network Flows∶Theory，Algorithms，and Applications[M].1993，prentice hall.

[7]Pinter，R.Y.Optimal Layer Assignment for Interconnect[J].Journal of VISI Computational Systems，1984，（1）∶123-137.

[8]Hager，W.W.&Krylyuk，Y.Graph Portioning and Continuous Quadratic Programming[J].SIAM Journal on Discrete Mathematics，1999，（12）∶500-523.

責(zé)任編輯：陳 侃

O243

A

1672-2868（2015）06-0021-04

2015-09-18

強(qiáng)敏(1980-），女，安徽固鎮(zhèn)人。安徽財(cái)貿(mào)職業(yè)學(xué)院，講師。研究方向：連鎖經(jīng)營(yíng)管理。