“名人”算法的最佳解决方案

abhishek agarwal 发表于 Dev

阿比舍克·阿加瓦尔

在n人中，“名人”是指每个人都认识但不认识任何人的人。问题是通过仅问以下形式的问题来识别名人（如果存在的话）：“对不起，你认识那边的人吗？ ”（假设所有答案都是正确的，甚至名人也会也可以回答。）目标是减少问题的数量。

有没有比O(n^2)这里明显的顺序解决方案？

Nikos M.

在这里使用名人问题的分析

蛮力解决方案。该图最多具有n(n-1)边，我们可以通过为每个潜在边提出一个问题来进行计算。在这一点上，我们可以通过计算其入度和出度来检查顶点是否为宿。这种强力解决方案会提出n(n-1)问题。接下来，我们展示如何在最多3(n-1)问题和线性位置处执行此操作。

优雅的解决方案。我们的算法包括两个阶段：在淘汰阶段，我们将除了一个人之外的所有其他人淘汰为名人。在验证阶段，我们检查剩下的那个人是否确实是名人。淘汰阶段会保留一系列可能的名人。最初，它包含所有人n。在每次迭代中，我们从列表中删除一个人。我们利用以下主要观察结果：如果一个人1认识一个人2，那么这个人1就不是名人。如果一个人1不认识这个人2，那么这个人2就不是名人。因此，通过询问某人1是否认识某人2，我们可以消除某人1或某人2从可能的名人列表中。我们可以反复使用这个想法来消灭除一个人之外的所有人p。现在，我们用蛮力验证是否p是名人：对于其他每个人i，我们询问一个人p是否认识他i，并询问一个人i是否认识他p。如果某人p总是回答“否”，而其他人总是回答“是”，则我们将某人p称为名人。否则，我们得出结论，该群体中没有名人。