尋找名人羣體的線性算法，不是單名人

假設我們有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

尋找名人羣體的線性算法，不是單名人

回答

相關問題