使用随机比较进行排序

Question

给出一个列表,其中对于每对元素(A,B),概率P(A> B),P(A <B)和P(A = B)是已知的,您如何确定最可能的排序排列？

Answer 1

让我们忽略P(A=B)(我们可以说它在<,>它们之间平均分配并将它们改为<=,>=).

现在,让我们看一个类似但直观上更容易的问题:

• 让我们找到最大的分配,这P(arr[0]<arr[1])*...*P(arr[i]<arr[i+1])*...*P(arr[n-2]<arr[n-1])是最大的.
• 这是一个更容易解决的问题,因为我们现在只考虑相邻的元素,(而不是例如P(arr[0]<arr[n-1])- 我们使用'less'信息.[证明缺少atm].

现在,我们希望最大化概率,这相当于最大化:

log{P(arr[0]<arr[1])} + ... + log{P(arr[n-2]<arr[n-1])}

这相当于最小化:

-log{P(arr[0]<arr[1])} - ... - log{P(arr[n-2]<arr[n-1])}

这是一个边缘有权重的TSP:

w(v,u) = -log(P(v<u))

然而,TSP是NP完全的,除非缺失的证明假设是错误的(仍在思考它......) - 这意味着没有已知的多项式解决这个问题,或者至少对相邻元素只有变化.