In organizarea unei tabere sau a unei conferinte se pune mereu problema impartirii oamenilor care participa:
in camere
in grupuri de lucru
in functie de trainerul de la workshop
Am luat ca un caz particular o tabara, TechFriend Camp 2011, unde participantii se inscriu, isi trimit un CV, si apoi sunt sau nu acceptati. In final se conecteaza cu profilele de Facebook si Twitter.
Aplicatia mea descarca prietenii si paginile preferate din conturile de Facebook, si conturile pe care le urmaresc pe Twitter. Administratorul apoi seteaza:
numarul de oameni din grupuri
daca oamenii dintr-un grup pot fi prieteni (satisfactia este mai mare cand cunosti persoane noi)
procentul de baieti si fete (intr-un grup de workshop acest procent este bine sa fie 50%, in schimb daca ar trebui sa fie oamenii impartiti in camere, acest procent va fi de 100%).
Si daca persoana respectiva nu are cont de Twitter sau de facebuc? Eu pana acum o luna daca nu faceam un rămăşag cu un coleg si il pierdeam tot nu imi faceam cont de facebuc?
Se pot grupa in camere gen random sau dupa nume, varsta?
Pentru a calcula grupurile cum procedezi? Faci un algoritm de flux/cuplaj pentru a afla cea mai “avantajoasa” aranjare a tuturor participantilor sau ceva mai simplu?
Da am inteles in mare cum faci, insa facand asa o sa ai camere in care sunt numai “best friends” si camere in care sunt numai persoane care nu se cunosc (cred ca asta ai zis si tu mai sus). Puteai sa faci un algoritm de flux care sa iti uniformizeze acele costuri, insa depinde de rezultatul pe care vrei sa il obtii .
Oricum probabil ca algoritmul acesta nu e asa important pentru ca se poate modifica usor, ce e important e cum aduni toate informatile din retele de socializare si interfata grafica a programului.
Persoanele care nu au niciun cont pe o retea sociala sunt puse intr-un grup separat, deoarece acestea reprezinta un caz particular. Apoi ele sunt repartizate decat dupa sex, fiind singurul factor critic.
Problema pe care o rezolv se rezuma astfel: am un graf, pe care trebuie sa il impart in subgrafuri partiale disjuncte in functie de 3 conditii: - ordinele subgrafurilor sa fie cele setat de admin (unele grupuri pot avea 5 persoane, altele . - in subgrafurile obtinute sa am un procent de baieti si fete setat tot de admin (100% daca am doar un sex, sau intre 50% si un anumit procent daca vreau ambele sexe). - suma costurilor muchiilor din subgrafurile obtinute sa fie maxima.
Nodurile reprezinta persoanele, iar costurile muchiilor reprezinta un numar calculat dupa o formula in care inmultesc numarul de prieteni comuni, nr de pagini comune si nr de conturi de twitter urmarite comune, cu constante setate de admin (un prieten comun e mai important decat un like comun).
Nestiind prea multa teorie a grafurilor, am conceput urmatorul algoritm: - selectez perechea de noduri care au costul maxim - o consider un nod si calculez costurile pentru muchii dupa formula de mai sus - apoi incep recursiv:
- selectez baiatul cu cel mai mare cost, il adaug la grupul meu, calculez din nou costuri pentru restul nodurilor, si apelez recursiv
- selectez fata cu cel mai mare cost…
- si cand ajung la numarul dorit de persoane, adaug grupul intr-un vector
- parcurg vectorul obtinut, si care subgraf respecta conditiile de proportie intre sexe si are costul maxim, acela va fi un grup al meu - scot din graf grupul meu, si o iau de la inceput pana termin toate nodurile
.
.