Problema majoritatii

Cosmin Negruseri
18 noiembrie 2007

Cum blogul ar trebui sa fie orientat spre comunitatea infoarena am zis ca voi pune cate un post cu jmenuri de algoritmica din cand in cand. Sper sa va placa.

O problema clasica dar interesanta suna asa: Se dau n alegatori si fiecare voteaza pe unul dintre ei (toti alegatorii sunt in acelasi timp si candidati). Se stie ca unul dintre alegatori a primit cel putin n/2 + 1 voturi si acesta va obtine functia de presedinte. Gasiti un algoritm eficient pentru a determina viitorul presedinte.

Pentru a face putin mai interesanta problema, sa spunem ca sunt de ajuns n/3 + 1 voturi pentru a castiga alegerile si mai impunem restrictia ca exact unul dintre participantii la vot are mai mult de n/3 voturi.

Cum putem rezolva problema asta?

O solutie naiva, dar eficienta ar fi sa luam cateva nume votate aleatoare din sir. Cum castigatorul apare ca optiunea a multi votanti, daca alegem destul de multe valori din sirul optiunilor vom da cu probabilitate mare peste castigator. Cand alegem un nume aleator avem probabilitatea p > 1/3 ca am ales numele viitorului castigator. Deci daca alegem k valori vom avea un timp de executie de ordinul O(kn) pentru a verifica daca una dintre cele k valori e cea buna si probabilitatea de a gasi peresedintele mai mare de 1 - (1/3)^k.

Alta idee vine de la faptul ca in sirul sortat, elementele de valori egale vor fi pe pozitii consecutive. Astfel numele presedintelui va aparea pe cel putin n/3 + 1 pozitii consecutive. Deci numele presedintelui va aparea sigur pe cel putin una din pozitiile n/3 sau 2n/3 din sir. Astfel putem folosi un algoritm de selectie pentru a gasi in O(n) elementele de pe pozitiile n/3 si 2n/3 si apoi in O(n) putem verifica care dintre acesti doi candidati au castigat.

Daca n nu depaseste un milion, putem la fiecare pas sa incrementam pentru candidatul votat x numerele a[x / 1000] si b[x % 1000]. Acum pentru a determina candidatul castigator, gasim valoarea p cu a[p] > n/3 + 1 si valoarea q cu b[q] > n/3 + 1, iar castigatorul va fi p * 1000 + q.

O solutie ar fi sa folosim un hash map ce mapeaza numele alegatorilor la numarul de voturi castigate. Solutia aceasta este eficienta dar foloseste O(n) memorie suplimentara pentru structura de date.

Alta solutie este sa facem grupuri de cate trei alegatori cu opinii diferite asupra castigatorului, care se cearta intre ei pana pica jos. Dupa ce am facut toate grupurile de cate trei, ne mai pot ramane maxim doua optiuni de candidati, in caz contrar mai gaseam un grup de trei votanti cu optiuni diferite. E clar ca dupa ce am eliminat grupurile de cate trei, va exista unul dintre alegatori cu optiunea pentru viitorul presedinte intre alegatorii negrupati, pentru ca acesta e votat de mai mult de n/3 ori. Asa ca pentru a gasi presedintele este de ajuns sa verificam cele doua optiuni ai alegatorilor ramasi negrupati. Va prezint codul solutiei:

x <- -1, counter_x <- 0;
y <- -1. counter_y <- 0;
pentru i = 1,n
  daca counter_x = 0 atunci x <- a[i], counter_x <- 1;
  altfel daca counter_y = 0 atunci y <- a[i]; counter_y <- 1;
      altfel daca x = a[i] atunci counter_x++;
      altfel daca y = a[i] atunci counter_y++;
          altfel
           // am gasit un grup de trei alegatori cu optiunile
           // x, y si a[i] pe care il eliminam
           // x != a[i], y != a[i] si x != y
           counter_x--, counter_y--;
verificam daca x sau y este elementul cautat.

Problema poate parea artificiala, dar reformulata in aceea de a gasi in mod eficient queriuri foarte frecvente(ce apar de n/k ori) pentru un motor de cautare devine mai interesanta si practica. Postul a fost inspirat din articolul "Problema majoritatii votului" ce l-am publicat in Ginfo, iar partea cu cearta intre alegatori din R. S. Boyer, J. S. Moore A Fast Majority Vote Algorithm