algorithm - 基于比较的排名算法

Question

我想对项目集合(大小可能大于 100,000)进行排名或排序，其中集合中的项目没有内在(可比较)值(value)，我所拥有的只是任意两个项目之间的比较 由用户以主观方式提供。

示例:考虑一个包含元素 [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 应用程序使用了此算法的类似应用程序，他根据比较对人进行排名(如果我理解正确的话)，但我无法找到该算法的实际含义。

是否已经存在可以解决上述问题的算法？如果是这样的话，我不想花精力去想出一个。如果没有特定的算法，您是否可以指出某些类型的算法或技术？

Answer 1

这是在另一个领域已经发生的问题:竞技游戏!这里的目标也是在一系列一对一比较的基础上为每个玩家分配一个全局“排名”。当然，困难在于比较不是传递性的(我在你的问题中将“主观”表示为“由人类提供”)。卡斯帕罗夫打败费舍尔打败(不认识其他棋手!)鲍勃有可能打败卡斯帕罗夫。

这会导致依赖传递性的无用算法(即 a > b 和 b > c => a > c)，因为您最终(可能)会得到一个高度循环的图。

已经设计了多种评级系统来解决这个问题。

最著名的系统可能是 Elo algorithm/score对于有竞争力的棋手。它的后代(例如，Glicko rating system)更加复杂，并考虑了输赢记录的统计属性——换句话说，评级的可靠性如何？这类似于您对玩过更多“游戏”的记录进行加权的想法。 Glicko 还构成了 TrueSkill system 的基础在 Xbox Live 上用于多人视频游戏。