algorithm - 算法:有没有解决比较的好方法？

Question

我有一组数字要比较。假设我必须从用户那里得到这个比较。我可以选择问他一个由2个数字组成的问题，或是3个由4个数字组成的问题。例如，我可以问下列任何问题：
哪个数字更大？2或4
哪个数字更大？2或3或4
哪一个数字更大？2或3或4或5
我的目标是尽量减少我向用户提出的问题的数量，以某种组合的方式，最终给我一个集合中所有数字的顺序…例如，如果只有4个数字{2,3,4,5}，我就可以问他第三类问题，我给他4个数字进行比较。但在我为之设计的生态系统中，用户会对冗长的问题感到恼火，所以我希望尽量减少此类问题的数量。因此，如果每个问题都有特定的权重，我将尝试找出一种方法，最终获得所有数字的顺序，但同时将用户的麻烦降到最低。
有解决这个问题的好办法吗？有人认为这是一个普遍的问题，还是我只是把它变得太复杂了？有什么建议吗？

Answer 1

让我们做个实验，好吗？
一。例子
让我们看看{A,B,C,D}并对其进行排序。
解决方案一：按套
大于{A,B,C,D}>B（因此B>A，B>C和B>D）
大于{A,C,D}>D（因此D>A和D>C）
大于{A,C}>A（因此A>C）
总订单[B,D,A,C]
解决方案2：成对
大于A和C>A之间（因此A>C）
大于B和D>B之间（因此B>D）
大于D和A>D
总订单[B,D,A,C]
有什么发现？很明显，成对比较困难，这里我选择了它们，这样合并就很容易了（没有）。
2.评论
a）总订购量
>只适用于总排序：即对于一组A或B的两个给定元素A>B和B>A。如果这两个关系都不成立，那么A和B是等价的。
解决方案1方法的问题在于，如果向用户呈现{A,B,C,D}和A以及B是等价的，并且大于C和D。答案应该是什么？
b）传递性
>关系是可传递的，这意味着如果A>B和B>C则A>C。使用这个事实是很重要的，因为您可以在不询问用户的情况下推断出两个元素之间的关系。
c）目标是什么？
目标应该是最小化对用户的问题数量还是最小化用户的工作？因为很明显，用户很难回答第一个解决方案中的问题…
三。建模
我们可以把这个问题建模为“图”问题。
首先是一组节点{A,B,C,D}，它们表示要测试的值。
对集进行排序相当于计算链接这些节点的最小定向边集，以便给定任意两个节点，一条路径从一个节点指向另一个节点。我坚持最低限度。
例如，如果我有两条边：B>A和B>C，那么如果我发现A>C，我将删除B>C，因为我可以通过传递性来推断它。重要的特性是，如果没有两个节点是等价的，则结果边集的基数是节点集的基数减去1。在我的示例中（给定4个节点），它将是3。
一个甲骨文（或一个非常幸运的人）将因此只能问3个问题，但建立这个图表…这是我们应该争取的。
四。如何解决这个问题？
好吧，假设我们没有2个等价元素。这意味着如果A>B是假的，那么我可以推断出B>A。
为了表示我们的小图，我们取一个数组：

  A B C D  
D . > .      # . represent the unknown
C . >        
B >          # < and > have their usual meaning...
A 

因为对称，我们只需要一个三角形。
通过计算 .的数量，我们可以看到未知关系的数量，理想的解决方案是在尽可能少地向用户提问的同时去掉所有这些 .。
因此，一个好问题是一次就尽可能多地删除 .。
5个。我的问题
因此，我有另一类问题：

Select the elements lower than "D" in the following {A,B,C}: _

这个问题让人感觉更好的是什么是更大的…因为我明确的目标是那些我想知道的关系（ D?A， D?B和 D?C），而更大的保证是我将获得同样多的关系，但我无法提前知道是哪一个。
我试图最大化问题的有用性。
当然，懒惰是没有余地的：在利用问题的结果时，考虑及物性仍然很重要。
6。探索更大的集合
对于较大的集合，您可以对元素进行分组，然后稍后再进行合并，但是合并操作总是一个混乱的操作：您可能会得到您已经知道的答案。不过，对于我的小问题来说，这是一个很好的练习：
给定2个有序（不相交）集： [A,B,C,D,...]和 [R,S,T,U,...]让我们看看工具箱中的3个问题：
哪个更大： A或 R？_
{A,B,R,S}的最大元素是什么？_
哪些元素大于 A中的 {R,S,T}？_
给出1个关系
给出2个关系：其中3个关系1已知
给出3种关系
第三个问题需要更详细的答案，但它更适合合并情况。在合并的情况下，它和要求对元素进行排序一样有效，因为它只要求董事会中我们不知道的3个关系。
7号。结论
您现在有4个问题：
排序：将下列元素从大到小排序{a，b，c，d}？_
pivot：在这个集合{b，c，d}中哪些元素大于a？_
greater：这个集合{a，b，c，d}中哪个元素更大？_
配对：A和B中哪个元素更重要？_
（对可以看作是大的或轴的退化情况）
假设每个问题给出了 n-1节点的 n节点关系，你可以尝试计算一个用户回答一个问题[cc]所花费的时间，然后找到最大化 T(n)的 n。