淘汰赛设计问题
本帖最后由 BeerRabbit 于 2016-7-1 15:42 编辑要举办一场象棋赛。假定每场比赛都只有胜负之分，没有平局；采用单败淘汰赛制，所以，对于给定的2^n个选手，可以有n轮比赛，第n轮即冠军争夺赛。
已知：每个选手对其他各个选手的经验胜率（这个数据通过对历史数据的统计得出，在数学处理上可以看做是本次大赛的严格胜率），比如用P(i,j)（i≠j）表示选手i对选手j的胜率。
问题：给出一个分组方案，使得各个选手的夺冠概率分布最合理。
补充：关于问题中的“胜率分布最合理”，可以有很多开放的衡量标准，比如：
（1）方差最小；
（2）熵最大；
（3）其他……
PS：如果使用穷举方法，从(2^n)!/2^(2^n-1)个分组方案中进行筛选，理论上是可行的，但是耗时有点吃不消……因此，需要一个优化方法，这个方法是什么？ “已知：每个选手对其他各个选手的经验胜率”
这其实是一张$N\times N$的表格，记录了任意两位棋手对弈的胜负概率。
如果以这张表格作为此问题的输入数据，那么这是一个$NP$完全问题，
即不存在关于$N$的多项式时间复杂度的算法，对于任意的输入数据都能求出正确答案。
因此楼主不用煞费心机寻找又高效又能得出准确结果的算法了。
#####
实际上 ，并不是任意一张胜率表都是合理的。
每一位象棋、围棋等棋类选手，我们通常用一个数值来衡量他的“棋力”。
以围棋为例，这个数值称为"Elo"。围棋选手的世界排名就是根据"Elo"的大小进行排名的（参见 http://www.goratings.org 表格的最后一列）
每$400$点Elo就等于一个数量级，
即Elo为$3600$的选手与Elo为$3200$的选手对战，前者的胜率约为$90%$；
Elo为$3200$的选手与Elo为$2800$的选手对战，前者的胜率也是约为$90%$；
而Elo为$3600$的选手与Elo为$2800$的选手对战，前者的胜率约为$99%$。
有了Elo值作为度量，那么
知道了$A$大概率赢$B$以及$B$大概率赢$C$，就可以推出$A$会以更大概率赢$C$。
而如果$C$也大概率赢$A$就不合情理了。
也就是具有传递性的胜率表才是合理的。
#####
那么“合理的胜率分布”就应该是选手的夺冠概率与$10$的${Elo}/400$次方成正比。
为了达成这一分布，通常会把已知Elo很高的选手（种子选手）分在不同的分组，避免他们过早地撞上。
例如，一共有$16$名选手，他们的Elo都已知，从高到低排序后得到第$1$、第$2$、……、第$16$，那么合理的分组就是
{[(1,9),(5,13)],[(3,11),(7,15)]},{[(2,10),(6,14)],[(4,12),(8,16)]}，
以确保各路高手能顺利晋级，避免过早被其他高手撞下去。 为什么不是
{[(1,16),(8,9)],[(4,13),(5,12)]},{[(2,15),(7,10)],[(3,14),(6,11)]}
页:
[1]