@..2.@
Muchiile din graful bipartit vor fi urmatoarele:
$(1, 1) (2, 2) (3, 3) (3, 2) (3, 4) (4, 5) (4, 3) (4, 2) (5, 2)$
Asadar fiecarei celule din harta terenului ii corespunde o singura muchie in acest graf bipartit. Avand construit graful trebuie sa aflam numarul minim de noduri selectate astfel incat orice muchie sa aiba cel putin un capat intre nodurile selectate (in literatura de specialitate aceasta problema se numeste $Minimum Vertex Cover$). Explicatia acestui lucru este simpla: orice muchie, fiind de fapt o celula, ea trebuie sa fie "acoperita" de cel putin un nod din graf (adica o placa orizontala sau verticala utilizata de FJ). Problema acesta este NP-completa pentru grafuri generale dar in cazul grafurilor bipartite ea se poate rezolva in timp polinomial. De asemenea s-a demonstrat ca numarul minim de noduri dintr-un astfel de set este egal cu cardinalul cuplajului maximal din graful bipartit. De aici nu mai e decat un pas spre solutia finala. Avem, astfel, urmatorii pasi in algoritmul de rezolvare a problemei:
==code(cpp) |
* PAS 1: Construirea grafului bipartit
* PAS 2: Aflarea cuplajului maximal
==
Primul pas este banal si consta din simple parcurgeri ale matricii. Pentru aflarea cuplajului maximal se poate afla utilizand un algoritm de aflarea a fluxului maxim in reteaua asociata grafului bipartit sau se poate algoritmul bazat pe gasirea succesiva a drumurilor in crestere in graf.
Complexitatea finala a algoritmului va fi $O(N^2^*M^2^)$ deoarece in graful bipartit avem maxim $N*M$ muchii si vom $N*M$ noduri. Cum algoritmul pentru aflarea cuplajului maximal are complexitatea $V*E$ ($V$ = numarul de noduri din graf, $E$ = numarul de muchii din graf) concluzia este evidenta.
Ca tema, recomand rezolvarea urmatoarelor probleme a caror solutie se bazeaza pe aflarea cuplajului maximal intr-un graf bipartit (in unele cazuri acest lucru insa nu este de ajuns):
Mentionez ca problema 8 m-a impresionat in mod placut fiind una dintre cele mai frumoase probleme pe care le-am intalnit in ultimele cateva luni.
Juice
Fie A(i, j) inaltimea blocului aflat in pozitia (i, j). Aflam inaltimea maxima la care poate urca nivelul sucului in fiecare celula. Daca notam aceasta inaltime cu B(i, j) solutia problemei va fi suma( B(i, j) - A(i, j) ).
Vom numi celula turn o celula (i, j) care are propietatea ca B(i, j) = A(i, j) (nu putem pune suc in ea pentru ca ar curge in afara matricei). Componenta conexa a unei celule turn (i, j) este compusa din acele celule (x, y) pentru care avem B(x, y) = A(i, j). Definim inaltimea componentei conexe ca fiind inaltimea comuna a tuturor celulelor componente. Facem urmatoarele observatii utile in rezolvarea problemei:
1. Celulele de pe marginea matricei sunt celule turn
2. Celula (x, y) devine celula turn daca este vecina unei celule (i, j) ce face parte dintr-o componenta conexa si are propietatea ca B(i, j) < A(x, y).
h2. Juice
Incet, incet se contureaza solutia problemei observand ca, pentru a declara o celula ca fiind turn, trebuie sa aflam componentele conexe ale celulelor turn mai joase decat ea. Acest lucru ne aduce la ideea de procesa aceste celule turn in ordinea inaltimii lor afland pentru fiecare componenta conexa corespunzatoare. In acelasi timp aflam si celule ce devin turn si sunt mai inalte. Pentru aceasta utilizam o coada de prioritati (un heap) in care pastram toate celule turn neprocesate inca ordonate descrescator dupa inaltime. Ajungem astfel la nimic altceva decat un algoritm de tip FILL modificat corespunzator cerintelor acestei probleme. Iata o descriere a acestuia:
Fie $A{~i,j~}$ inaltimea blocului aflat in pozitia $(i, j)$. Aflam inaltimea maxima la care poate urca nivelul sucului in fiecare celula. Daca notam aceasta inaltime cu B{~i,j~} solutia problemei va fi $suma( B{~i,j~} - A{~i,j~} )$.
Vom numi celula turn o celula $(i, j)$ care are propietatea ca $B{~i,j~} = A{~i,j~}$ (nu putem pune suc in ea pentru ca ar curge in afara matricei). Componenta conexa a unei celule turn $(i, j)$ este compusa din acele celule $(x, y)$ pentru care avem $B{~x,y~} = A{~i,j~}$. Definim inaltimea componentei conexe ca fiind inaltimea comuna a tuturor celulelor componente. Facem urmatoarele observatii utile in rezolvarea problemei:
# Celulele de pe marginea matricei sunt celule turn
# Celula $(x, y)$ devine celula turn daca este vecina unei celule $(i, j)$ ce face parte dintr-o componenta conexa si are propietatea ca $B{~i,j~} < A{~x,y~}$.
PAS 1: Se introduc in coada de prioritati
pozitiile de pe margine
Incet, incet se contureaza solutia problemei observand ca, pentru a declara o celula ca fiind turn, trebuie sa aflam componentele conexe ale celulelor turn mai joase decat ea. Acest lucru ne aduce la ideea de procesa aceste celule turn in ordinea inaltimii lor afland pentru fiecare componenta conexa corespunzatoare. In acelasi timp aflam si celule ce devin turn si sunt mai inalte. Pentru aceasta utilizam o coada de prioritati (un heap) in care pastram toate celule turn neprocesate inca ordonate descrescator dupa inaltime. Ajungem astfel la nimic altceva decat un algoritm de tip $FILL$ modificat corespunzator cerintelor acestei probleme. Iata o descriere a acestuia:
==code(cpp) |
PAS 1: Se introduc in coada de prioritati pozitiile de pe margine
PAS 2: Cat timp heapul nu este gol:
* se selecteaza celula turn cea mai joasa
* se afla componenta conexa a acesteia
* se introduc in coada de prioritati
celulele vecine cu componenta conexa construita
care au inaltimea mai mare decat inaltimea
componentei
* se introduc in coada de prioritati celulele vecine cu componenta conexa construita care au inaltimea mai mare decat inaltimea componentei
==
Se poate modifica usor algoritmul FILL pentru a rezolva toate aceste cerinte. Complexitatea finala a algoritmului va fi O(N^2*logN) deoarece, in cazul cel mai defavorabil, toate celulele sunt turn (un exemplu este cand matricea este piramidala) si in consecinta toate celulele vor fi introduse si scoase din heap necesitand logN pentru fiecare operatie. Aflarea componentelor conexe va necesita O(N^2) timp in total fiindca o celula va fi selectata o singura data intr-o componenta conexa si va fi accesata de maxim 4 ori de algoritmul FILL. Ca detalii de implementare, programatorii in C++ pot folosi cozile de prioritati din STL (pririority_queue ce se gaseste in headerul <queue>) pentru a reduce din complexitatea implementarii. Totusi, trebuie acordata atentie utilizarii acestora deoarece este posibil ca sursa sa depasesca timpul de executie.
Naptime
h2. Naptime
Vom incerca sa rezolvam problema, ignorand la inceput faptul ca sirul este circular. Astfel, problema se transforma intr-una relativ usoara, abordabila cu programare dinamica. O prima incercare ar fi sa realizam o astfel de rezolvare: A(i, j) = utilitatea de somn maxima care se poate obtine alegand j perioade din primele i.
Relatia de recurenta care se obtine este A(i, j)=max(A(i-k, j-k)+suma U[i-k+2]...U[i]) unde U este vectorul de utilitati. Din pacate aceasta abordare are dezavantajul ca are complexitatea de timp O(N*B^2) si de memorie O(N*B), neincadrandu-se nici in timp si nici in spatiu de memorie. Astfel, vom incerca sa imbunatatim aceasta dinamica modificand un pic semnificatia matricei A bazandu-ne pe faptul ca alegerea unei secvente continue de perioade aduca ca utilitate suma lor, mai putin prima perioada folosita:
