求解n人中最多(n/2)-1个说谎者的最优识别算法

问题背景 #

n个人组成的群体中，最多存在t个说谎者（已知t < n/2）。其中诚实者始终说真话，说谎者始终说假话。我们仅能通过询问任意两人X：“Y是说谎者吗？”来获取“是”或“否”的回答，目标是用最少的询问步骤识别出所有说谎者。

最优算法步骤 #

步骤1：筛选出一名诚实者作为基准 #

• 初始化一个空的候选栈
• 依次遍历群体中的每一个人P：
  • 若栈为空，将P压入栈中
  • 若栈不为空，取出栈顶元素Q，询问Q：“P是说谎者吗？”
    • 若回答为是：说明Q和P中至少有一人是说谎者，将两人全部丢弃（由于t < n/2，丢弃一对后剩余人群中诚实者仍占多数）
    • 若回答为否：说明Q和P身份一致（同为诚实者或同为说谎者），将P压入栈中
• 遍历完成后，栈内所有人身份完全相同；又因为诚实者在群体中占多数，因此栈内所有成员都是诚实者，任选其一作为基准诚实者即可。

步骤2：用基准诚实者验证所有成员 #

• 对群体中的每一个人，询问基准诚实者：“这个人是说谎者吗？”
  • 回答为是，判定该人为说谎者
  • 回答为否，判定该人为诚实者

算法复杂度分析 #

• 步骤1的询问次数最多为n-1次（每处理一个新成员最多触发一次询问）
• 步骤2的询问次数固定为n次
• 总询问次数为2n-1次，这是当前已知的最优复杂度——因为每个个体至少需要被验证一次，而筛选基准的步骤无法通过更少的询问保证找到可靠的诚实者。

内容的提问来源于stack exchange，提问作者roku675