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 Mij 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:
zvezda je jedna od prvih n − 1 osoba; zvezda je n-ta osoba; 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 }
Reference
Spoljašnje veze c implementacija problema zvezde
Категорија:Алгоритми Категорија:Конструкција алгоритама индукцијом