类瑞士赛制两轮批量对阵生成器的图论算法求解需求

核心需求 #

• 区别于传统瑞士赛逐轮生成对阵，需批量生成两轮完整对阵
• 采用Glicko/Elo类评分系统做种子排位：
  • 初始阶段所有玩家用默认评分，初始对阵随机生成
  • 后续生成对阵时，以最小化对阵双方评分差的平方和为优化目标
• 硬性规则：绝对禁止两名玩家重复对阵（同一轮内严格规避，跨轮也要避免）
• 每批两轮对阵结束后，根据对战结果更新玩家评分

图论建模思路 #

将问题转化为图论模型来拆解：

• 顶点：代表每一位玩家
• 边：代表一对玩家的可行对阵（已对阵过的玩家间，给这条边设置极高的「距离权重」，确保优化时不会被选中）
• 目标：找到满足以下条件的子图：
  1. 每个顶点恰好关联2条边（对应每个玩家在两轮中各进行一场对战）
  2. 所有选中边的距离平方和最小

示例可行子图（不连通结构）：

1 vs 2
2 vs 3
3 vs 1

4 vs 5
5 vs 6
6 vs 4

两组3人各自形成闭环，互相不连通，完全符合每个玩家打两场的要求

可行算法方向 #

这个问题本质是带约束的最小权2-因子问题（2-因子指每个顶点度数恰好为2的子图），属于组合优化领域，以下是几种可行的解决思路：

1. 整数线性规划（ILP） #

适合小规模玩家群体，能保证最优解：

• 变量定义：给每条边设置0-1变量，1代表选中该对阵，0代表不选
• 约束条件：
  • 每个顶点对应的边变量之和必须等于2
  • 已对阵过的边，变量强制设为0
• 目标函数：最小化所有选中边的评分差平方和
• 缺点：玩家数量超过20人后，计算复杂度会急剧上升，效率变低

2. 启发式近似算法 #

适合大规模玩家场景，牺牲最优性换效率：

• 先按评分对玩家排序，采用贪心策略：优先给评分最接近的未配对玩家安排两场对阵（全程避开重复对阵记录）
• 若贪心过程中出现冲突（比如某玩家剩余可选对手的评分差都过大），回溯调整局部配对组合
• 可以通过多次迭代调整，逐步逼近最优结果

3. 分步匹配构建 #

比直接求解2-因子简单，实现成本低：

• 第一步：求解第一轮的最小权完美匹配（每个玩家配对一次，评分差平方和最小，同时避开重复对阵）
• 第二步：基于第一轮的配对结果，求解第二轮的最小权完美匹配，额外约束不能和第一轮的对手重复
• 缺点：这种分步优化可能无法达到两轮总评分差平方和的全局最优，但胜在逻辑简单、易实现

关键注意点 #

• 玩家人数无需限制为偶数：示例中的3人组是奇数，但每个玩家都能完成两场对战，因为2-因子可以是多个环的组合（比如3-环+3-环）
• 重复对阵的权重设置要足够高：比如设为当前所有可能评分差平方最大值的1000倍，确保优化过程中绝不会被选中

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