排名-最小化成对比较 [英] Ranking - minimizing pair-wise comparison

问题描述

我有一个100个项目的列表，我想生成一个排名列表，要求用户对项目对进行评级，并提示：您是更喜欢项目A还是项目B？。因为询问这些项目的所有可能组合真的很累。例如。如果第1项比第2项更受青睐，第2项比第3项更受青睐，则无需比较第1项和第3项。

I have a list of 100 items and I want generate a ranked list, the user is asked to rate pairs of items, prompting: "Do you prefer item A or item B instead?". Since it would be really tiring asking every possible combination of those items. Eg. if item 1 is prefered over item 2, and item 2 is preferred over item 3, it's not necessary to compare item 1 and item 3.

我正在寻找一个减少此类比较并提供完整排名列表的算法。

I'm looking for a algorithm that reduce such comparisons and will give a complete ranked list.

如果通过使用3对项来提高比较次数，则更喜欢这种方式。在这种情况下，用户将对3对中的最佳和最差进行评分，从而在转弯中对3个项目进行排名。

If the number of comparisons would be improved by using 3-pairs of items instead, it would be prefered that way. In this case the user would rate the best and the worst of the 3 pairs, thus ranking 3 items per 'turn'.

推荐答案

可能有 100！个订单。 2 ^ 524< 100！ < 2 ^ 525 ，所以您能做的最好的就是 525 二元问题。

There are 100! possible orders. 2^524 < 100! < 2^525 so the best you can ever do is 525 binary questions.

3个问题的版本做得更好。它可以给出6个可能的答案，因此通过相同的分析，您能做的最好的就是 204 个问题。

The 3 question version does better. It can give 6 possible answers, so the best you can ever do by the same analysis is 204 questions.

您不太可能轻松达到这些界限。但是您可以接近。

It is unlikely that you can easily get to those bounds. But you can get close.

对于二进制比较，很难做到比福特-约翰逊合并插入排序。

For binary comparisons, it will be hard to do better than the Ford-Johnson Merge-Insertion Sort.

通过3向比较，真正的最佳答案将是做一个有趣的研究项目。但是，您可以使用贪婪算法通过找到3个元素来使 close 闭合，使最可能出现的顺序尽可能地少。

With 3-way comparisons, a truly optimal answer will be a fun research project. But you can come close with a greedy algorithm by finding 3 elements such that the most likely order is as unlikely as possible.

精确计算太难了。但是贪婪的方法如下。对于每个元素，计算已知还有多少个更好的元素，以及已知有几个更差的元素。将它们排序为优先级列表，依次是最不知名的比较，优劣之间的最小差异，最不知名的最差，原始顺序。

An exact calculation will be too hard. But a greedy approach goes as follows. For each element, calculate how many others are known to be better, and how many are known to be worse. Sort them into a priority list by, "fewest known comparisons" then "smallest difference between better/worse" then "fewest known to be worse" then "original order".

在此优先级列表中获取第一个元素。.在列表中向下查找从未与之进行比较的第一个元素。继续向下寻找从未与任何一个相比的第一个。如果找不到一个，请寻找一个从未与第一个进行比较的，但可能已经与第二个进行比较的一个。失败了，只需比较一下货币对。

Take the first element in this priority list.. Look down the list for the first that it has never been compared with. Continue down looking for the first that has never been compared with either. If you fail to find one, instead look for one that has never been compared with the first but may have been compared with the second. Failing that, just compare the pair.

一个示例可能会有所帮助。让我们尝试通过3种方式对 2、4、1、3、5 进行排序。没有任何信息，我们一开始只是接受我们的命令。我们先比较 2，4，1 ，然后发现它是 1,2,4 。至此，我们知道：

An example may help. Let's try to sort 2, 4, 1, 3, 5 with 3 way comparisons. With no information, we at first just take the order we were given. We start by comparing 2, 4, 1 and find out that that is 1, 2, 4. At this point we know:

1: better: 2, 4; worse:
2: better: 4; worse: 1
3: better: ; worse:
4: better: ; worse: 1, 2
5: better: ; worse:

现在，我们按最少的比较进行排序，然后按最佳和较差数目​​之间的最小差排序，然后按最小排序更糟的是原始顺序。这给出了 3、5、2、1、4 。没有比较 3、5、2 ，因此我们接下来要做的就是获得 2、3、5 。现在我们知道：

Now we sort by fewest comparisons, then smallest difference between number of best and worse, then fewest worse, then original order. This gives 3, 5, 2, 1, 4. None of 3, 5, 2 have been compared, so we do that next to get 2, 3, 5. We now know:

1: better: 2, 3, 4, 5; worse:
2: better: 3, 4, 5; worse: 1
3: better: 5; worse: 1, 2
4: better: ; worse: 1, 2
5: better: ; worse: 1, 2, 3

现在，我们的优先级排序为 4 ，3、5、2、1 。我们取 4，5 。一切都已与其中之一进行了比较，因此我们转到 3 ，因为它尚未与 4 进行比较。这三个比较 3、4、5 。现在我们知道：

And now our priority sort gives us 4, 3, 5, 2, 1. We take 4, 5. Everything has been compared to one of them so we go to 3 because it has not been compared to 4 yet. These three compare 3, 4, 5. We now know:

1: better: 2, 3, 4, 5; worse:
2: better: 3, 4, 5; worse: 1
3: better: 4, 5; worse: 1, 2
4: better: 5; worse: 1, 2, 3
5: better: ; worse: 1, 2, 3, 4

我们用排序了5样东西3 3向比较。从理论上讲，这是我们可以做的最好的事情。 （随着您增加数字，我怀疑您也会经常这样做。但是它应该优于二元策略。）

And we sorted 5 things with 3 3-way comparisons. Which is theoretically the best that we could do. (As you increase the number, I doubt you will often do as well. But it should beat a binary strategy.)

这篇关于排名-最小化成对比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！