Problem pronalaženja zvezde

Problem pronalaženja zvezde je problem identifikacije zvezde u nekom skupu koji na osnovu postavljanja pitanja (Uz pretpostavku da sve osobe odgovaraju istinito na pitanja) određuje da li je neka osoba zvezda ili nije. Konkretno, za osobu A kažemo da je zvezda ukoliko u nekom skupu S sve osobe poznaju osobu A, a osoba A ne poznaje ni jednu drugu osobu. Pitanja su tipa: "Izvinite, da li poznajete onu osobu?". Cilj je minimizovati broj postavljenih pitanja. Neka u skupu S ima N osoba, tada imamo N(N-1)/2 parova, pa je u najgorem slučaju potrebno postaviti N(N-1) pitanja, ako se pitanja postavljaju bez neke strategije.

Preformulisano, problem se može posmatrati grafovski. Formiramo usmereni graf sa čvorovima koji odgovaraju osobama, u kome grana od osobe A ka osobi B postoji ako A poznaje B. Zvezda odgovara ponoru grafa, čvoru u koji ulazi n − 1 grana, a iz koga ne izlazi ni jedna grana. Jasno je da graf može imati najviše jedan ponor. Ulaz problema se opisuje n × n matricom povezanosti M, čiji elemenat M_ij je jednak 1 ako osoba i poznaje osobu j, odnosno 0 u protivnom; dijagonalni elementi su jednaki nuli.

Problem

Definicija problema

Data je n×n matrica povezanosti M. Ustanoviti da li postoji indeks i, takav da su u M svi elementi i-te kolone (sem i-tog) jednaki 1, i da su svi elementi i-te vrste jednaki 0.

Opis rešenja

Bazni slučaj sa dve osobe je jednostavan. Posmatrajmo kao i obično razliku između problema sa n − 1 osobom i problema sa n osoba. Pretpostavljamo da znamo da pronađemo zvezdu među prvih n − 1 osoba indukcijom. Pošto može da postoji najviše jedna zvezda, postoje tri mogućnosti:

1. zvezda je jedna od prvih n − 1 osoba;
2. zvezda je n-ta osoba;
3. zvezda ne postoji.

Prvi slučaj je najjednostavniji: treba samo proveriti da li n-ta osoba poznaje zvezdu, odnosno da li je tačno da zvezda ne poznaje n-tu osobu. Preostala dva slučaja su teža, jer da bi se proverilo da li je n-ta osoba zvezda, treba postaviti 2(n − 1) pitanja. Ako postavimo 2(n − 1) pitanja u n-tom koraku, onda će ukupan broj pitanja biti n(n − 1), što hoćemo da izbegnemo.

Ideja je da se problem posmatra "unazad". Pošto je teško identifikovati zvezdu, pokušajmo da pronađemo osobu koja nije zvezda: u svakom slučaju, broj ne-zvezda mnogo je veći od broja zvezda. Ako eliminišemo nekoga iz razmatranja, paramentar n koji definiše veličinu problema smanjuje se na n−1. Pri tome uopšte nije bitno koga ćemo eliminisati! Pretpostavimo da osobu A pitamo da li poznaje osobu B. Ako A poznaje B, onda A nije zvezda, a ako pak A ne poznaje B, onda B nije zvezda. U oba slučaja se jedna osoba eliminiše postavljanjem samo jednog pitanja!

Ako se sada vratimo na tri moguća slućaja pri prelasku sa n − 1 na n, vidimo da je novost u tome da n-tu osobu ne biramo proizvoljno. Eliminacijom osobe A ili B problem svodimo na slučaj sa n−1 osobom, pri čemu smo sigurni da do slučaja 2. neće doći, jer eliminisana osoba ne može biti zvezda.

Ako je nastupio slučaj 3, odnosno nema zvezde među prvih n − 1 osoba, onda nema zvezde ni među svih n osoba. Ostaje prvi slučaj, koji je lak: ako među prvih n − 1 osoba postoji zvezda, onda se sa dva dopunska pitanja može proveriti da li je to zvezda i za kompletan skup. Ako nije, onda nema zvezde.

Algoritam se sastoji u tome da pitamo osobu A da li poznaje osobu B i eliminišemo ili osobu A ili osobu B, zavisno od dobijenog odgovora. Neka je eliminisana npr. osoba A. Indukcijom (rekurzivno) se pronalazi zvezda među preostalih n − 1 osoba. Ako među njima nema zvezde, rešavanje je završeno. U protivnom, proverava se da li je tačno da A poznaje zvezdu, a da zvezda ne poznaje A.

Složenost

Vremenska složenost algoritma je O(n).

Preciznije: Postavlja se najviše 3(n − 1) pitanja: n − 1 pitanja u prvoj fazi da bi se eliminisala n − 1 osoba, i najviše 2(n − 1) pitanja za proveru da li je preostali kandidat zvezda. Takođe, primetimo da veličina ulaza nije n, nego n(n − 1), tj. broj elemenata matrice.

Implementacija algoritma u C-u

Algoritam Superstar(Poznaju)
ulaz: Poznaju (n*n matrica ˇciji elementi su:
Poznaju[i][j]=1, ako osoba i poznaje osobu j
Poznaju[i][j]=0, ako osoba i ne poznaje osobu j , gde i,j=1..n )
izlaz: Superstar (njegova vrednost, ako postoji ili 0, ako ne postoji)
{
  i=1; /*osoba A*/
  j=2; /*osoba B*/
  Sled=3; /*sledeci koji ce se proveravati*/
  /*prva faza*/
  while (Sled <=n+1)
    {
      if (Poznaju[i][j]==1)
	i=Sled; /*i nije superstar, eliminacija*/
      else
	j=Sled; /*j nije superstar, eliminacija*/
      Sled=Sled+1;
    }
  /*nakon izlaska iz petlje ili je i=n+1 ili je j=n+1 */
  if (i==n+1)
    kandidat=j
  else
    kandidat=i
      /*druga faza*/
  Jeste=1; /*1 ako kandidat jeste superstar*/
  k=1; /*osoba iz skupa*/
  while ( (Jeste==1) && (k <=n) )
    {
      if (Poznaju[kandidat,k]==1)
	Jeste=0; /*kandidat nije superstar*/
      if (Poznaju[k,kandidat]==0 && k!=kandidat)
	Jeste=0; /*kandidat nije superstar*/
      k=k+1;
    }
  if (Jeste==1)
    Superstar=kandidat
    else
      Superstar=0; /*nema superstar-a*/
  return superstar
}

Spoljašnje veze

• c implementacija problema zvezde Архивирано на сајту Wayback Machine (19. јануар 2015)