algorithm - 不精确比较的不完全排名算法

Question

摘要

我正在寻找一种对对象进行排名的算法。可以比较两个对象。但是，这些比较是现实世界中可能存在缺陷的比较。另外，我更关心找出最好的对象，而不是找出最差的对象。

激励：

认为我正在科学地评估材料。我结合两种材料。我想找到进行深度测试的最佳工作材料。因此，我不在乎那些没有前途的材料。但是，每种测试都可能是假阳性或在这两种特定材料之间存在异常。

精确问题：


有无限的对象池。
两个对象可以相互比较。比较两个对象是资源昂贵的。
考虑其他对象是很昂贵的资源。因此，只有对象可以完全排名，才应将其包括在评估中。
在测试对象池中找到最好的对象非常重要。如果对象位于下半部分，则不必找出它在下半部分的位置。找出准确排名的重要性是最重要的梯度。
在大多数情况下，如果A> B且B> C，则可以安全地假设A>C。有时，存在误报。有时A> B和B> C和C>A。这不是抽象的数学空间，而是实际的测量结果。
开始时，不知道允许进行多少比较。该算法被授予进行其他比较的权限，直到没有进行比较为止。因此，必须做出包括附加对象或测试更多已测试对象的决定。


激发更多深度：

想象一下，您要雇用一组拳击手。您对评估拳击手一无所知，但可以要求两名拳击手互相搏斗。世界上有无限数量的拳击手。但是让他们飞起来很昂贵。理想情况下，您想雇用n名最佳拳击手。实际上，您不知道拳击手是否会接受您的报价。另外，您不知道其他拳击俱乐部的竞争力。您将只向最好的n个拳击手提供要约，但必须准备知道向其发送下一个n个拳击手的要约。只得到最差的拳击手是不太可能的。

某些方法

我可以想到以下方法。但是，它们都有缺点。我觉得应该有一个更好的方法。


使用传统排序算法


可以使用传统的排序算法。

退税：
-误报可能会严重抛出算法的正确性。
-排序算法将花费一半的时间对数据包的下半部分进行排序，这并不重要。
-排序算法始于所有项目。有了这个问题，我们可以进行第一次测试，而不知道是否可以进行第二次测试。我们可能最终只能进行两次测试。否则我们可能被允许做一百万次测试。


使用比赛算法
有用于比赛的算法。例如，每个人都有第一场比赛。第一场比赛的胜者将进入下一轮。有多种锦标赛策略可以解决人们在第一天比赛中表现不佳或与冠军配对的问题。


退税：
-这看起来很有希望。困难在于找到一个允许一次增加一名球员的比赛，因为我们可以进行更多的比较。似乎应该有一个比标准锦标赛算法更好的高度专业化的解决方案。


二进制搜索
我们可以从两个对象开始。每次添加对象时，我们都可以使用二进制搜索来找到其在排名中的位置。因为顶部更重要，所以我们可以使用加权二进制搜索。例如。而不是测试中点，而是测试顶部1/3的点。


退税：
-该算法无法纠正误报。如果在早期的顶部出现误报，则可能会使其余的测试产生偏差。


输赢数
得失可以计算在内。该算法将根据损失最少的优先级和获胜最多的第二优先级来选择测试对象。这将专注于测试最佳对象。如果一个对象的损失为零，它将成为测试的重点。它可能很快失去优先级，或者失去优先级，或者因为它可能是最佳候选人而接受更多测试。


退税：
-这种方法非常不错，因为它可以纠正误报。它还允许轻松地将更多对象添加到测试池。但是，它并不认为与顶部对象的胜利比对底部对象的胜利重要得多。因此，浪费了比较。


图形
所有对象都可以添加到图形中。该图可以展平。


退税：
-我不知道如何展平这样一个混乱的图形，它可能具有周期和不明确的末端节点。可能存在多个不败的对象。在这样一个凌乱的图表中，如何选出一个赢家？谁会知道哪个比较最有价值？


计分
由于获胜取决于失败者的排名，因此可以给获胜分配一个分数。说A> B，表示A得1分。如果C> A，则C得到2分，因为A得到1分。最后，根据对象具有的分数对其进行排名。


退税
-该方法似乎很有希望，因为很容易将新对象添加到测试对象池中。它还考虑到，与顶级对象的获胜应该算得更多。我想不出一种确定要点的好方法。第一次比较，获得1分。一旦池中有10,000个对象，平均获胜将获得5,000点。两项测试的奖励应大致相等。后来的比较压倒了先前的比较，并在不应该进行的比较中将其忽略。

有谁有解决这个问题的好主意？

Answer 1

我将为对象搜索一个易于计算的值，可以在对象之间进行比较以给出足够好的阶数近似值。您可以准确地将每个新对象与当前对象进行比较，然后使用计算出的值将失败者插入到其余列表中。

最好的永远是准确的。其余的排序取决于您的“值”。