如何通过编程计算淘汰赛制下每支队伍的夺冠概率

核心思路 #

这个问题可以通过动态规划（DP）高效求解，时间复杂度为O(n² * 2ⁿ)，适用于n≤10（也就是最多1024支队伍）的场景。

状态定义 #

定义dp[r][i]为第r轮比赛结束后，队伍i仍然存活的概率：

• 初始状态：dp[0][i] = 1，所有队伍在开赛前都处于存活状态
• 最终结果：dp[n][i]就是队伍i最终夺冠的概率（2ⁿ支队伍需要打满n轮才能决出冠军）

对阵范围判定 #

淘汰赛的签表是固定分区的，第r轮时，队伍i只会和同个2ʳ大小分区内、另一个2ʳ⁻¹子分区的存活队伍对阵：
以8支队伍（n=3）的场景为例：

• 第1轮（r=1）：分区大小为2，每支队伍只能和同分区的另一支队伍对阵
• 第2轮（r=2）：分区大小为4，队伍只能和同4队分区内、另一个2队子分区的胜者对阵
• 第3轮（r=3）：分区大小为8，队伍只能和另一个4队子分区的胜者对阵

状态转移方程 #

dp[r][i] = dp[r-1][i] * sum( dp[r-1][j] * P[i][j] for j in 第r轮i的可能对手集合 )

含义是：队伍i要撑到第r轮结束，首先要在r-1轮存活，同时第r轮的对手j也要在r-1轮存活，再乘以i击败j的概率加权求和。

代码实现示例（Python） #

def calculate_champion_prob(n, P):
    # n: 2^n 为参赛队伍总数
    # P: 二维数组，P[i][j] 为i击败j的概率，大小为(2^n)*(2^n)
    team_count = 1 << n
    dp = [[0.0] * team_count for _ in range(n+1)]
    # 初始化初始状态
    for i in range(team_count):
        dp[0][i] = 1.0
    
    for r in range(1, n+1):
        block_size = 1 << r
        half_block = 1 << (r-1)
        for block_start in range(0, team_count, block_size):
            # 遍历当前块的所有队伍
            for i in range(block_start, block_start + block_size):
                # 计算i所在的半区，对手在另一个半区
                if i < block_start + half_block:
                    # i在前半区，对手在后半区
                    opponents = range(block_start + half_block, block_start + block_size)
                else:
                    # i在后半区，对手在前半区
                    opponents = range(block_start, block_start + half_block)
                # 计算求和项
                win_sum = 0.0
                for j in opponents:
                    win_sum += dp[r-1][j] * P[i][j]
                dp[r][i] = dp[r-1][i] * win_sum
    return dp[n]

测试用例示例 #

2支队伍（n=1）的场景下，设置P[0][1] = 0.7，P[1][0] = 0.3，调用函数后得到的结果为[0.7, 0.3]，符合预期。

注意事项 #

上面的实现默认队伍按编号顺序排列在签表中，如果实际签表的对阵顺序不是按编号排列，只需要修改opponents的生成逻辑，匹配实际签表的分区规则即可。

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