具有概率成对比较的模糊排序算法

Question

假设有 n 个玩家玩一个 pair-wise 游戏。每场比赛的结果主要取决于两位选手的实力，也有一点运气。

如何用较少的局数获得更准确的各玩家排名？

Answer 1

在强者总是获胜的理想情况下，您可以使用合并排序或快速排序等比较排序对玩家列表进行排序，甚至可以使用排序网络来尽可能减少比较次数。由于这不是理想的情况(涉及运气)，这些算法可能由于违反传递属性而无法产生正确的结果，但是我相信有一种方法可以检测并纠正许多运气击败力量的情况，如下所述:

首先，使用诸如合并排序之类的方法对玩家进行排序(违反传递属性不会导致无限循环)。将执行的比较转换为有向图，其中每条边都指向比赛的获胜者。将此原始图称为 G。现在，对于 G 中的每对连接边，通过比较“结束”顶点添加第三条边(创建三角形)，并将更新后的图放入 G'(保持 G 不变) .完成此操作后，检查 G' 中的循环 - 如果存在循环，则表示违反了传递属性。要解决它们，请将循环的成员与图中的其他成员进行比较，这不可避免地会产生更多的循环。这些周期之间的相互优势很可能是罪魁祸首，我们可以假设这是一次“幸运”的胜利。将所有这些边缘标记为否定。

一旦解决了所有循环，您可能会发现由于某些歧义，您无法对图进行拓扑排序。根据需要进行比较以解决歧义，但请注意，这些新比较还不能保证其正确性(目前)。为了解决这个问题，用图 G1 中的这些新边递归地重复上述过程，直到生成一个明确的图。将这些边插入到G中，进行拓扑排序。

如果您愿意，您可以修改上述算法以获得更快的速度或更高的准确性。为了准确起见，只需将每条边与更多冗余边进行比较，以更可靠地揭示和阐明循环。为了更快的速度，测试更大的循环组——而不是试图找到长度为 3 的循环，比较说的“末端”——每 6 个边缘找到长度为 7 左右的循环。如果循环/“幸运获胜”足够罕见，您可以通过一次检查多个边来节省大量时间，尽管 a) 如果两个违规“相互抵消”，您可能会忽略一个循环，并且 b) 您仍然会花费 a)大量时间在更大的循环中定位特定的违规边缘。