首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

求一排名算法,该如何处理

2013-04-02 
求一排名算法产生一千个正随机数,每个数表示一个人的下棋水平(A表示人,a表示其水平;B表示另一人,b表示其水

求一排名算法
产生一千个正随机数,每个数表示一个人的下棋水平
(A表示人,a表示其水平;B表示另一人,b表示其水平,a不小于b)
A胜B的概率是 MIN(50%+(a/b-1),1)

任意挑两个人对弈,用随机数按以上概率确定胜负
重复以上步骤一万次,产生一万条对弈记录

现在要求设计一算法,输入是这一万条记录,输出是一千个人的排名
然后和这一千个人的水平相比较,以评判排名算法的优劣

[解决办法]
一般排名算法用等级分的办法比较合理,但你的测试数据太少,可能会影响准确性。
一开始,所有的棋手都有一样的等级分;
对每次对局,根据对局双方的等级分差和胜负关系来增减等级分;
上一步只是静态调整,当一个人的等级分变化时,还需要调整所有跟他有历史对局的人,所以还需要做动态调整,这个调整比较麻烦,不可能每增加一次对局就调整一次,可以在总对局达到多少是对所有棋手做一次调整。
[解决办法]
我觉得你这里的随机性只是为了保证不同水平的人都有可能对战到,
但是你随机抽取两来对战这种会造成每人的对战局数差异会很大,极大影响了对战结果
以前遗传算法的时候用过一个2副本锦标赛选择
也就是123456 不保序随机打乱(大家都可能不再在自己位置上 、复杂度O(n))比如634512
然后 (1、6)(2、3)(3、4)(4、5)(5、1)(6、2)对战,
这样既保证了对战对手的随机性,也保证大家参赛的机会均等


void MyFunctions::Sort_shuffle(int* pData,const int& nsize)
{
    //随机打乱//倒序//不允许保序
    for ( int i = nsize - 1 ; i > 0 ; i --)
    {      
        int index = rand()%i;
        std::swap(pData[index],pData[i]);              
    }
}

热点排行