n选手赛事独特双人组队轮次调度算法优化求助

需求说明 #

给定n名选手，每轮需组建两人队伍，要求所有轮次中的组队组合完全唯一——即每名选手不会与之前合作过的队友再次组队。

现有实现代码 #

all_players = {
    player: set({player})  # 存储历史队友，包含自身
    for player in tournament.players
}

team_backlog = []

for round in self.rounds:
    available_team_mates = set(all_players)
    players_in_use = set()
    all_teams = []

    # 为所有选手配对
    for player, prior_team_mates in all_players.items():
        if player in players_in_use:
            continue

        # 先尝试从待配对队列中找兼容队友
        for next_team_mate in team_backlog:
            if next_team_mate not in prior_team_mates:
                team_backlog.remove(next_team_mate)
                break
        else:
            # 待配对队列无兼容队友，从可用选手中筛选
            compatible_team_mates = available_team_mates - prior_team_mates
            try:
                next_team_mate = compatible_team_mates.pop()
            except KeyError:
                # 仍无兼容队友，若还有未合作过的候选则加入待配对队列
                if len(prior_team_mates) < len(all_players):
                    team_backlog.append(player)
                continue

        # 更新配对状态
        players_in_use |= {next_team_mate, player}
        available_team_mates -= {player, next_team_mate}
        all_players[next_team_mate].add(player)
        prior_team_mates |= {next_team_mate}
        all_teams.append(round.create_team(player, next_team_mate))

现有算法逻辑 #

• 为每位选手维护一个「历史队友」集合（初始包含自身）。
• 优先从待配对队列中查找未合作过的队友，找到则组队并更新状态。
• 若待配对队列无合适人选，则从当前可用选手中筛选未合作过的队友，找到则组队并更新状态。
• 若仍找不到兼容队友，且该选手还有未合作过的候选，则将其加入待配对队列，留到下一轮优先配对。

当前核心问题 #

1. 当历史配对分布不均时，部分选手会找不到合适配对，导致某轮生成奇数数量的队伍（即有选手无法组队）。
2. 假设n名选手最多可进行n轮最优调度，但无法验证该假设的合理性。

分析与解决方案建议 #

理论上限与轮次合理性验证 #

该问题本质是完全图的边分解问题：将代表选手的节点、代表组队的边构成的完全图，分解为若干个匹配（每轮的组队集合是一个匹配，匹配中的边不共享节点）。

• 当n为偶数时：完全图可分解为n-1个完美匹配（每轮所有选手都能组队），每个选手恰好与其他n-1名选手各组队一次，总轮次上限为n-1。
• 当n为奇数时：完全图可分解为n个近完美匹配（每轮有1名选手轮空，其余组队），每个选手会轮空1次，与其他n-1名选手各组队一次，总轮次上限为n。
  你的n轮假设在n为奇数时成立，偶数场景下应为n-1轮。

算法优化方案 #

1. 基于环形调度的最优匹配生成（适用于所有n）

这是能保证无重复组队且每轮组队数量最大化的经典方法：

• 偶数n场景：
  1. 固定1名选手在中心位置，其余选手围成环形。
  2. 每轮：中心选手与环形对面的选手组队，环形上其余相邻选手两两组队。
  3. 每轮结束后，环形选手顺时针旋转1个位置，重复上述步骤，共进行n-1轮。
• 奇数n场景：
  1. 虚拟添加1名选手，使总人数变为偶数，按上述偶数方法生成n-1轮完美匹配。
  2. 每轮中，与虚拟选手配对的真实选手即为该轮轮空选手，其余真实选手正常组队。
  3. 额外添加1轮：让之前轮空过的选手两两组队（若n为奇数，此时剩余未组队的选手对恰好能组成完整队伍），总轮次为n轮。

2. 修正现有贪心算法逻辑

针对当前算法容易累积配对冲突的问题，可调整策略：

• 每轮开始时，为所有未配对选手构建兼容图（边代表未合作过的选手对）。
• 采用最大匹配算法（如简化版匈牙利算法）从兼容图中选出最多的不重叠组队，确保每轮组队数量为偶数（或尽可能接近偶数）。
• 放弃待配对队列的累积逻辑，改为每轮优先为剩余未合作次数最多的选手寻找队友，避免单个选手的配对冲突累积。

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