最大截问题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-），女，安徽固镇人。安徽财贸职业学院，讲师。研究方向：连锁经营管理。