在n个人中最多找到(n/2)-1个骗子的最快算法

Question

这是我的场景:

这个问题是关于骗子和真相讲述者的问题,但它在确定复杂系统的哪些组件是好的(正常运行)和哪些是错误方面具有实际应用.假设我们有一个n人社区,我们知道一个整数t <n/2,它具有n个人中大多数人都是骗子的属性.这并不是说实际上有说谎者,而只是说最多只有说谎者.

我认为真相讲述者总是真实和正确,而骗子可能会说出错误答案或正确答案.

我们将通过连续挑选一对人来识别社区中的骗子,(X,Y)说,并问X:Y是骗子吗？回答是"是"或"否";

找到所有骗子的最佳算法(最小步数)是多少？

Answer 1

具有O(n)的最佳预期运行时间和优良常数的随机算法:

1. 随意选择
2. 询问其他人是否是骗子,直到一个选项("是"或"否")的权重> n/2(即直到超过n/2的人给出相同的答案).
   多数人决定(这是关键的观察!).
3. 如果他不是骗子,那么就对剩下的人进行迭代,只询问他是否每个人都是骗子(因为我们确定他说实话).
4. 如果他是个骗子,请将他带出小组,然后回到1.

关键的观察是,如果我们向每个人询问一个人,多数意见必须是正确的(因为大多数真相出纳员).稍微技术性的是,如果我们首先挑选一个非骗子并问别人,假设所有骗子撒谎,我们将达到50-50,那么我们如何决定哪一方说实话？这不是一个问题,因为如果我们首先选择一个非骗子,我们只能达到50-50,所以我们这个人确实是真理出纳员.

我们必须随机选择的预期人数是O(1)(这是这个问题中最可怕的部分,因为它可能是作业,我会跳过证明,但暗示一个简单的证明:几何分布) ,这意味着我们将在O(1)*O(n)时间内找到我们的真实出纳员和可靠的来源,从那里到另一个O(n)直到完成.总共,O(n).

Answer 2

关于这一主题的一篇好文章是Leslie Lamport的"拜占庭将军问题",可在http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf上找到.

对于那些感兴趣的人来说,这不是一个直接的解决方