Page 64 - 《软件学报》2024年第6期

2640 软件学报 2024 年第 35 卷第 6 期

v ∈ V , 我们定义顶点的度为其邻居节点的权重和, 即
我们首先定义加权图 G(V,E,W) 的度, 对任意顶点
∑
v
d(v) = w(u) , 其中 N(v) 代表了顶点 的邻居节点集合, 由此我们定义顶点的优先度为:

u∈N(v)
r(v) = αd (v)+(1−α)w (v),
∗
∗
∗ ∗
其中, d (v),w (v) 为归一化后顶点的度与权重, α ∈ [0,1] 为参数.
我们按照变量的优先度顺序进行贪心着色, 算法 2 展示了 CMC-h 算法的具体过程. 算法的第 2 行, 我们首先对
问题进行理论下界分析, 并得到初始的着色方案, 只有在该方案不连续的情况下, 我们才会采用启发式方法进行着
色. 通常, 我们选择 α ∈ {0,0.5,1} 进行 3 次着色并选择最优结果, 我们将在第 4.3 节中进行详细论述. 算法的第 6 行,
我们计算了变量的优先度, 该优先度决定了顶点着色的顺序. 在这里我们对顶点的度与权重进行了归一化处理. 第
8–16 行代表了按照优先度顺序进行连续着色的过程. 与计算理论下界时有所不同, 由于无法通过完美消除序列快速
计算当前顶点的已着色情况, 因此我们在第 4 行构建了完整的干涉图. 其中, 构建的干涉图为加权图, 需要为每个顶
点赋予等于该顶点对应变量位宽的权重. 在第 11, 12 行需要每次重新计算顶点 的邻居节点 的已着色情况. 第 13, 14
行要求对同一顶点染多种连续的颜色, 而不是每个比特分别着色, 从而保证每个顶点的颜色集合均是连续的.
着色算法的时间复杂度为 O(|V|+|E|) , 排序算法的时间复杂度为 O(|V|log|V|) , 构建干涉图的时间复杂度为
2 2
O(|V| ) , 因此算法的整体复杂度仍然为 O(|V| ) .
算法 2. CMC-h 算法.

Input: 变量列表 V , 每个变量 v ∈ V 的位宽 W v 与活跃区间 I v ;
Output: 着色方案 Color .

1. function CMC −h(V,W,I)
2. L,Color,index ← LowerBound(V,W,I)
3. if ¬isContinue(Color) then
G(V,E,W) ← BuildInterferenceGraph(V,W,I)
4.
5. for α ∈ {0,0.5,1} do
∗
∗
6. r(v) = αd (v)+(1−α)w (v),∀v ∈ V
7. Sort(V,key ← lambda v : r(v),reversed ← True)

8. Color v ← ∅,∀v ∈ V
done ← ∅
9.
10. for v ∈ V do
freeColor ← True ,∀i ∈ [0, M)∩N
11.
i
12. freeColor i ← False,∀i ∈ index u ,u ∈ N(v)∩done
13. j ← min{k|freeColor s = True,∀s ∈ [k,k +W v )∩N}
14. Color v ← Color v ∪([j, j+W v )∩N)
15. done ← done∪{v}
16. end for
17. if max(Color) = L then
18. return Color
19. end if
20. end for
21. end if
22. return Color
23. end function