带权无向图节点着色：求最小化加权距离评分的近似算法

输入说明 #

无向带权图（边列表格式） #

输入为节点间的边及对应权重，示例：

A B 10
A C 9
A D 2
B C 1

颜色分配配额 #

给定各颜色可分配的节点数量，示例：

Red: 2
Blue: 2

核心定义 #

• 节点距离 dist(u, v)：两节点之间的最短路径长度
• 颜色集合 c：所有唯一颜色的集合（示例中 c = [Red, Blue]）
• 组内距离和 I_color：同一颜色组内所有节点对的距离之和（如 I_Red 表示Red组内节点对的距离总和）
• 组间距离和 E_color1,color2：不同颜色组之间所有节点对的距离之和（如 E_Red,Blue 表示Red组与Blue组之间节点对的距离总和）

评分计算公式 #

评分由组内距离和与组间距离和加权求和得到，公式示例如下：

评分 = (权重1 × 所有组内距离和的总和) + (权重2 × 所有组间距离和的总和)

以示例分配方案（B、C分配为Red，A、D分配为Blue）为例：

• I_Red = dist(B,C) = 1，I_Blue = dist(A,D) = 2，所有组内距离和总和为 1+2=3
• E_Red,Blue = dist(A,B)+dist(A,C)+dist(D,B)+dist(D,C) = 10+9+12+11=42
• 评分计算：4/5 × 3 + 1/5 × 42 = 10.8

问题目标 #

寻找一种节点颜色分配方案，最小化上述评分。由于全局最优解无法通过多项式复杂度算法求得，需生成较优的近似解。

内容的提问来源于stack exchange，提问作者mbison