论文拾萃 | BITS算法求解Equitable Coloring Promblem(附C++和java代码）

1前言

各位读者大家好，今天我们来讲讲equitable coloring promblem(ECP)。

2问题描述

图着色问题（Graph Coloring Problem, GCP）又称着色问题，是最著名的NP-完全问题之一。 数学定义：给定一个无向图

G=(V,E)

，其中V为顶点集合，E为边集合，图着色问题即为将V分为k个颜色组

{V_1,V_2,...,V_k}

，每个组形成一个独立集，即其中没有相邻的顶点。经典的GCP问题就是希望获得最小的k值。

图的k-着色判定问题——给定无向连通图G和k种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?

正如上图，将11个顶点着三种颜色，相连的顶点需要异色，故左图中存在一个冲突“1-2”，当执行一系列邻域动作后，右图达到零冲突的状态，相连的顶点都为异色，代表我们解决了k=3的情况。

而ECP问题在此基础上又新加入一个约束条件the equity constraint，即

||V_i|-|V_j||≤1,∀i≠j.

换句话说，就是在满足零冲突的GCP问题上的同时确保划分出来的每个独立集大小相差不超过一。

ECP问题有较为广泛的应用领域，例如垃圾收集、分区和负载平衡以及调度问题等。

举个小例子，假设现在必须将一组任务分配给一些工人，这些任务之间可能会相互冲突，这意味着它们不应该分配给同一工人。通过构建一个代表每个任务的顶点和代表冲突任务对的边的图，对问题进行建模。工人用不同的颜色表示。然后，为了使此图着色问题用来表示将一组任务有效分配给工人，必须将相同数量的任务分配给每个工人。又因为任务数可能不能被工人数整除时，所以可以要求分配给两个任意工人的任务数不能相差超过一个。这称为the equity constraint，由此产生的问题称为ECP问题。

3解决步骤

对于n个顶点不能从头试下去，分n,n-1,...个独立集慢慢试，遍历最后得到最合适的K值。

故我们首先采用二分法查找得到一个适当的K值范围，即一个较好的初始解，在采用迭代禁忌搜索(ITS)来找寻零冲突的集合划分方法，回溯就体现在调整K值为合适的值，固定常数m，逐渐尝试K~K-m，若找到更好的，就更新K值，重新回溯。

而本论文创新点就在于不像之前论文尝试到k个集合，当得不到满足要求的解，就返回k 1作为最终的最优解，而是再向前回溯m个，因为当加入the equity constraint后，极有可能k-1反而比k更容易得到合理解。

而算法整体贯穿始终的就是始终满足the equity constraint，找寻零冲突的集合划分方法。

对应每一个k，其解空间为

故BITS算法搜索的整个解空间即可描述为

评价函数

即为冲突数，可以用数学语言描述如下

4邻域动作

现有一种存在冲突（即

f≠0

）的集合划分方式

s={V_1,V_2,...,V_k}

，存在两种邻域动作，the constrained OneMove operator和the constrained Swap operator。

OneMove

< v,V_i,V_j >

表示顶点v在满足the equity constraint的条件下从

V_i

移动到

V_j

，

s⊕< v,V_i,V_j >

则表示新的解，其中

C(s)

表示满足下述条件的顶点集合：存在至少一个同色的邻接顶点。

如图(a)中，冲突顶点集合可以表示为

C(s)={1,8,9,10}

，邻域动作即

< 8,V_1,V_3 >

，之后

C(s)={7,8,9,10}

。

而

|V_i|>[frac{n}{k}],|V_j|<[frac{n}{k}]

这个条件则确保了始终满足the equity constraint。值得一提的是，若顶点均分时，则此邻域为空，这里读者不妨自己想想。

时间复杂度为

O(|C(s)×k|)

。

Swap

选取两个不同颜色集合的顶点

u,v

，至少其中之一是存在冲突的，

Swap(v,u)

交换两个顶点得到新解。

如图(a)中，冲突顶点集合可以表示为

C(s)={1,8,9,10}

，邻域动作即

Swap(5,9)

，之后

C(s)={1,8,3,9}

。

时间复杂度为

O(|C(s)×n|)

。

5Fast Neighborhood Evaluation Technique

敲黑板，重点来了。

为了快速计算目标函数

的改变值

Δf

，我们首先用矩阵

M[v][q](1≤v≤n,1≤q≤k)

表示顶点v的邻接顶点中为颜色q的顶点数。

P(u)

代表顶点u的颜色，

δ_1(x,y)

定义如下：

OneMove

Δ_f( < v,V_i,V_j >)=M[v][V_j]-M[v][V_i]

显而易见，但莫要忘了要更新矩阵。

接着用上面的“小栗子”展示下，显而易见

Δ_f=0

，那么在让我们用公式验证下，首先顶点8的邻接顶点在

V_1

中有1个，在

V_3

中有1个。

Δ_f(< 8,V_1,V_3 >)=M[8][V_3]-M[8][V_1]=1-1=0

Swap

Δ_f(Swap(u,v))=(M[v][P(u)]-M[v][P(v)]) (M[u][P(v)]-M[u][P(u)])-2δ_2(v,u)

其中

δ_2(v,u)=1

当顶点u,v相连，否则为0.

同样

Δ_f=0

，用公式验证下，

Δ_f(Swap(5,9))=(M[9][P(5)]-M[9][P(9)]) (M[5][P(9)]-M[5][P(5)])-2δ_2(9,5)=(1-1) (0-0)-2*0=0

这里部分读者可能会在

-2δ_2(v,u)

处卡壳一下，不妨先自己想想，

现在奉上小编的拙见，

或者可以将the constrained Swap operator理解为连续进行两次the constrained OneMove operator。

懂了吗，最后送给坚持看完的小伙伴们来自蔡元培的肯定！

欲下载本文相关代码，请移步留言区

参考文献：

【1】Xiangjing Lai, Jin-Kao Hao, Fred Glover "Backtracking Based Iterated Tabu Search for Equitable Coloring"，Engineering Applications of Artificial Intelligence, Volume 46, Issue PA, November 2015, pp 269–278.

【2】Méndez-Díaz I., Nasini G., Severín D., 2014, A tabu search heuristic for the equitable coloring problem. Lecture Notes in Computer Science pp. 347–358.

-The End-

evaluation swap 集合

0 人点赞