Maski bitowe

03.10.2009 - Damian Rusak
TrudnośćTrudnośćTrudność

Zadanie Studenci

Oto inne ciekawe zadanie, które można rozwiązać, korzystając z masek bitowych:


Dla danej liczby $ n $, rozpatrujemy $ n $ studentów i $ n $ zadań. Każdy student lubi pewne wybrane zadania. Twoim zadaniem jest obliczyć, na ile sposobów można przyporządkować dokładnie po jednym zadaniu do każdego studenta, tak aby każdy otrzymał inne zadanie i każdy lubił zadanie, które otrzymał. Studentów będzie co najwyżej 20.


Pierwsza rzecz, która jest istotna, to fakt, że studentów jest niewielu. Dopuszcza to rozwiązania działające w czasie wykładniczym. Zauważamy też, że w zadaniu chcemy policzyć, ile jest pełnych skojarzeń zbiorów studentów i zadań.

Ten problem, podobnie jak TSP, jest trudny. Zliczanie ilości pełnych skojarzeń to zadanie bardzo pracochłonne i nie znane są algorytmy, działające w czasie wielomianowym, które rozwiązywałyby ten problem. Jeśli chcesz dowiedzieć się więcej na ten temat, polecam artykuł na Wikipedii, na temat Permanentu - pojęcia matematycznego, związanego z naszym problemem.


Szukajmy wobec tego dobrego rozwiązania w wykładniczym czasie.

Możemy podejść do problemu w ten sposób - gdyby zliczać skojarzenia stopniowo, dla coraz większych podzbiorów studentów, nie trzeba by pamiętać, któremu studentowi przydzielono które zadanie, a jedynie którzy studenci  i które zadania są już „zajęte”. Jeśli przyjmiemy, że będziemy rozpatrywać studentów po kolei, znajdując ilość skojarzeń najpierw dla studenta nr 1, potem dla studentów 1 i 2, i tak dalej, to będziemy musieli wiedzieć dwie rzeczy:


- którego studenta obecnie rozpatrujemy
- które zadania są już przydzielone (nie interesuje nas, które do kogo)

Pierwsze wymaganie załatwia nam zwykła pętla, drugie zaspokaja metoda masek bitowych - zapamiętujemy, który podzbiór zadań został już przydzielony. Będziemy obliczać dynamicznie wartości dla kolejnych stanów. Oznaczmy:

$ Z $ - zbiór zadań.

$ X $ - zbiór studentów.

$ D\left[k\right]\left[W\right] $ - ilość skojarzeń $ k $ pierwszych studentów z podzbiorem $ W $ zbioru $ Z $.

$ B\left[x\right]\left[z\right] $ = 1, jeśli studentowi x można przydzielić zadanie z, 0 w przeciwnym razie.



Dla uproszczenia notacji będziemy też przyjmować, że oznaczenie zbioru to zarazem oznaczenie jego maski bitowej, w kontekście, w którym jest wymagana (np. dla zbioru $ Y $, wartość $ D\left[k\right]\left[Y\right] $ odnosi się w drugim parametrze tablicy do maski bitowej zbioru $ Y $).

 
Nasz algorytm będzie wyglądał tak, że przeglądać będziemy kolejnych studentów i dla
k-tego w kolejności studenta, przeglądniemy te podzbiory zbioru $ Z $ zadań, których moc wynosi $ k $ (chcemy mieć dokładne skojarzenie). Takie podzbiory mamy zapamiętane, dzieki metodzie generowania masek bitowych wraz z ilością ich zapalonych bitów. Teraz dla ustalonego $ k $ i podzbioru $ Y $, potencjalnie każde  z zadań z $ Y $ (oznaczmy takie zadanie $ y $) mogło zostać przydzielone studentowi o numerze $ k $, o ile $ B\left[k\right]\left[y\right] = 1 $. Musimy więc przeiterować po elementach $ Y $ (znamy metodę sprawdzania, które bity są zapalone), dla każdego zapalonego bitu na pewnej pozycji  $ r $  sprawdzić, czy student o numerze $ k $ może otrzymać to zadanie, i do wartości $ D\left[k\right]\left[Y\right] $ dodać wartość $ D\left[k-1\right]\left[Y - 2^{r-1}\right] $, jeśli to możliwe. Dzięki temu, uzyskamy sumę wszystkich możliwości przydziału :

$ D\left[k\right]\left[Y\right] = \sum_{\left(r+1\right)\in Y}D\left[k-1\right]\left[Y-2^{r-1}\right] $

Rozwiązaniem jest wartość $ D\left[n\right]\left[2^{n-1} - 1\right] $, czyli ilość wszystkich możliwych skojarzeń pomiędzy pełnymi zbiorami studentów i zadań.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
5
Twoja ocena: Brak Ocena: 5 (7 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com