最大截問題CC改進算法研究

強敏

(安徽財貿職業學院，安徽 合肥 230601）

最大截問題CC改進算法研究

強敏

(安徽財貿職業學院，安徽 合肥 230601）

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

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

最大割問題是屬于圖論問題，它是最困難的組合優化問題之一，是NP完全的(NP-complete）。然而，它的逆問題(最小割）得到了廣泛的研究[1-2]，利用網絡流技術在多項式時間是可解的[3]。最大割已經應用在許多領域，包括超大規模集成(VISI）電路設計[4-5]，統計物理學[6]，以及其他方面[7-8]。

1 最大截問題及CC算法

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

式(1）、(2）要求找出一個最優的分劃，使分劃中的邊的權和最大，且同一條邊僅允許穿越一次。

CC算法描述如下：

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

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

step3：檢查G有無未著色的頂點，若有，找出Gδ中權值最大的邊，轉step4，否則，stop；

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

根據CC算法，所有紅色頂點構成集合V0，所有白色頂點構成集合V1，端點為不同顏色的邊集即為所求的分劃。然而算法step4的任選顏色使目標函數值可能差別很大。

例1：有7個頂點，12條邊組成的賦權無向圖，各邊權值如圖1所示意。

依據CC算法，計算過程如下：

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

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

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

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

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

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

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

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

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

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

2 CC改進算法

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

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

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

①變異操作具有普遍性，對立顏色標記的全部頂點必須同時變異，不可遺漏。

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

③變異操作具有異色對立性，如2個頂點v1，v2顏色為(A1，B1），若v1已經變異成A1色，v2只能變異成A2色。

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

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

假設對立顏色由(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。

根據相關概念的定義，設計CC改進算法步驟如下：

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

step2：從u，v中任選一頂點著Ai，而另一頂點著Bi；

step3：檢查G有無未著色的頂點，若有，找出Gδ中權值最大的邊，轉step4，否則，stop；

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

step5：如所有頂點均已著色，轉step6；

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

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

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

式(3）、(4）中：

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

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

3 算例

例2：假設圖G有10個頂點，20條邊，邊上權數如圖2(1）。

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

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

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

4 結論

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

[1]張憲超，講賀，陳國良.節點和邊都有容量的有向平面網絡中的最小截和最大流[J].計算機學報，2006，（4）∶544-551.

[2]張憲超，萬穎瑜，陳國良.一類實際網絡中的最小截算法[J].軟件學報，2003，（5）∶885-890.

[3]Barahona，F.，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.

責任編輯：陳 侃

O243

A

1672-2868（2015）06-0021-04

2015-09-18

強敏(1980-），女，安徽固鎮人。安徽財貿職業學院，講師。研究方向：連鎖經營管理。