強(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ī)選取，針對這種情況，引入了對立顏色的概念，用多組顏色進(jìn)行著色，并通過變異效果的累加來尋找最大截。

最大截；對立顏色；變異效果

最大割問題是屬于圖論問題，它是最困難的組合優(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)算法

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

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

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

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

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

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

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

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

假設(shè)對立顏色由(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)只需著對立顏色即可，并將該邊置入集合δ，step3；若兩端點(diǎn)均未著色，i=i+1，兩端點(diǎn)分別著顏色Ai+1或Bi+1，并將該邊置入集合δ，step3；

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

step6：依據(jù)變異公式計(jì)算變異效果，假設(shè)最終圖中有k組對立顏色，首先計(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組對立顏色變異到第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級對立顏色(A1，B1），可令v1著A1色，v3著B1色；G有未著色的頂點(diǎn)，找出Gδ中權(quán)值最大的邊(v2，v5），將其置入δ，兩端點(diǎn)v2和v5均未著色，引入2級對立顏色組(A2，B2），令v2著A2色，v5著B2色；依次著色，令v6著A3色，v7著B3色，v8著A4色，v10著B4色；在邊(v5，v9）中，端點(diǎn)v5已著B2色，則v9著B2的對立色A2色，v4著B4的對立色A4色；所有頂點(diǎn)均已著色。有六條邊(v1，v3）、(v2，v5）、(v6，v7）、(v8，v10)、(v8，v10）、(v5，v9）、(v4，v10）肯定是截邊，權(quán)值為85，

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

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

4 結(jié)論

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

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

[2]張憲超，萬穎瑜，陳國良.一類實(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)營管理。