Probleme de acoperire 2

(Categoria Algoritmi, autor Cosmin Negruşeri)

Subiectul acestui articol sunt acoperirile cu o abordare bazată pe tehnici de programare.

Problema 1 (MagicBoxes, TopCoder)

Să se determine numărul N maxim astfel ca într-un dreptunghi de dimensiuni L x W (1 <= L , W <= 30) să poată fi dispuse paralel cu axele de coordonate N pătrate de laturi 1 .. N astfel ca oricare două pătrate să nu aibă porţiuni care se suprapun.

Soluţie:

• Această problemă, deşi clasică, este dificil de rezolvat în cazul general si singura abordare a ei este aceea de a folosi metoda backtracking.
• Întâi putem stabili o limită superioară a numarului N: este evident că N <= W, N <= L şi că 1² + 2² + .. + N² <= L x W. Putem porni cu N de la limita superioară dată de aceste inegalităţi şi să încercăm să dispunem cele N pătrate în interiorul dreptunghiului. O optimizare simplă care ne-ar fi ajutat să rezolvăm problema, precalculând toate rezultatele, ar fi fost să punem în dreptunghi pătratele în ordinea descrescătoare a înălţimii. Altă observaţie ce reduce timpul de execuţie este că piesa cea mai mare nu trebuie pusă în toate poziţiile posibile ci în un sfert din ele, din cauza soluţiilor simetrice, iar între ea şi margine nu trebuie lăsat spaţiu puţin pentru că acel spaţiu va rămâne nefolosit. Observaţia care ne-ar fi dus la o soluţie care să rezolve un test în două secunde, cât era limita de timp în concurs, este că procedura backtraking pierde mult timp pentru verificarea dacă o piesă poate fi pusă pe o anumită poziţie. Dacă în loc de reprezentarea pe matrice folosim L întregi astfel ca bitul al j-lea din întregul i este 1 dacă celula (i, j) este deja ocupată şi 0 altfel, vom putea verifica dacă pătratul de latură i poate fi plasat pe o anumită poziţie în i paşi, şi nu în i² paşi ca înainte.
• Această reprezentare pe biţi este foarte utilă în probleme de acest gen, şi cum avem întregi de 64 de biţi pe care îi putem folosi, avem o metodă foarte simplă de reprezentare a tablelor de mărime până la 64.

Problema 2 (IOI 2001 Pavement, problemă de rezervă [1])

Se dă o matrice de dimensiuni N x M (1 <= N <= 7 şi 1 <= M <= 100). Unele celule ale acestei matrici sunt distruse şi trebuie acoperite cu piese de forma din Fig. 1. Fiecare celulă rămasă neacoperită se consideră o greşeală, iar dacă o piesă cu care am acoperit celule distruse a trebuit să fie tăiată pentru a acoperi numai celule distruse, fiecare pătrăţel din partea nefolosită a piesei este considerată o greşeală. Se cere acoperirea tablei astfel ca numărul de greşeli să fie minimizat. În Fig. 2, pentru prima tablă, acoperirea optimă are două greşeli, aşa cum vedem în al doilea desen.

Fig. 1   Fig. 2

Soluţie:

• Aşa cum am zis şi în articolul anterior, problemele de acoperire sunt în general NP complete, deci prima idee ar fi să încercăm o rezolvare prin metoda backtraking, dar dimensiunile datelor de intrare ne arată că o asemenea rezolvare nu ne rezolvă problema.

• Strategii polinomiale de tip greedy sau de tip programare dinamică nu vor rezolva această problemă pe toate cazurile de intrare, şi pentru orice strategie se poate găsi câte un contraexemplu. Totuşi vom putea să folosim o rezolvare bazată pe combinarea tehnicilor de programare dinamică şi backtraking. Să vedem cum.
• Construim soluţia optimă coloană cu coloană, dar este evident din următorul exemplu că pentru a construi soluţia optimă pentru coloana j + 1 nu este de ajuns să acoperim optim primele j coloane.

• 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:

• Putem reprezenta această acoperire astfel:

00010
01110
11110
00011

• Iar ultimele două coloane arată în felul următor:

10
10
10
10
11

• În acest caz config are valoarea 1 * 3⁰ + 1 * 3¹ + 1 * 3² + 1 * 3³ + 2 * 3⁴ = 202. Acum, la fiecare pas noi vrem să punem pe coloana j – 1 câte o piesă pentru a obţine rezultatele pentru newBest[j + 1], sau să nu punem o piesă acolo. Deci, avem 9 posibilităţi de a pune piese (fiecare rotaţie şi reflexie a pieselor din problemă) şi posibilitatea de a nu pune piesă în pătrăţelul curent, deci în total 10 posibilităţi. Astfel, complexitatea algoritmului nostru devine O(M * 3^N * 10^N), constanta din faţă acestei complexităţi este subunitară din cauză că nu vom trece prin stări imposibile.

Problema 3 (ACM ICPC 1997)

Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni N x M (N <= 15, M <= 15) cu dominouri.

Soluţie:

• Am văzut în numărul anterior că există o formulă pentru acest număr. Abordarea matematică poate fi generalizată şi pentru mai multe probleme asemănătoare de acoperire, dar cunoştinţele necesare sunt avansate, deci această abordare nu ne prea ajută pe noi ca informaticieni.
• O soluţie care ne va da numărul exact şi ar fi putut fi folosită în concurs este asemănătoare celei expuse mai sus. Vom folosi o combinaţie a metodei backtracking cu metoda programării dinamice. Tabloul numWays[i][config] va fi numărul de posibilităţi de a acoperi complet primele i - 1 coloane ale unei table, iar pe coloana i pătratele ocupate sunt reprezentate de mulţimea config. Astfel, numWays[i + 1][config1] va fi egal cu suma de numWays[i][config] unde putem acoperi cu dominouri două coloane astfel ca pe prima coloană să nu fie acoperite celulele date de config şi pe a doua coloană să fie acoperite celulele date de config1. De exemplu, starea dată de (4, 100100) este prezentată în următoarea figură:

• Dacă procedura aşezăm trei dominouri pe linia 4 şi linia 5 aşa cum vedem mai sus, atunci vom trece în starea (5, 011000). La final, vom returna valoarea aflată în numWays[N + 1]⁰ . Complexitatea ca timp a acestei rezolvări este O(M * 4^N), iar ca spaţiu este O(2^N).