(Categoria _Tehnici de programare_, autori _Catalin Tiseanu_, _Andrei Homescu_)

TODO:

TODO://ok..to do...dar do mai repede...k e foarte bun articolul si vreau sa citesc si partea cealalta...e pacat sa lasati articolul neterminat asa...vede lumea...bine..e si funny ;)) peace out ;)

1. Reparat link de la ugly numbers

h2. Programare dinamică folosind măşti de biţi şi codificări $k$-are

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:

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 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.

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.

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_).

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.

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. Numărul căutat este suma numerelor de stări care îndeplinesc fiecare condiţie.

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;

  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];

         IS = IS + S[G][B][k + 1];

       sfârşit pentru;
  sfârşit pentru;
  returnează IS;

  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];

      IS = IS - S[G][B][k + 1];

      n[k] = n[k] + 1;
    sfârşit cât timp;
  sfârşit pentru;

  returnează n;
==

Aceşti algoritmi pot fi integraţi în funcţia recursivă de calcul a matricii $R$.
 

To be continued ...