2020 年时想的问题, 一直搁着. 今天突然想起来了.
瑞士轮编排通常要满足这些约束:
- 匹配过的两人不再重遇 (硬规则)
- 同分或近分者优先匹配
- 先后手尽量均衡 (棋类: 保证选手执黑 / 执白次数大致相等)
- 满足上述条件后适度随机 (部分严肃比赛不做随机)
要找到一组同时满足上述约束的匹配并不 trivial. 一种朴素做法是按经验法则先构造一组匹配, 再检查是否满足约束, 不满足就回溯重试 (trial and error). 早年 FIDE (国际棋联) 的裁判就是这样手工编排的. 这种启发式搜索的复杂度已经很高; 若改为暴力枚举所有可能的匹配再随机抽, 由于匹配数量随人数呈阶乘级增长, 更不可行. 因此需要更高效的算法求解.
