上周接了个内部需求把下个月十场左右的内部会议排进尽量少的会议室。每场会都要拉三五个成员而成员之间重叠得厉害——产品经理既要参加评审会又要参加需求对接会研发骨干既要在技术方案会上发言又要参与代码走查。我一开始老老实实按时间轴手工排排到一半发现已经要六间会议室行政当场表示不够用。冷静下来换了个视角才发现这个会场安排问题本质上就是教科书里的图的着色Graph Coloring问题而当时最适合快速落地的解法就是 Welsh-Powell 贪心着色算法。这篇文章把我从建模、推演、编码到上线踩坑的完整过程整理出来。如果你也要做会议排期、考试排考、课程表编排这类资源冲突问题或者只是想把图着色算法真正跑通一次应该能从这里拿到可直接抄作业的思路和代码。1. 从会议室不够用到图着色模型问题是怎么被抽象出来的1.1 一个真实得不能再真实的排会场景先说原始数据。假设公司某个月要开八场会参与人用甲、乙、丙、丁、戊、己六个代号表示具体如下编号会议名称参与成员M1产品月度评审会甲、乙、丙M2技术方案讨论会乙、丁、戊M3运营周例会甲、乙、己M4客户需求对接会丙、丁M5代码走查会戊、己、甲M6季度总结大会全员M7新员工入职培训己、戊M8管理团队碰头会乙、丙、丁排会的核心约束是一个人同一时间只能出现在一场会里。所以只要两场会议存在哪怕一个共同成员它们就不能被安排进同一个时间段否则就有人要分身。我的目标很明确最少用几个时间段能把八场会出现排完如果每个时间段对应一间会议室等价于最少需要几间会议室。1.2 图建模会议是点冲突是边把每场会议看成一个顶点两场会议有共同成员就在它们之间连一条边得到的就是一张冲突图。排会问题立刻变成了一个经典的数学问题给图中每个顶点染一种颜色要求相邻顶点颜色不能相同问最少需要几种颜色。这个最少颜色数在图论里叫色数记作 χ(G)。在我们这个场景里一种颜色就是一个时间段或一间会议室颜色相同的顶点就是可以并行举行的会议因为它们两两之间没有边、互不冲突。你可能会问为什么要绕这么大圈子直接按成员重叠少优先去贪心不行吗我的体会是图着色模型最大的价值不是给你一个魔法公式而是把问题变成一张可以被程序处理的图。之后不管是换算法、加约束、还是做可视化都是在这张图上做文章。数据能不能建模成图直接决定了后面所有方案的上限。1.3 为什么这个问题不能暴力硬解最朴素的想法是枚举假设最多用 k 个时间段把 n 场会议依次分配到 k 个时间里枚举量是 k 的 n 次方。n 取 30、k 取 6 时这个数大约是 2×10^23 量级普通机器算到地老天荒也跑不完。就算加一堆剪枝几十场会议也够呛。原因在于图着色是公认的 NP-hard 问题这里不展开复杂度理论你只要知道不存在一个多项式时间的算法能保证对任意图都求出最优色数。工程上面对 n 几十上百的排会场景大家普遍用两类手段启发式贪心跑得快结果通常不错但不保证最优比如简单贪心、Welsh-Powell、DSATUR。精确搜索回溯、分支限界小规模比如 n≤30可以验证最优解规模一大就爆炸。实际项目里几乎都是启发式出结果 精确法兜底验证的组合。而 Welsh-Powell 就是启发式里实现最简单、效果又比较稳的那个这也是我最终选它作为第一版方案的原因。2. Welsh-Powell算法的完整推演为什么先处理最难搞的会议2.1 算法三句话讲清楚先纠正一个容易被坑的细节这个算法英文名是Welsh-Powell以提出者命名你标题里的 Werch Powell 大概率是 Welsh 的笔误搜索资料时用 Welsh-Powell 才能查到正确出处。Welsh-Powell 的全部逻辑只有四步把所有顶点按度数也就是冲突数量从大到小排序得到着色顺序。取出当前顺序里第一个还没着色的顶点给它分配一种新颜色。按顺序扫描剩余未着色顶点如果某个顶点跟已经染上当前颜色的任意顶点都没有边相连就给它也涂上当前颜色。回到第 2 步直到所有顶点都有颜色。核心思想一句话每轮颜色都尽量一网打尽所有互不冲突的顶点。第 3 步本质上是在找当前剩余顶点里的一个独立集两两不相邻的顶点集合把它们合并到同一时间段。为啥第 2 步要取顺序里第一个未着色的顶点而不是随便挑一个因为第 1 步的排序决定了优先级既然我们把度数大的放在前面那么每一轮开头就应该是还没着色的人里最难搞的那个。让最难搞的会议先定档后面才不容易被它卡死。2.2 八场会议的完整手工推演先把上面 8 场会议的冲突关系算出来。判断规则很简单两场会议有至少一个共同成员就冲突。逐个两两检查后得到下面的冲突集合会议冲突的会议集合度数M1M2, M3, M4, M5, M6, M86M2M1, M3, M4, M5, M6, M7, M87M3M1, M2, M5, M6, M7, M86M4M1, M2, M6, M84M5M1, M2, M3, M6, M75M6M1, M2, M3, M4, M5, M7, M87M7M2, M3, M5, M64M8M1, M2, M3, M4, M65按度数降序得到顺序度数相同就按编号先后反正代码里总得有个稳定的平局规则M2(7) → M6(7) → M1(6) → M3(6) → M5(5) → M8(5) → M4(4) → M7(4)接下来一步一步着色。第 0 轮颜色 0取第一个未着色的 M2涂上颜色 0。然后按顺序扫描M6 与 M2 冲突跳过M1 与 M2 冲突跳过M3、M5、M8、M4、M7 全部与 M2 冲突跳过。结果颜色 0 只给了 M2。原因很直观M2 的度数达到 7跟所有其他会议都有冲突它当然只能独占一个时段。第 1 轮颜色 1第一个未着色顶点是 M6。M6 也是全员会它与剩下所有顶点都冲突所以颜色 1 也只给 M6。第 2 轮颜色 2第一个未着色顶点是 M1。继续扫描M3 与 M1 冲突跳过M5 与 M1 冲突跳过M8 与 M1 冲突跳过M4 与 M1 冲突跳过轮到 M7检查它与当前颜色 2 的顶点——只有 M1——M7 与 M1 不冲突于是 M7 也涂上颜色 2。本轮结果{M1, M7}。第 3 轮颜色 3第一个未着色顶点是 M3。M5 与 M3 冲突跳过M8 与 M3 冲突跳过M4 与 M3 不冲突涂上颜色 3。本轮结果{M3, M4}。第 4 轮颜色 4第一个未着色顶点是 M5。M8 与 M5 不冲突涂上颜色 4。本轮结果{M5, M8}。全部着色完毕一共用了 5 种颜色。对应的排会方案是时间段/会议室会议安排时段 0M2 技术方案讨论会时段 1M6 季度总结大会时段 2M1 产品月度评审会、M7 新员工入职培训时段 3M3 运营周例会、M4 客户需求对接会时段 4M5 代码走查会、M8 管理团队碰头会这个结果还能顺手验证一下是不是最优M2 和 M6 都连向其他所有顶点、彼此也相连所以它们至少要用 2 种颜色剩下的 M1、M3、M5 两两冲突构成一个三角形至少还需要另外 3 种颜色。下界 2 3 5 种而 Welsh-Powell 正好用 5 种说明它在这个实例上达到了最优。2.3 大度数优先为什么有效以及它不保证最优为什么度数大的优先这个策略这么关键我习惯用一个生活类比就像考试排监考最抢手的几位老师冲突最多一定要最先锁定时间否则等其他人把时间段占满他们反而没地方放。Welsh-Powell 把最难处理的顶点放在每个颜色的最前面相当于主动消除最大的约束压力。但必须强调Welsh-Powell 是一个启发式算法它不保证得到色数最优。原因是贪心策略只考虑当前局部选择不会回头调整已经涂好的颜色。经典的失败场景是两个度数相同的顶点选谁先染色会影响后面一大片顶点的可用颜色而算法本身只用度数排序并没有更多判断去看穿这种结构性差异。实际工程中我见过 WP 在部分随机密集图上比最优多出 1 到 2 种颜色的情况。所以我的习惯是WP 算出一版结果后先用下界论证比如找最大团判断是否有余量如果心里没底再上精确搜索或 DSATUR 交叉验证。2.4 和其他着色调度的对比做工程选型时手头至少要有几个备选方案。我把常见几种列成一张表算法核心思路时间复杂度实际效果简单贪心按输入顺序逐个给顶点分配最小可用颜色O(n²)结果极不稳定完全依赖输入顺序Welsh-Powell度数降序 每轮尽量合并独立集O(n²)~O(n³)实现简单密集图效果稳定DSATUR动态选择饱和度高邻居颜色种类多的顶点O(n²)结构复杂时往往比 WP 少用 1~2 色回溯/分支限界精确搜索指数级小规模n≤30可验证最优解我一般的工作流是大规模先用 WP 快速出基线如果会议之间有大量不均匀的冲突结构再换 DSATUR 试试真正要对外承诺这是最少会议室的时候把 n 压缩到 30 以内跑回溯验证。这样既有速度又有可信度。3. 代码落地Python和C两种写法从输入到验证3.1 数据结构选型写代码前先想清楚数据结构。会议本身用(名称, 成员集合)表示冲突图用邻接表实现——每个顶点存一个和它冲突的顶点集合。为什么用集合而不是列表因为后面着色时要频繁判断某个顶点是否与某颜色内的顶点相邻集合可以在构建时顺便去重而且做交集判断也方便。成员集合直接用 Python 的set两场会议是否冲突就是一个集合交集是否为空的问题。3.2 Python实现与运行结果完整实现如下from collections import defaultdict def build_conflict_graph(meetings): meetings: list of (name, frozenset_of_members) 返回邻接表 graph[i] set(与i冲突的顶点下标) n len(meetings) graph defaultdict(set) for i in range(n): for j in range(i 1, n): # 只要有共同成员就认为冲突 if meetings[i][1] meetings[j][1]: graph[i].add(j) graph[j].add(i) return graph, n def welsh_powell(graph, n): # 第 1 步按度数降序排列顶点 order sorted(range(n), keylambda i: len(graph[i]), reverseTrue) colors [-1] * n current_color 0 remaining set(range(n)) while remaining: # 第 2 步取顺序中第一个未着色顶点分配新颜色 v next(v for v in order if v in remaining) colors[v] current_color remaining.remove(v) # 第 3 步扫描剩余顶点能同色的尽量同色 for u in order: if u in remaining: # 检查 u 是否与任何已染当前颜色的顶点冲突 adjacent_same_color any(colors[w] current_color for w in graph[u]) if not adjacent_same_color: colors[u] current_color remaining.remove(u) current_color 1 return colors, current_color def verify(graph, colors, n): for i in range(n): for j in graph[i]: if colors[i] colors[j]: return False return True # 测试数据八场会议 meetings [ (产品月度评审会, frozenset(甲乙丙)), (技术方案讨论会, frozenset(乙丁戊)), (运营周例会, frozenset(甲乙己)), (客户需求对接会, frozenset(丙丁)), (代码走查会, frozenset(戊己甲)), (季度总结大会, frozenset(甲乙丙丁戊己)), (新员工入职培训, frozenset(己戊)), (管理团队碰头会, frozenset(乙丙丁)), ] graph, n build_conflict_graph(meetings) colors, num_colors welsh_powell(graph, n) print(验证通过:, verify(graph, colors, n)) print(最少需要时段数:, num_colors) for c in range(num_colors): names [meetings[i][0] for i in range(n) if colors[i] c] print(f时段 {c}: {, .join(names)})运行输出如下验证通过: True 最少需要时段数: 5 时段 0: 技术方案讨论会 时段 1: 季度总结大会 时段 2: 产品月度评审会, 新员工入职培训 时段 3: 运营周例会, 客户需求对接会 时段 4: 代码走查会, 管理团队碰头会和手工推演完全一致。这里的verify函数是我排会必写的最后一道保险遍历全部边检查相邻顶点颜色是否不同。这个步骤不能省尤其是后面一旦改动输入数据或加约束有一道自动验证能救你于水火。3.3 C实现要点如果场景要嵌进已有服务或者数据量上千场会议C 版本会更合适。核心函数如下#include bits/stdc.h using namespace std; struct Meeting { string name; setstring members; }; vectorsetint buildGraph(const vectorMeeting meetings) { int n meetings.size(); vectorsetint graph(n); for (int i 0; i n; i) { for (int j i 1; j n; j) { for (const string p : meetings[i].members) { if (meetings[j].members.count(p)) { graph[i].insert(j); graph[j].insert(i); break; // 找到一个共同成员即可判定冲突 } } } } return graph; } pairvectorint, int welshPowell(const vectorsetint graph) { int n graph.size(); vectorint order(n); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [](int a, int b) { return graph[a].size() graph[b].size(); }); vectorint colors(n, -1); setint remaining; for (int v : order) remaining.insert(v); int color 0; while (!remaining.empty()) { int v -1; for (int x : order) { if (remaining.count(x)) { v x; break; } } colors[v] color; remaining.erase(v); for (int u : order) { if (!remaining.count(u)) continue; bool conflict false; for (int w : graph[u]) { if (colors[w] color) { conflict true; break; } } if (!conflict) { colors[u] color; remaining.erase(u); } } color; } return {colors, color}; }注意两点一是 C 里用set存邻接表判断顶点是否与某颜色内顶点冲突时直接遍历它邻居的颜色逻辑与 Python 一致二是构建冲突图时找到第一个共同成员就该break别傻傻把整个集合遍历完这在高重复成员数据里能省不少时间。3.4 结果验证与复杂度分析验证逻辑前面已经写过了但值得再说清楚一点贪心着色最怕相邻同色这种低级错误一旦出问题整个排期表直接作废。所以我总是固定三步走先跑着色再跑verify全量校验最后把着色结果输出成时段→会议列表让人肉眼扫一遍。复杂度方面建图需要两两比较会议成员是 O(n²·k)k 是每场会的平均人数排序 O(n log n)着色阶段最坏情况下每轮都要扫描剩余顶点并检查其邻居颜色整体大约是 O(n·(nm))m 是边数。对几百场会议这个量级完全没压力。真到几千上万顶点就要看下面的优化。3.5 大图优化的一个实用技巧当顶点数到几千any(colors[w] current_color for w in graph[u])这种逐边扫描会成为瓶颈。一个工程上常用的优化是给每个顶点维护一个颜色占用位掩码每染一个颜色就把它的编号对应位放进所有邻居的掩码里。后续判断某顶点能否染当前颜色时只需检查当前颜色位是否在掩码中从 O(度数) 变成 O(1)。代价是多花一点内存但对稀疏大图收益非常明显。另一个更简单便宜的技巧是多次随机打破平局取最优。Welsh-Powell 排序时度数相同的顶点顺序完全由代码决定而这一顺序对结果有影响。我在实际项目中会把等度数顶点的遍历顺序随机打乱跑 20 到 50 次保留色数最少且各时段会议数最均衡的那一版。这个 trick 基本零成本却经常能把结果再压下去 1 个颜色。4. 工程排线时真正会踩的坑以及我的应对4.1 坑一冲突判定只看人远远不够把成员重叠作为唯一冲突标准是第一版最容易犯的错。真实会议场景里冲突来源至少还有三类一是时间偏好某场会必须在特定的半天开如果两场会都要抢那个半天它们也冲突二是独占资源比如整个公司只有一间能容纳全员的大会议室三是设备限制两场会都要用同一套视频会议终端。我的处理原则是硬约束和软约束分开建模。硬约束必须错开老老实实变成图中的边软约束尽量错开但实在不行也能接受别塞进图里否则图会变成完全图任何着色调度都会失效。软约束放到后处理阶段用加权评分去优化比如弹性地把某场会挪到邻近时段只要不碰硬约束就接受。4.2 坑二最小色数不等于可执行排班算法给出的 5 个颜色代表 5 个时段但它不保证每个时段的工作量均匀。极端情况下一个颜色里塞了 4 场会另一个颜色只有 1 场会——4 场会那个时段会议室和人都忙不过来。我们在数据分析里经常讲均值不代表分布排会也一样。对策是加一个均衡化后处理检查所有颜色里的会议数量如果某颜色过载尝试从里面抽出一场与目标颜色所有顶点都不冲突的会议挪过去。这个检查和着色时的判断逻辑完全一样所以实现成本很低。我通常把它写成一个 while 循环直到无法再优化为止。4.3 坑三时间槽和房间是两层问题前文我一直把一种颜色等于一个时间段也等于一间会议室这是在会议室数量无上限的假设下。现实往往反过来会议室只有 3 间或大小不一。这时候问题变成两层第一层用图着色把会议分成若干互不冲突的时段第二层在每个时段内部把若干场会议分配进有限的物理房间考虑房间容量、设备匹配。第二层本质上是个装箱问题跟着色不是同一个模型。我在项目里的做法是先跑 Welsh-Powell 把时段定下来再写一个简单的按容量降序贪心去填房间。如果第二层出现这个时段塞不下的情况就把相关会议之间补一条硬约束边重新回到第一层再算一次。两阶段交替迭代实战里通常两三轮就收敛了。4.4 坑四排完之后的人因素排会排到最后真正让你崩溃的往往不是算法而是排完之后大家开始改时间。技术方案讨论会要推迟一天新员工入职培训的人选换了季度总结会全员参加改成部分参加。每改一次冲突图就变一次方案就得重排。所以从第一天起我就把输入数据做成独立的配置文件或表格程序只读数据不写死任何会议信息。改完一轮数据重跑整个流程只要几秒钟。排完的输出也要让行政看得懂时段、会议室、主持人、成员、备注逐项列清楚。千万别只抛出一个色号那是给自己挖坑。4.5 我的工程化建议清单最后把这轮实战沉淀下来的操作清单列出来照着做基本不会翻车数据先行把所有会议信息集中到一个可编辑的文件/表格里程序从那里读取。硬软分离硬冲突画成边软冲突留给后处理评分。快速基线先用 Welsh-Powell 跑一版配合随机平局多跑几次取最优。自动验证着色完成后必须跑一遍相邻不同色校验。两阶段兜底时段定完再分房间房间塞不下就补边重算。输出可解释最终交付的排期表必须是人能直接看懂的别只给算法结果。留手动入口总有算法想不到的例外比如领导拍板这两场必须挨着开这时候要给人工 override 的接口。我在实际项目里跑完这版 Welsh-Powell 之后排期从手工方案的 6 个时段降到了 5 个时段相当于直接省下一间会议室。后来另一波数据量更大的排考需求我也是拿这套代码改了改输入格式就顶上了。图着色这个思路确实是排会/排考/排课这一类冲突调度问题的通用解法而 Welsh-Powell 就是那个入门最快、效果最稳的第一板斧。