ggr*_*ner 24 sorting algorithm comparison ranking
我想对一组项目(大小可能大于100,000)进行排序或排序,其中集合中的项目没有内在(可比较)值,而我所拥有的是用户提供的任何两个项目之间的比较.一种主观的方式.
例如:考虑的元素的集合[a, b, c, d]用户和比较b > a,a > d,d > c.这个集合的正确顺序是[b, a, d, c].
这个例子很简单,但可能会有更复杂的情况:
c > b.在这种情况下会导致与上面的排序冲突.b > a,d > c.在这种情况下,排序是模糊的.它可能是[b, a, d, c]或[d, c, b, a].在这种情况下,任何订购都是可以接如果可能的话,以某种方式考虑相同比较的多个实例并且给予具有更高发生率的那些更多权重将是很好的.但是没有这种条件的解决方案仍然可以接受.
Zuckerberg的FaceMash应用程序使用了这种算法的类似应用,他根据比较对人进行了排名(如果我理解正确的话),但是我无法找到该算法实际上是什么.
是否存在可以解决上述问题的算法？如果是这样的话,我不想花钱努力想出一个.如果没有特定的算法,是否有某些类型的算法或技术可以指向我？
Der*_*urk 18
这是另一个竞技场已经出现的问题:竞技游戏!在这里,目标也是在一系列1对1比较的基础上为每个玩家分配全局"等级".当然,困难在于比较不具有传递性(我在你的问题中采用"主观"来表示"由人提供").卡斯帕罗夫击败菲舍尔节拍(不认识另一位国际象棋选手!)鲍勃有可能击败卡斯帕罗夫.
这会产生无用的算法,这些算法依赖于传递性(即a > b and b > c => a > c),最终得到(可能)高度循环的图形.
已经设计了几种评级系统来解决这个问题.
最着名的系统可能是竞争国际象棋选手的Elo算法/得分.它的后代(例如,Glicko评级系统)更复杂,并考虑到赢/输记录的统计特性 - 换句话说,评级的可靠性如何？这类似于您使用更多"游戏"加权更重的记录的想法.Glicko也构成了Xbox Live用于多人视频游戏的TrueSkill系统的基础.