我想对一个包含多个元素(可能大于100,000)的集合进行排序或排名,但是集合中的元素没有固有的(可比较的)价值,而是我所拥有的只有用户提供的任意两个元素之间的比较结果,这些结果是主观的。
例如:考虑一个元素为
这个例子很简单,但是还有更复杂的情况:
- 由于比较结果是主观的,某个用户还可能说
如果可能的话,最好考虑到同样的比较出现多次,并给予较高的权重。但是如果没有这个条件,解决方案仍然可接受。
类似的算法也被 Zuckerberg 的 FaceMash 应用程序所使用,他根据比较结果对人物进行排名(如果我理解得正确的话),但我没有找到该算法实际上是什么。 是否存在可以解决上述问题的算法?如果已经有了特定的算法,我不想浪费精力来尝试创造一个新算法。如果没有特定的算法,您是否可以指向某些类型的算法或技术?
例如:考虑一个元素为
[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 应用程序所使用,他根据比较结果对人物进行排名(如果我理解得正确的话),但我没有找到该算法实际上是什么。 是否存在可以解决上述问题的算法?如果已经有了特定的算法,我不想浪费精力来尝试创造一个新算法。如果没有特定的算法,您是否可以指向某些类型的算法或技术?