h2. Programare dinamica folosind bitmask
In continuare vom vedea un exemplu de programare dinamica unde vom folosi un bitmask (codificat pe un intreg) pentru a tine spatiul starilor.
h2. Programare dinamică folosind măşti de biţi şi codificări $k$-are
Astfel sa presupunem ca avem nevoie sa tinem un vector caracteristic pentru o multime.
Daca cardinalul acesteia este suficient de mic putem folosi un intreg pentru a codifica aceasta informatie astfel:
Unele probleme de programare dinamica au drept componentă a stării unei subprobleme o mulţime de elemente care fac parte din subproblemă. Astfel, subproblema nu este o reducere a problemei iniţiale la un subset continuu de elemente ({$1..i$} sau $i..j$) ci la un subset oarecare. În acest caz, codificăm submulţimea curentă în stare, ca vector sau ca număr întreg. Dacă dimensiunea submulţimii este suficient de mic putem folosi un întreg pentru a codifica această informaţie astfel:
Fie multimea A = { x{~1~}, x{~2~}, ... x{~n~} }.
Atunci bitmaskul unei partitii a lui A, MASK, va avea bitul i egal cu 1 numai si numai daca x{~i~} apartine partitiei.
Fie mulţimea $A$ = { x{~1~}, x{~2~}, ... x{~n~} }.
Atunci masca de biţi a unei partitii a lui $A$, $MASK$, va avea bitul $i$ egal cu 1 dacă şi numai dacă x{~i~} apartine partitiei. Desigur, această reprezentare duce la o complexitate direct proporţională cu $2 ^card(A)^$. Putem intui dacă trebuie să folosim o astfel de rezolvare din limitele valorilor de intrare; pentru $N$ cu valori cuprinse între $10-20$, deducem că trebuie să căutăm o astfel de soluţie.
Desigur, aceasta reprezentare duce la o complexitate direct proportionala cu 2 ^card(A)^.
Pentru multe probleme, fiecare element poate face parte din subproblemă în mai mult de 2 feluri. De exemplu, dacă starea reprezintă o linie de maxim $K$ elemente dintr-o matrice iar fiecare element de pe linie poate avea valorile 0, 1 sau 2 atunci există $3^K$ variante distincte posibile pentru o astfel de linie. Un alt exemplu este o problemă de optimizare în care fiecare element (participant) se poate afla în una din câteva stări (dacă $N$ persoane trebuie să treacă un pod peste un râu, cele 3 stări pot fi: _pe malul stâng_, _pe pod_ şi _pe malul drept_).
h3(#problema-1). Problema 1: 'Be a Smart Raftsman':http://acm.sgu.ru/problem.php?contest=0&problem=475 (SGU)
==
h3(#problema-2). Problema 2: 'Doipatru':http://infoarena.ro/problema/doipatru
bq. Membrii Lotului Naţional de Informatică sunt foarte mândri de noul joc inventat de ei, pe care l-au denumit asemănător cu o problemă de la Olimpiada Internaţională de Informatică din anul 2001, care le-a plăcut foarte mult. Astfel, jocul se numeşte DoiPatru.
Pentru acest joc se folosesc $3 ≤ N ≤ 30$ grămezi, fiecare conţinând cel puţin 0 şi cel mult 4 bile. Numărul total de bile din toate grămezile este $2*N$. Doi jucători mută alternativ. Atunci când ii vine rândul, fiecare jucător este obligat să efectueze o mutare validă.
O mutare validă constă din alegerea a două grămezi, dintre care prima grămadă are mai multe bile decât cea de a doua. Jucătorul ia o bilă din prima grămadă şi o mută în cealaltă. Mutarea se consideră validă, doar dacă numărul de bile rezultat în a doua grămadă după mutarea bilei nu este mai mare decât numărul de bile rămas în prima grămadă.
Jocul se termină atunci când nu mai poate fi efectuată nici o mutare validă (dacă vă gândiţi puţin, veţi constata că acest lucru se întâmplă atunci când fiecare grămadă conţine două bile).
Câştigătorul jocului este desemnat cel care deţine mai multe grămezi la sfârşitul jocului. Bineînţeles, dacă cei doi jucători deţin un număr egal de grămezi, jocul se consideră a fi remiză.
Un jucător deţine o grămadă dacă grămada are două bile, iar acest număr (de două bile) a rezultat în urma unei mutări efectuate de jucătorul respectiv. De exemplu, dacă un jucător alege o grămadă cu 4 bile şi una cu o bilă, în urma efectuării mutării, el va deţine cea de-a doua grămadă (care va avea două bile), dar prima nu va aparţine deocamdată nici unuia dintre jucători. Dacă alege o grămadă cu 3 bile şi una cu 0 bile, jucătorul va deveni proprietarul primei grămezi, deoarece, în urma mutării efectuate, grămada respectivă va rămâne cu două bile. În cazul în care alege o grămadă cu 3 bile şi una cu o bilă, după efectuarea mutării, el va deţine ambele grămezi (amândouă au acum doua bile).
Dacă un jucător este proprietarul unei grămezi la un moment dat în timpul jocului, nu înseamnă că această grămadă va rămâne în posesia lui până la sfârşit. De exemplu, să presupunem că jucătorul 1 deţine o grămadă cu două bile şi este rândul jucătorului 2 să mute. Dacă acesta alege o grămadă cu 4 bile şi grămada cu două bile ce aparţine jucătorului 1, după efectuarea mutării, ambele grămezi vor avea 3 bile, iar numărul de grămezi aflate în posesia jucătorului 1 va scădea cu 1 (grămada deţinută de el anterior nu mai aparţine nici unuia din cei doi jucători, căci nu mai are doua bile).
Dacă la începutul jocului există unele grămezi având două bile, acestea sunt distribuite în mod egal celor doi jucători. Dacă numărul de grămezi cu două bile este impar, atunci jucătorul 2 va primi cu o grămadă mai mult decât jucatorul 1. Jucătorul 1 este cel care efectuează prima mutare.
Scrieţi un program care, pentru un $N$ dat şi un set de configuraţii iniţiale ale jocului cu $N$ grămezi, decide rezultatul fiecărei configuraţii de joc.
h3. Rezolvare:
Începem rezolvarea cu observaţia că există 5 tipuri de grămezi (0, 1, 2, 3 şi 4 bile), dar pentru fiecare grămadă de 2 bile aparţine doar unuia dintre jucători, informaţie esenţială pentru stabilirea câştigătorului. Vom separa deci toate grămezile de 2 bile în 2 categorii: $2A$ care reprezintă grămezile de 2 bile deţinute de primul jucător şi $2B$ care sunt grămezile de 2 bile deţinute de al doilea jucător. Orice moment al jocului poate fi reprezentat identificând jucătorul care urmează la mutare şi numărul de bile din fiecare dintre cele $N$ grămezi. O variantă alternativă este de a reprezenta numerele de grămezi din fiecare tip, starea fiind reprezentată prin valorile $(J, n{~0~}, n{~1~}, n{~2A~}, n{~2B~}, n{~3~}, n{~4~})$, unde $n{~k~}$ reprezintă numărul de grămezi care au $k$ bile (cu excepţiile $2A$ şi $2B$, descrise înainte).
Vom nota prin $R[J, n{~0~}, n{~1~}, n{~2A~}, n{~2B~}, n{~3~}, n{~4~}]$ cel mai bun rezultat pe care îl poate obţine jucătorul care urmează ({$J$}). Valorile posibile ale rezultatului vor fi alese ca numere întregi crescătoare, astfel: 0 dacă din configuraţia curentă jucătorul nu are nici o şansă să câştige, 1 dacă jucătorul poate obţine o remiză şi 2 dacă jucătorul are o strategie sigură de câştig. Fiecare jucător va alege mutarea potrivită astfel încât să maximizeze valoarea $R$, care este în acelaşi timp rezultatul cel mai prost pentru celălalt jucător. Vom nota jucătorii prin 0 şi 1 şi putem calcula valoarea optimă pentru $R$ astfel:
<tex> $R[J, n_0, n_1, n_{2A}, n_{2B}, n_3, n_4] = 2 - \min\{R[\(1 - J\), n_0', n_1', n_{2A}', n_{2B}', n_3', n_4'] \}$</tex> dacă $(n'{~0~}, n'{~1~}, n'{~2A~}, n'{~2B~}, n'{~3~}, n'{~4~})$ reprezintă o stare accesibilă din starea curentă printr-o singură mutare. Observăm că rezultatul este cu atât mai bun pentru unul dintre jucători cu cât este mai prost pentru celălalt, deci rezultatele sunt invers proporţionale, $2$ pentru $J$ reprezentănd $0$ pentru jucătorul $1 - J$. Fiecare jucător alege mutarea care îi va obţine rezultatul maxim, acesta fiind corespunzător rezultatului defavorabil (de valoare minimă) pentru celălalt.
Stările pentru care nu mai există decât grămezi de tipuri $2A$ şi $2B$ sunt, conform enunţului, stări finale.
<tex> $R[J, 0, 0, n_{2A}, n_{2B}, 0, 0] = \left\{
\begin{array}{l l}
0 & \quad J = 0, n_{2A} < n_{2B}\\
0 & \quad J = 1, n_{2A} > n_{2B}\\
1 & \quad n_{2A} = n_{2B}\\
2 & \quad J = 0, n_{2A} > n_{2B}\\
2 & \quad J = 1, n_{2A} < n_{2B}\\
\end{array} \right. $</tex>
Notând cu $S$ tuplul distribuţiei bilelor în grămezi $(J, n{~0~}, n{~1~}, n{~2A~}, n{~2B~}, n{~3~}, n{~4~})$ atunci vom folosi o notaţie echivalentă dar mai scurtă, $R[J, S]$. Vom iniţializa toate valorile din acest tablou multidimensional la -1 şi apoi vom calcula recursiv valorile, obţinând o complexitate polinomială prin memoizare.
== code(cpp) |
calculR(J, S)
dacă R[J, S] != -1 atunci
returnează R[J, S];
dacă S e stare finală
returnează 0, 1 sau 2 în funcţie de câştigător;
R[J, S] = 0;
pentru toate stările S' în care se poate ajunge din S printr-o mutare
R[J, S] = max(R[J, S], 2 - calculR(1 - J, S'));
sfârşit pentru;
returnează R[J, S];
==
La prima vedere, numărul stărilor este $2 * (2N)^6^ = 2 * 60^6^ = 93,312 * 10^9^$, deci numărul stărilor este prea mare pentru a intra în limite rezonabile de spaţiu şi timp. Observăm totuşi că toate stările îndeplinesc condiţia $n{~0~} + n{~1~} + n{~2A~} + n{~2B~} + n{~3~} + n{~4~} = N$. Numărul total al stărilor este numărul tuplurilor care îndeplinesc egalitatea şi condiţiile $n{~k~} ≥ 0$. Vom numerota cele 6 tipuri de grămezi prin numere de la 0 la 5. Vom calcula valorile $N{~S~}[g, b, v]$ care reprezintă numărul de variante de a grupa $b$ bile în $g$ grămezi, astfel încât cea mai mică grămadă să aibă cel puţin mărimea tipului de indice $0 ≤ v ≤ 5$. Notăm cu $D$ şirul dimensiunilor tipurilor, $(0, 1, 2, 2, 3, 4)$ şi observăm că o stare descrisă prin $(g, b, v)$ ori are o grămadă de dimensiune $D{~v~}$ ori toate grămezile sunt mai mari decât această dimensiune. Atunci recurenţa de calcul pentru $N{~S~}$ este: $N{~S~}[g, b, v] = N{~S~}[g, b, v + 1] + N{~S~}[g - 1, b - D{~v~}, v]$ cu cazul particular $N{~S~}[0, 0, 5] = 1$. Numărul total de stări este valoarea $N{~S~}[N, 2*N, 0]$. Pentru valoarea maximă a lui $N$ din enunţ, am obţinut $N{~S~}(30) = N{~S~}[30, 60, 0] = 8266$. Rezultă deci că numărul total real al stărilor este relativ mic, iar soluţia noastră se încadrează în limitele de timp şi spaţiu date.
Pentru o stare $S$ dată, numărul stărilor posibile $S'$ în care putem ajunge este foarte mic. În cel mai rău caz, perechile de grămezi care reprezintă mutarea din pasul curent sunt din mulţimea ${(0, 2A), (0, 2B), (0, 3), (0, 4), (1, 3), (1, 4), (2A, 4), (2B, 4)}$, deci un jucător are maxim 8 mutări posibile de efectuat. După ce am ales tipurile de grămezi pe care efectuăm mutarea, este irelevantă alegerea grămezilor cu dimensiunile date, deoarece toate alegerile duc la aceeaşi stare următoare.
Un mod de a stoca tabloul $R$ astfel încât spaţiul necesar să fie minim este folosirea unui dicţionar care să stocheze valorile $R[J, n{~0~}, n{~1~}, n{~2A~}, n{~2B~}, n{~3~}, n{~4~}]$ pentru toate stările valide, folosind astfel doar $O(N{~S~}(N))$ spaţiu. Dicţionarul poate fi implementat printr-o tabelă de dispersie sau arbori binari de căutare, în C++ folosind chiar $map$ sau $hash_map$ din STL. Altă opţiune este codificarea fiecărei stări $S$ printr-un număr întreg cuprins între 1 şi $N{~S~}(N)$, caz în care tabloul $R$ poate fi stocat într-o matrice de dimensiune $2xN{~S~}(N)$. Asocierea dintre descrierea unei stări (numărul de grămezi de fiecare tip) şi numărul său de ordine poate fi precalculată şi stocată într-un dicţionar sau poate fi calculată în $O(N)$ cu ajutorul unor formule. În primul caz, vom genera prin backtracking toate variantele posibile de stări într-o ordine oarecare şi vom aloca fiecărei stări câte un număr, stocând izomorfismul într-un dicţionar.
Varianta mai complexă, dar mai elegantă presupune stabilirea unei ordini fixe a stărilor şi apoi folosirea unor tehnici combinatoriale pentru a calcula numărul corespunzător unei stări sau starea corespunzătoare unui număr. Vom defini mai formal o stare ca un 6-tuplu $(n{~0~}, n{~1~}, n{~2A~}, n{~2B~}, n{~3~}, n{~4~})$ şi vom ordona toate stările lexicografic (stările sunt ordonate după $n{~0~}$; în caz de egalitate, sortarea se face după $n{~1~}$ ş.a.m.d.). Atunci numărul de ordine al unei stări calculat de formula de mai sus este numărul de stări care au o valoare mai mică pentru $n{~0~}$ plus numărul de stări care au aceeaşi valoare pentru $n{~0~}$ dar o valoare mai mică pentru $n{~1~}$ ş.a.m.d.
==code(cpp) |
IS = 1;
G = N;
B = 2 * N;
pentru k = 0, 4 execută
dacă n[k] > 0 atunci
pentru i = 1, n[k] execută
IS = IS + S[G][B][k + 1];
G = G - 1;
B = B - D[k];
sfârşit pentru;
sfârşit pentru;
returnează IS;
==
Operaţia inversă calculează o stare $S$ pe baza valorii $I(S)$ a indicelui stării.
==code(cpp) |
G = N;
B = 2 * N;
pentru k = 0, 4 execută
n[k] = 0;
cât timp IS > S[G][B][k + 1] execută
IS = IS - S[G][B][k + 1];
G = G - 1;
B = B - D[k];
n[k] = n[k] + 1;
sfârşit cât timp;
sfârşit pentru;
n[5] = G;
returnează n;
==
Aceşti algoritmi pot fi integraţi în funcţia recursivă de calcul a matricii $R$.
To be continued ...
