基于Doubles Round Robin Sorting Algorithm的6人匹克球双打排程算法求解

问题概述 #

6人（A、B、C、D、E、F）每周开展2v2双打活动，需完成以下排程：

• 共4次活动，每次分2组，每组6场比赛（总计8组48场）
• 45场为唯一对局（所有搭档组合对阵其余搭档组合），剩余3场可重复安排
• 每组必须满足三项约束：
  1. 每位选手参赛4场、轮空2场
  2. 无选手连续轮空两场
  3. 每组内每位选手的搭档不重复

此前用Excel VBA暴力枚举耗时过长，需高效排程算法。

核心算法思路 #

1. 单组约束预筛选 #

从组合数学角度缩小候选范围，避免无效枚举：

• 搭档唯一性：每位选手有5个潜在搭档，单组参赛4场需匹配4个不同搭档，直接排除搭档重复的对局组合
• 轮空规则：6场比赛中，为每位选手分配2场不连续的轮空场次，同时保证每场恰好2人轮空（6人×2次轮空=12人次，6场×2人/场=12人次，刚好匹配）
• 先生成所有满足「轮空不连续+每场2人轮空」的轮空分配方案，再为每个场次匹配符合搭档唯一性的对局。

2. 贪心+回溯混合算法 #

放弃全量暴力枚举，用贪心优先填充，冲突时回溯调整：

• 对局排序：将45场唯一对局按「选手搭档重复次数」升序排列，优先安排搭档组合出现次数少的对局，避免后期出现某选手搭档重复的死局
• 组构建逻辑：每次构建组时，从剩余对局中选6场，实时校验三个约束：
  • 统计每个选手参赛次数是否为4次
  • 检查每个选手的轮空场次是否连续
  • 确认每个选手的搭档无重复
• 冲突回溯：若当前选组不满足约束，回溯替换1-2场对局，优先替换轮空冲突或搭档重复的场次，减少无效尝试。

3. 剩余场次填充 #

8组共48场，用完45场唯一对局后，剩余3场优先选择「选手搭档次数分布最均匀」的对局，保证整体排程公平性。

满足约束的示例组 #

以下是一组符合所有约束的6场比赛安排：

校验结果：

• 每位选手参赛4场、轮空2场（如A参赛1、3、5、6，轮空2、4，无连续轮空）
• 每位选手搭档均不重复（如A的搭档为B、D、E、F）

完整唯一对局列表 #

T1  T2  Bye
AB  CD  EF
AB  CE  DF
AB  CF  DE
AB  DE  CF
AB  DF  CE
AB  EF  CD
AC  BD  EF
AC  BE  DF
AC  BF  DE
AC  DE  BF
AC  DF  BE
AC  EF  BD
AD  BC  EF
AD  BE  CF
AD  BF  CE
AD  CE  BF
AD  CF  BE
AD  EF  BC
AE  BC  DF
AE  BD  CF
AE  BF  CD
AE  CD  BF
AE  CF  BD
AE  DF  BC
AF  BC  DE
AF  BD  CE
AF  BE  CD
AF  CD  BE
AF  CE  BD
AF  DE  BC
BC  DE  AF
BC  DF  AE
BC  EF  AD
BD  CE  AF
BD  CF  AE
BD  EF  AC
BE  CD  AF
BE  CF  AD
BE  DF  AC
BF  CD  AE
BF  CE  AD
BF  DE  AC
CD  EF  AB
CE  DF  AB
CF  DE  AB

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