寻找名人群体的线性算法，不是单名人

假设我们有N人并且有可能是里面的一群名人。寻找名人群体的线性算法，不是单名人

每个人都知道每个名人，每个名人都知道其他名人。

如果给出的功能know x y其中returns true or false，确定名人群。

这个问题是标识一组名人的，它是不识别人当中唯一的名人，如http://www.geeksforgeeks.org/the-celebrity-problem/。

使用蛮力很容易。我可以构建N个人的所有可能的子序列并用条件过滤它们（每个人都知道每个名人，每个名人只知道其他名人）。

另外我知道必须只有一个名人组或没有。

证明：

假设我们有两个名人组，C1和C2。因为每个人都知道C1的ci，所以每个来自C2的cj也知道ci;对称地，每个ci知道cj;所以C1和C2实际上属于一个组。所以我们至多有一个名人团体或没有。

关于可能的任何想法线性算法？

编辑

有可能是一组名人的，有可能是没有。

来源

2014-01-07 Jackson Tale

一位名人是否知道其他名人？在任何一个名人都知道每个其他名人？ – isick

@isick是的，正好 –

一个非名人是否也可以知道其他非名人的数量？ – Dukeling

是的，这是可能的O（N）（但请参阅下面的第二编辑）。这里有一个算法。

枚举从0到N-1的所有N个人。

int find_a_celebrity() 
{ 
    int C = 0; // C is a potential celebrity 
    for(int i=0 ; i<N ; ++i) 
     if(!know(i,C)) // C is not a celebrity nor are all j<i, but i might be. 
     C = i; 
    for(int i=0 ; i<N ; ++i) // Loop a second time to check everyone knows C. 
     if(!know(i,C)) return -1; 
    return C; 
} 
int C = find_a_celebrity();

如果C==-1那么没有名人。否则集{ y | know(C,y) }是所有名人的集合。总而言之，这通过所有N个人最多进行3次迭代，因此在时间O(N)中发现。

编辑：

// Output the set of celebrities 
if(C == -1) std::cout << "There are no celebrities."; 
else for(int i=0 ; i<N ; ++i) if(know(C,i)) std::cout << i << ' '; 
std::cout << std::endl;

编辑2：

有两种解释了这个问题：

名人的定义是，他们每个人都知道。由于这个问题的限制，所有的名人只知道其他名人。
名人的定义是，他们是众所周知的，名人只知道其他名人。

上述算法解决了情况＃1。这也适用于案例＃2，只要我们可以假设至少存在一个名人。否则，我们将不得不验证潜在名人的名单只相互认识，这需要O(N*M)时间，其中M是潜在名人的数量。

来源

2014-01-07 23:24:24 Matt

可以请你填写代码吗？ –

@JacksonTale完成。希望有所帮助。 – Matt

所有非名人不一定彼此认识，所以我不认为这会起作用（你从C =非名人A开始，非名人B不知道A，因此你将C分配给B，然后返回-1，因为每个人都不知道B）。 – Dukeling

编辑：我没有仔细阅读问题陈述。您没有所有边的列表，我们假设我们无法在线性时间内生成它。

这里的关键是每个人都知道每个名人。将这个问题表述为一个带有V个顶点（名人）和E个边（关系）的连接它们的定向邻接图。

遍历列表E计算每个人知道多少次。名人被称为V-1次;其他人都是非名人。运行时间应该是O（E）。

来源

2014-01-07 22:41:56 Daniel

我也想过一个图，但构建图将是昂贵的（已有关系的二次数）。 – Dukeling

严格地说，你只需要名人名单和关系列表;您不需要实际的矩阵或二维数组来实现图形。 – Daniel

是的，但是你没有关系列表，你只有一个函数来确定给定两个人的关系。 – isick

-1

让candidates成为所有n人的列表。构建所有人的循环：

1 -> 2 -> ... -> n -> 1。

现在，逐个检查knows k,k+1。如果真的比k = k+1继续。如果knows k,k+1 == False,然后k+1不是名人所以请将他从candidates中删除，并检查k,k+2。

在最后size(candidates)转弯没有删除任何人的时候结束了。

证明：

如果在列表中的名人，那么：

他将永远不会被删除
一旦我们找到他，我们走的更远最后名人
算法将删除所有非名人的'最后一个'后，直到我们得到另一个名人，然后我们回到2.

最后我们会得到一个名人的循环。

如果列表中没有名人，请按照@ Matt的回答。

来源

2014-01-07 23:15:08

这是不正确的。假设0不知道1或2，1也不知道0。在你的算法中，0是唯一剩下的，但它不是正确的答案 –

如果0不知道1，那么1不是名人，我们可能会删除他 - 他提供的信息在我的算法中是多余的。现在，如果0停留在周期中，并且至少有1名名人，那么在某点0将被删除。如果周期中没有名人，那么与**“里面有一群名人”**（我认为它的大小是积极的）是矛盾的。 –

Ps。如果我们包括根本没有名人的可能性，那么解决这个问题是不可能的。对于每个有名人的群体，我们都可以用**完全相同的关系“知道**”来构建另一个群体，而没有名人。所以我们无法区分这两种情况。 –

作为名人是不知道状态。正常是知道而不知道的状态。因此，每个人比较旁边的人他们会看起来像：

foreach person in persons 
{ 
    knows = know(person, next_person) 
    isknown = know(next_person, person) 

    if knows and !isknown then normal 
    if !knows and isknown then celeb 
    if !knows and !isknown then normal 
    if knows and isknown then friends.add(person) 

    foreach friend in friends 
    { 
     alsoknows = know(person, friend) 
     if !alsoknows then normal; break; 
    } 
}

来源

2014-01-07 23:40:37

构建一个朋友的子列表是一个有趣的方法。我认为你的标准有点不合适，因为你不能确定那个人是名人，只是因为另一个人知道他们;每个人都必须了解他们但是创建子列表的想法仍然很有趣。但是，您必须在“朋友”列表中循环嵌套才能确定您的最终列表是详尽的和排他性的。在所有人都知道next_person的情况下，你的朋友列表将成为起始“人员”列表的复制品，这意味着它仍然是O（N^2） – isick

是的，我的解决方案存在缺陷。我只留下了它，因为我认为它可能会贡献一些概念。我的妻子告诉我停止试图解决这个问题:) –

@isick我应该补充一点，你可以肯定地说有人是名人，因为另一个人知道他们，他们不认识那个人。 –

考虑所有N *（N-1）的评估可能是知道真实的情况下（X，Y）。在这种情况下，所有N人都是名人。接下来，考虑知识（x，y）的N *（N-1）个评价中除N中的一个都是真的情况。根据this comment by the asker，我预计我们应该将这种情况解释为零名人。为了区分这两种情况，您需要评估所有可能的N *（N-1）对。

来源

2014-01-08 01:00:22 mhum

寻找名人群体的线性算法，不是单名人

回答

相关问题