Leg*_*end 4 language-agnostic algorithm
我有一组数字要比较.假设我必须从用户那里得到这个比较.我可以选择问他一个由2个数字组成的问题或者3个数字的4个数字.例如,我可以问以下任何一个问题:
我的目标是最大限度地减少我在一些组合中询问用户的问题数量,最终会让我对集合中的所有数字进行排序...例如,如果只有4个数字{2,3,4,5我可以问他第三类问题,我给他4个数字进行比较.但是在我为此设计的生态系统中,用户对长期问题感到恼火,所以我想尽量减少这类问题的数量.因此,如果每个问题都有一个特定的权重,我试图找到一种方法来最终获得所有数字的排序,但同时给用户带来最小的麻烦.
有没有一种解决这个问题的好方法？有没有人认为这属于一般类问题,或者我只是把它变得太复杂了？有什么建议？
我们试验吧,不管你.
1.例子
让我们来看看{A,B,C,D}并对其进行排序.
解决方案1:按套装
{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)目标是什么？
目标应该是最小化用户的问题数量还是应该最小化用户的工作？因为很明显,用户更难回答第一个解决方案的问题......
3.建模
可以将问题建模为"图形"问题.
您从一组{A,B,C,D}表示要测试的值的节点开始.
对集合进行排序等效于计算链接这些节点的最小定向边缘集合,以便给定任意两个节点,路径从一个节点引导到另一个节点.我坚持要求最低限度.
例如,如果我有2个边缘:B>A然后B>C,如果我发现A>C我将删除,B>C因为我可以通过传递性推断它.重要的属性是,如果没有两个节点是等价的,那么结果边集的基数是节点集的基数减1.在我的例子中(给定4个节点)它将是3.
因此,一个oracle(或一个非常幸运的人)只能提出3个问题,然后建立这个图表......这就是我们应该努力的方向.
4.如何解决这个问题？
好的,我们假设我们没有2个等效元素.这意味着如果A>B是假的,那么我可以推断B>A......
为了表示我们的小图,让我们采用一个数组:
A B C D
D . > . # . represent the unknown
C . >
B > # < and > have their usual meaning...
A
由于对称性,我们只需要一个三角形.
通过计算.我们可以看到未知关系数量的数量,理想的解决方案是.在向用户询问尽可能少的问题的同时摆脱所有这些.
因此,一个好问题就是一举一动.尽可能地删除.
我的问题
因此,我有另一种类型的问题:
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个关系
第三个问题要求更详细的答案,但它更适合合并情况.在合并的情况下,它与要求对元素进行排序一样高效,因为它准确地询问了我们在电路板中不知道的3种关系.
7.结论
您现在在框中有4个问题:
(对可以视为大或旋转的退化情况)
假设每个问题都给出n-1了n节点的关系,你可以尝试估计用户回答问题所需的时间T(n),然后找到n最大化的问题T(n)/n;)