Evident soluţia optimă pe primele trei coloane ale tablei foloseşte piesa în formă de cruce şi se obţine o acoperire cu $0$ greşeli, dar când vrem să acoperim toate $4$ coloanele tablei folosind prima acoperire obţinem o tablă cu $2$ greşeli, iar folosind două piese de tipul doi orientate înspre stânga, obţinem o acoperire cu o singură greşeală.

Pentru a obţine o soluţie cu $j + 1$ coloane ne trebuie toate soluţiile cu $j$ coloane la care ştim configuraţia coloanelor $j – 1$ şi $j$ (o piesă poate influenţa configuraţia a cel mult trei coloane). De aici se conturează ideea de a folosi un tablou $best$ unde $best[j][config1][config2]$ conţine numărul minim de greşeli astfel încât coloana $j$ are pătratele rămase neacoperite date de mulţimea $config1$, iar coloana $j - 1$ are pătratele neacoperite date de mulţimea $config2$. Pentru a trece de la $j$ la $j + 1$, facem un $backtracking$ pe o tablă de trei coloane dintre care prima are pătrăţelele ocupate date de $config2$, a doua pătrăţelele ocupate date de $config1$, iar a treia nu are nici un pătrăţel ocupat. După ce am plasat în procedura $backtraking$ nişte piese ajungem la configuraţiile pentru coloane date de mulţimile $c1 c2 c3$ şi actualizăm dacă am obţinut un număr mai mic pe $best[j + 1][c3][c2]$. În procedura recursivă ţinem cont atunci când vom acoperi cu piese un pătraţel deja acoperit sau un pătraţel ce nu este stricat. Ambele mulţimi $config1$ şi $config2$ pot fi reprezentate cu biţii unui întreg, $N$ fiind mic, astfel: primii $7$ biţi ai unui întreg vor reprezenta elementele primei mulţimi iar următorii $7$ biţi elementele celei de a două mulţimi. Memoria folosită de algoritmul nostru are ordinul de complexitate $O(M * 4^N^)$, acesta putând fi uşor micşorat la $O(4^N^)$ pentru că la pasul $j + 1$ avem nevoie numai de linia $j$ a matricii. Pentru a reduce numărul de stări folosite ne vom folosi de observaţia că putem să facem o restricţie asupra acoperirilor, aceea că atunci când ajungem la linia $j$ orice piesă nouă amplasată trebuie să acopere cel puţin un pătrăţel neacoperit de pe linia $j – 1$. Fie $newBest[j][confing12]$ structura care păstrează cele mai bune acoperiri cu această restricţie, atunci soluţia optimă va fi în $newBest[M + 1]$ unde am considerat o nouă coloană $M + 1$ a tablei ce nu are niciun pătrăţel stricat. Pentru tablele astfel acoperite, configuraţiile ultimelor două pătrăţele de pe o linie de forma $11$ şi $10$ şi $00$, configuraţia $01$ nu apare pentru că este evident că nu există o piesă care să acopere un pătrat din ultima coloană, un pătrat cu două coloane înainte şi să nu acopere pătratul imediat în stânga pătratului de pe ultima linie. Astfel avem $O(3^N^)$ configuraţii posibile pentru ultimele două coloane. Mai există multe configuraţii de două coloane la care nu se poate ajunge folosind piesele din problemă, dar o analiză exactă ar fi dificilă şi probabil ar complica inutil implementarea. Să vedem cum arată configuraţiile pe un exemplu:

Pentru a obţine o soluţie cu $j + 1$ coloane ne trebuie toate soluţiile cu $j$ coloane la care ştim configuraţia coloanelor $j – 1$ şi $j$ (o piesă poate influenţa configuraţia a cel mult trei coloane). De aici se conturează ideea de a folosi un tablou $best$ unde $best[j][config1][config2]$ conţine numărul minim de greşeli astfel încât coloana $j$ are pătratele rămase neacoperite date de mulţimea $config1$, iar coloana $j - 1$ are pătratele neacoperite date de mulţimea $config2$. Pentru a trece de la $j$ la $j + 1$, facem un $backtracking$ pe o tablă de trei coloane dintre care prima are pătrăţelele ocupate date de $config2$, a doua pătrăţelele ocupate date de $config1$, iar a treia nu are nici un pătrăţel ocupat. După ce am plasat în procedura $backtraking$ nişte piese ajungem la configuraţiile pentru coloane date de mulţimile $c1 c2 c3$ şi actualizăm dacă am obţinut un număr mai mic pe $best[j + 1][c3][c2]$. În procedura recursivă ţinem cont atunci când vom acoperi cu piese un pătraţel deja acoperit sau un pătraţel ce nu este stricat. Ambele mulţimi $config1$ şi $config2$ pot fi reprezentate cu biţii unui întreg, $N$ fiind mic, astfel: primii $7$ biţi ai unui întreg vor reprezenta elementele primei mulţimi iar următorii $7$ biţi elementele celei de a două mulţimi. Memoria folosită de algoritmul nostru are ordinul de complexitate $O(M * 4^N^)$, acesta putând fi uşor micşorat la $O(4^N^)$ pentru că la pasul $j + 1$ avem nevoie numai de linia $j$ a matricii. Pentru a reduce numărul de stări folosite ne vom folosi de observaţia că putem să facem o restricţie asupra acoperirilor, aceea că atunci când ajungem la coloana $j$ orice piesă nouă amplasată trebuie să acopere cel puţin un pătrăţel neacoperit de pe coloana $j – 1$. Fie $newBest[j][confing12]$ structura care păstrează cele mai bune acoperiri cu această restricţie, atunci soluţia optimă va fi în $newBest[M + 1]$ unde am considerat o nouă coloană $M + 1$ a tablei ce nu are niciun pătrăţel stricat. Pentru tablele astfel acoperite, configuraţiile ultimelor două pătrăţele de pe o linie sunt de forma: $11$ şi $10$ şi $00$, configuraţia $01$ nu apare pentru că este evident că nu există o piesă care să acopere un pătrat din ultima coloană, un pătrat cu două coloane înainte şi să nu acopere pătratul imediat în stânga pătratului de pe ultima linie. Astfel avem $O(3^N^)$ configuraţii posibile pentru ultimele două coloane. Mai există multe configuraţii de două coloane la care nu se poate ajunge folosind piesele din problemă, dar o analiză exactă ar fi dificilă şi probabil ar complica inutil implementarea. Să vedem cum arată configuraţiile pe un exemplu:

p=. !probleme-de-acoperire2?P224.jpg!

}
==

În $num[i][config]$ ţinem minte câte posibilităţi sunt să acoperim $i - 1$ linii cu piesele date în problemă, iar linia $i$ să fie ocupată aşa cum arată reprezentarea în baza $2$ a numărului întreg $config$. Se observă folosirea variabilei $step$ care de la un pas la altul se transformă astfel $step ^= 1$, aceast mic truc ne face să putem folosi o matrice de doar $2$ linii în loc să folosim $N$ linii. La momentul $i$, în $num[step][config]$ avem informaţia ce ar fi fost în mod normal în $num[i][config]$, iar în $num[1 ^ step][config1]$ vom calcula ce ar fi fost normal în $num[i + 1][config1]$. În şirul $p$ ţinem minte forma pieselor din problemă.

În $num[i][config]$ ţinem minte câte posibilităţi sunt să acoperim $i - 1$ linii cu piesele date în problemă, iar linia $i$ să fie ocupată aşa cum arată reprezentarea în baza $2$ a numărului întreg $config$. Se observă folosirea variabilei $step$ care de la un pas la altul se transformă astfel $step ^= 1$, acest mic truc ne face să putem folosi o matrice de doar $2$ linii în loc să folosim $N$ linii. La momentul $i$, în $num[step][config]$ avem informaţia ce ar fi fost în mod normal în $num[i][config]$, iar în $num[1 ^ step][config1]$ vom calcula ce ar fi fost normal în $num[i + 1][config1]$. În şirul $p$ ţinem minte forma pieselor din problemă.

În procedura $doit$ punem pe două linii consecutive piese în toate modurile posibile. Această procedură face ca pe prima linie să avem o configuraţie de pătrăţele libere $config$ şi o configuraţie de pătrăţele ocupate pe a doua linie $config1$. Dacă pătrăţelele reprezentate de $config$ nu au fost ocupate la pasul curent ele trebuie să fi fost ocupate la pasul anterior. Astfel, pentru fiecare pereche de configuraţii $config$ şi $config1$ trebuie să efectuăm operaţia $num[i + 1][config1] += num[i][config]$.

h3. Soluţie:

Evident, putem încerca o soluţie identică cu cea a $Problemei 1$, dar aici limitele sunt puţin mai mari şi avem nevoie de un algoritm mai eficient.

Evident, putem încerca o soluţie identică cu cea a '$Problemei 1$':probleme-de-acoperire2#prob1, dar aici limitele sunt puţin mai mari şi avem nevoie de un algoritm mai eficient.

Există o rezolvare de complexitate $O(N * M * 3^M^)$ care aşa cum deja v-aţi obişnuit combină metoda $backtracking$ cu metoda $programării dinamice$. Folosim un tablou $max[N][M + 1][3^(M + 1)^]$ care conţine numărul maxim de dale puse pentru o anumită stare. Fiecare element al matricii va avea iniţial $max[i][j][config]$ egal cu $0$. Iterăm rândurile în ordinea $1 .. N$ ,coloanele în ordinea $1 .. M$ şi configuraţiile în ordine lexicografică. Când vom procesa starea reprezentată de parametrii $(i, j, config)$ vom decide dacă punem una dintre piese cu colţul de stânga sus în $(i, j)$ sau dacă lăsăm celula $(i, j)$ liberă. O stare $(i, j, config)$ se referă la un pătrăţel din matrice şi la o bandă „activă” de pătrăţele ce are lăţimea $2$. Banda conţine celulele $(i1, j + 1), (i1, j + 2)$ pentru $i1 < i$ şi celulele $(i2, j), (i2, j + 1)$ pentru $i <= i2$. Cifrele în baza $3$ ale parametrului $config$ ne spun starea perechilor de pătrate de pe banda activă: $00$ este reprezentat în $config$ de cifra $0$, $10$ de cifra $1$ şi $11$ de cifra $2$ (configuraţia $01$ nu poate apărea). De exemplu, starea $(4, 3, 1000212)$ va reprezenta configuraţia prezentată în următoarea imagine (ultima cifră corespunde primei perechi de pătrăţele, penultima cifră celei de a doua perechi şamd):