Проблем проналажења звезде

Проблем проналажења звезде је проблем идентификације звезде у неком скупу који на основу постављања питања (Уз претпоставку да све особе одговарају истинито на питања) одређује да ли је нека особа звезда или није. Конкретно, за особу А кажемо да је звезда уколико у неком скупу С све особе познају особу А, а особа А не познаје ни једну другу особу. Питања су типа: "Извините, да ли познајете ону особу?". Циљ је минимизовати број постављених питања. Нека у скупу С има Н особа, тада имамо Н(Н-1)/2 парова, па је у најгорем случају потребно поставити Н(Н-1) питања, ако се питања постављају без неке стратегије.

Преформулисано, проблем се може посматрати графовски. Формирамо усмерени граф са чворовима који одговарају особама, у коме грана од особе А ка особи Б постоји ако А познаје Б. Звезда одговара понору графа, чвору у који улази н − 1 грана, а из кога не излази ни једна грана. Јасно је да граф може имати највише један понор. Улаз проблема се описује н × н матрицом повезаности M, чији елеменат M_иј је једнак 1 ако особа и познаје особу ј, односно 0 у противном; дијагонални елементи су једнаки нули.

Проблем

Дефиниција проблема

Дата је н×н матрица повезаности M. Установити да ли постоји индекс и, такав да су у M сви елементи и-те колоне (сем и-тог) једнаки 1, и да су сви елементи и-те врсте једнаки 0.

Опис решења

Базни случај са две особе је једноставан. Посматрајмо као и обично разлику између проблема са н − 1 особом и проблема са н особа. Претпостављамо да знамо да пронађемо звезду међу првих н − 1 особа индукцијом. Пошто може да постоји највише једна звезда, постоје три могућности:

1. звезда је једна од првих н − 1 особа;
2. звезда је н-та особа;
3. звезда не постоји.

Први случај је најједноставнији: треба само проверити да ли н-та особа познаје звезду, односно да ли је тачно да звезда не познаје н-ту особу. Преостала два случаја су тежа, јер да би се проверило да ли је н-та особа звезда, треба поставити 2(н − 1) питања. Ако поставимо 2(н − 1) питања у н-том кораку, онда ће укупан број питања бити н(н − 1), што хоћемо да избегнемо.

Идеја је да се проблем посматра "уназад". Пошто је тешко идентификовати звезду, покушајмо да пронађемо особу која није звезда: у сваком случају, број не-звезда много је већи од броја звезда. Ако елиминишемо некога из разматрања, параментар н који дефинише величину проблема смањује се на н−1. При томе уопште није битно кога ћемо елиминисати! Претпоставимо да особу А питамо да ли познаје особу Б. Ако А познаје Б, онда А није звезда, а ако пак А не познаје Б, онда Б није звезда. У оба случаја се једна особа елиминише постављањем само једног питања!

Ако се сада вратимо на три могућа слућаја при преласку са н − 1 на н, видимо да је новост у томе да н-ту особу не бирамо произвољно. Елиминацијом особе А или Б проблем сводимо на случај са н−1 особом, при чему смо сигурни да до случаја 2. неће доћи, јер елиминисана особа не може бити звезда.

Ако је наступио случај 3, односно нема звезде међу првих н − 1 особа, онда нема звезде ни међу свих н особа. Остаје први случај, који је лак: ако међу првих н − 1 особа постоји звезда, онда се са два допунска питања може проверити да ли је то звезда и за комплетан скуп. Ако није, онда нема звезде.

Алгоритам се састоји у томе да питамо особу А да ли познаје особу Б и елиминишемо или особу А или особу Б, зависно од добијеног одговора. Нека је елиминисана нпр. особа А. Индукцијом (рекурзивно) се проналази звезда међу преосталих н − 1 особа. Ако међу њима нема звезде, решавање је завршено. У противном, проверава се да ли је тачно да А познаје звезду, а да звезда не познаје А.

Сложеност

Временска сложеност алгоритма је О(н).

Прецизније: Поставља се највише 3(н − 1) питања: н − 1 питања у првој фази да би се елиминисала н − 1 особа, и највише 2(н − 1) питања за проверу да ли је преостали кандидат звезда. Такође, приметимо да величина улаза није н, него н(н − 1), тј. број елемената матрице.

Имплементација алгоритма у C-у

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
}

Спољашње везе

• ц имплементација проблема звезде Архивирано на сајту Wayback Machine (19. јануар 2015)