摘要
我正在寻找一种排列对象的算法。两个对象可以进行比较，但是这些比较可能存在缺陷。另外，我更关心找到最好的对象，而不是哪些是最差的。
激励：
想象一下，我正在科学地评估材料。我将两种材料组合在一起。我想找到最适合深入测试的最佳工作材料。因此，我不关心那些没有前途的材料。但是，每个测试都可能是假阳性或在那两种特定材料之间存在异常。
明确问题：
- 有一个无限的对象池。
- 两个对象可以相互比较。比较两个对象的成本很高。
- 考虑额外的对象会消耗资源。因此，只有当一个对象可以完全排名时，才应将其纳入评估范围内。
- 在被测试对象的池中找到最好的对象非常重要。如果一个对象处于底部一半，那么找出它在底部一半的位置并不重要。确定精确排名的重要性是一个梯度，其中顶部更为重要。
- 大多数情况下，如果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分。两次测试的奖励应该大致相等。后续的比较会压倒之前的比较，在不应该被忽略的情况下使其被忽略。
有没有人对解决这个问题有好的想法？