我想对一个项目集合(大小可能大于100,000)进行排序或排序,其中该集合中的项目没有内在(可比较)值,而 我所拥有的只是 用户在其中提供的 任何两个项目之间的比较 主观的方式。
例如:考虑的元素的集合[a, b, c, d]用户和比较b > a,a > d,d > c。此集合的正确顺序为[b, a, d, c]。
[a, b, c, d]
b > a
a > d
d > c
[b, a, d, c]
这个例子很简单,但是可能会有更复杂的情况:
c > b
[d, c, b, a]
如果可能的话,最好以某种方式考虑同一比较的多个实例,并为出现次数更高的实例赋予更大的权重。但是没有这种情况的解决方案仍然可以接受。
扎克伯格的FaceMash应用程序使用了该算法的类似应用程序,他在该应用程序中根据比较对人进行排名(如果我理解正确的话),但是我无法找到该算法的真正含义。
是否已经存在可以解决上述问题的算法? 如果是这样的话,我不想花力气想出一个。如果没有特定的算法,您可能会指出某些类型的算法或技术吗?
这是另一个领域已经出现的问题:竞技游戏!同样,这里的目标是根据一系列1对1的比较为每个玩家分配一个全局“排名”。当然,困难在于比较不是可传递的(在您的问题中,我将“主观”理解为“由人提供”)。卡斯帕罗夫击败了费舍尔(不认识其他国际象棋选手!)鲍勃可能会击败卡斯帕洛夫。
这导致无用的算法依赖于传递性(即a > b and b > c => a > c),最终导致(可能)出现一个高度循环的图。
a > b and b > c => a > c
已经设计出几种评级系统来解决这个问题。
最著名的系统可能是竞技棋手的Elo算法/得分。它的后代(例如,Glicko评分系统)更加复杂,并考虑了获胜/失败记录的统计属性- 换句话说,评分的可靠性如何?这类似于您对播放更多“游戏”的记录进行加权的想法。Glicko还构成了Xbox Live上用于多人视频游戏的TrueSkill系统的基础。