Soluzione ottimale per la "celebrità" algoritmo

Question

Tra n persone, una "celebrità " è definito come qualcuno che è conosciuto da tutti, ma non conosco nessuno. Il problema è identificare la celebrità, se ne esiste una, chiedendo solo la domanda del modulo "Scusami, conosci la persona laggiù?" (L'ipotesi è che tutte le risposte siano corrette, e anche quella celebrità risponderà anche.) L'obiettivo è ridurre al minimo il numero di domande.

C'è una soluzione dell'ordine inferiore all'ovvio O(n^2) qui?

Answer 1

Utilizzando l'analisi del problema di celebrità here

soluzione forza bruta. Il grafico ha al massimo spigoli n(n-1) e possiamo calcolarlo ponendo una domanda per ogni margine potenziale. In questo punto , possiamo verificare se un vertice è un sink calcolando il suo indegree e il suo outdegree. Questa soluzione a forza bruta chiede le domande n(n-1) . Successivamente mostriamo come fare con al massimo 3(n-1) domande e posto lineare.

Una soluzione elegante. Il nostro algoritmo consiste in due fasi: nella fase di eliminazione, eliminiamo tutti tranne una persona dall'essere la celebrità ; nella fase di verifica verifichiamo se questa persona rimasta è davvero una celebrità. La fase di eliminazione mantiene un elenco di possibili celebrità. Inizialmente contiene tutte le persone n . In ogni iterazione, eliminiamo una persona dall'elenco. Noi sfruttiamo la seguente osservazione chiave: se la persona 1 conosce la persona 2, , la persona 1 non è una celebrità; se la persona 1 non conosce la persona 2, allora la persona 2 non è una celebrità. Quindi, chiedendo alla persona 1 se conosce persona 2, possiamo eliminare la persona 1 o la persona 2 dall'elenco di celebrità possibili. Possiamo usare questa idea ripetutamente per eliminare tutte le persone tranne una, per esempio la persona p. Ora verifichiamo con la forza bruta se p è una celebrità: per ogni altra persona i, chiediamo persona p che lo sappia persona i, e chiediamo persone i se sanno persona p. Se la persona p risponde sempre no, e le altre persone rispondono sempre sì , dichiariamo la persona p come la celebrità. Altrimenti, noi concludiamo che non c'è celebrità in questo gruppo.

Answer 2

1. Divide tutte le persone in coppia.

2. Per ogni coppia (A, B), chiedere A se conosce B.

   • se la risposta è sì, A non può essere la celebrità, scartarlo.
   • se la risposta è no, B non può essere la celebrità, scartarlo.

   Ora, solo la metà delle persone rimane.

3. Ripetere da 1 fino a quando rimane una sola persona.

Costo O (N).

Answer 3

Ecco algoritmo O (N) tempo

1. Spingere tutti gli elementi in stack.
2. Rimuovi primi due elementi (dicono A e B), e mantenere A se B conosce A e A non sa B.
3. Rimuovi sia A, B è sia conoscono tra loro o che non si conoscono

Answer 4

Ecco la mia soluzione.

#include<iostream> 
using namespace std; 
int main(){ 
    int n; 
    //number of celebrities 
    cin>>n; 
    int a[n][n]; 
    for(int i = 0;i < n;i++){ 
     for(int j = 0;j < n;j++){ 
      cin>>a[i][j]; 
     } 
    } 
    int count = 0; 
    for(int i = 0;i < n;i++){ 
     int pos = 0; 
     for(int j = 0;j < n;j++){ 
      if(a[i][j] == 0){ 
       count = count + 1; 
      } 
      else{ 
       count = 0; 
       break; 
      } 
     } 
     if(count == n){ 
      pos = i; 
      cout<<pos; 
      break; 
     } 
    } 

    return 0; 
}