Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-10-12 10:37:54.
Revizia anterioară   Revizia următoare  

Dk

Kcity

"Bandwidth"-ul si "Pathwidth"-ul unui graf

Sa consideram ca nodurile unui graf sunt renumerotate cu numere de la 1 la N si sa notam cu BMAX valoarea maxima a diferentei (in modul) dintre numerele asociate a doua noduri adiacente. "Bandwidth"-ul B al unui graf este valoarea minima a lui BMAX dintre toate renumerotarile posibile ale nodurilor. Determinarea acestei valori B nu se poate realiza in timp polinomial. In cadrul problemei date, nodurile au fost deja numerotate corespunzator, astfel incat graful sa aiba un "bandwidth" mic, egal cel mult cu valoarea K data.

"Pathwidth"-ul unui graf este un numar ce reflecta cat de mult structura grafului este asemanatoare cu cea a unui drum. Daca un graf G are un "pathwidth" P, atunci exista un graf-drum D, cu nodurile D1, D2, ..., DX, avand urmatoarele proprietati:

  • fiecare nod Di corespunde unei submultimi de cel mult P noduri ale grafului G
  • oricare doua noduri adiacente ale grafului G, u si v, se afla impreuna in cel putin una din submultimile D1,...,DX
  • orice nod u al grafului G apartine unor multimi Di care formeaza un sub-drum al grafului D (mai exact, niciun nod u al lui G nu poate sa apartina unui submultimi Di, sa nu apartina unei submultimi Dj (j > i) si apoi sa apartina din nou unei alte submultimi Dk (k > j)

Daca avem o renumerotare a unui graf G corespunzatoare unui "bandwidth" mic, atunci putem obtine si o descompunere cu "pathwidth" mic a grafului G, care ne va ajuta sa rezolvam problema.

Solutie de complexitate O(N * numar_stari * K3)

Elementele teoretice prezentate mai sus nu sunt neaparat necesare pentru a rezolva problema. Se "ghiceste" usor ca problema se rezolva folosind programare dinamica pe un numar exponential de stari, care depinde, insa, numai de K, care este o valoare mica.

Vom calcula urmatoarele valori:

  • minp[i][S] = numarul minim de drumuri cu care se pot acoperi nodurile 1,2,...,i, iar starea la pasul i sa fie S
  • minc[i][S] = numarul minim de cicluri cu care se pot acoperi nodurile 1,2,...,i, iar starea la pasul i sa fie S (nu trebuie sa apartina neaparat unui ciclu inchis si nodurile din cadrul starii curente sau cele care apartin deja unor drumuri care au capetele in cadrul starii curente)

O stare S la pasul i este reprezentata de starea ultimelor K noduri (i-K+1, i-K+2, ..., i). O prima idee de definire a starii este urmatoarea: fiecare nod se poate afla in una din urmatoarele 3 stari:

  • are gradul 0 (este un drum ce consta doar din nodul respectiv)
  • are gradul 1 (este un capat al unui drum)
  • are gradul 2 (se afla in interiorul unui drum sau al unui ciclu (in orice caz, daca un nod are gradul 2, el nu mai prezinta interes in algoritmul nostru)

Definind o stare astfel, ar exista 3K stari in total. La fiecare pas i, am considera toate starile S' de la pasul i-1 si, adaugand nodul i, impreuna cu unele muchii, la starea S', am obtine niste stari S, pentru pasul i. Avem urmatoarele optiuni:

  • pentru cazul acoperii cu drumuri
    • nodul i formeaza un drum nou (are gradul 0) => numarul de drumuri creste cu 1
    • nodul i extinde un drum deja existent (il legam de un nod j de grad 0 sau 1, cu conditia sa existe muchia i-j) => numarul de drumuri ramane acelasi
    • nodul i leaga doua drumuri diferite (il legam de nodurile j si k de grad 0 sau 1, unind astfel doua drumuri) => numarul de drumuri scade cu 1
  • pentru cazul acoperirii cu cicluri
    • nodul i formeaza un drum nou (are gradul 0) => numarul de cicluri ramane la fel
    • nodul i extinde un drum deja existent (il legam de un nod j de grad 0 sau 1, cu conditia sa existe muchia i-j) => numarul de cicluri ramane la fel
    • nodul i leaga doua drumuri diferite (il legam de nodurile j si k de grad 0 sau 1, unind astfel doua drumuri) => numarul de cicluri ramane la fel
    • nodul i leaga cele 2 capete ale unui drum => numarul de cicluri creste cu 1
    • daca nodul i > K, trebuie sa ne asiguram, inainte de a trece mai departe, ca nodul i-K are gradul 2 (se afla in interiorul unui drum sau al unui ciclu) => optiunile de mai sus nu sunt valide decat daca, in urma aplicarii lor, nodul i-K are gradul 2

Observam o dificultate in cazul in care nodul i trebuie sa uneasca doua drumuri de grad 1. In cazul acoperirii cu drumuri, trebuie sa ne asiguram ca el nu leaga capetele aceluiasi drum (inchizand, de fapt, un ciclu, in timp ce noi credeam ca a unit 2 drumuri). In cazul acoperii cu cicluri trebuie sa putem realiza aceeasi distinctie. Asadar, modul in care am definit starea nu este corect, desi era, poate, cel mai intuitiv.

O stare va trebui definita in felul urmator: fiecare din cele K noduri ale starii se poate afla in una din urmatoarele situatii:

  • are gradul 0 (este un drum ce consta doar din nodul respectiv) - se codifica prin 0
  • are gradul 1 si este capatul unui drum care are un identificator bine specificat - se codifica prin identificatorul drumului
  • are gradul 2 (se afla in interiorul unui drum sau al unui ciclu) - se codifica prin -1

De exemplu, pentru K=6, starea S=(-1, 1, 0, 2, -1, 1) specifica faptul ca primul si al cincilea nod au gradul 2, al treilea nod are gradul 0, al doilea si al saselea nod sunt capetele aceluiasi drum, care are identificatorul 1, iar al patrulea nod este capatul unui drum ce are identificatorul 2 (celalalt capat fiind ramas undeva in urma).

Conform noii definitii a starilor, acestea trebuie generate explicit. Observam ca doar doua noduri pot fi capetele aceluiasi drum, ca identificatorii drumurilor ii putem genera de la 1 pana la cate drumuri pot exista intr-o stare (maxim K) si ca putem considera identificatorii drumurilor sortati in ordinea in care apar in cadrul starii nodurile ce sunt capetele acestora. De exemplu, starea S=(-1, 2, 0, 1, -1, 2) nu ar avea sens, fiind echivalenta cu cea prezentata mai sus, schimband doar identificatorii drumurilor intre ei. Pentru K=6 exista 2364 astfel de stari.

Raspunsul dorit il gasim intr-una din starile de la pasul N:

  • pentru acoperirea cu drumuri se alege minimul dintre toate valorile minp[N][S]
  • pentru acoperirea cu cicluri se alege valoarea minc[N][S], unde S este starea in care toate nodurile au gradul 2 ; daca aceasta valoare este infinit, atunci rezultatul este -1

Consir

Sa presupunem ca dorim sa aflam rezultatul pentru secventa maxima 1, 2 ... M. Fie F1, F2, ... FM frecventele numerelor de la 1 la M (numarul de aparitii). Sa construim acum un vector P cu semnificatia Pi = F1* F2 * ... * Fi. Datoria faptului ca rezultatul este mai mic decat 263 este clar ca nu avem mai mult de 63 de pozitii pentru care Fi>1, deci la fiecare pas trebuie sa updatam subsecventele care se termina intr-o pozitie cu Fi>1. Algoritmul in pseudocod pentru a calcula vectorul Res cu semnificatia Resi egal cu numarul de consiruri de lungime i devine

Res[M] = P[M];
pentru i = n-1, 1 executa
   Res[i] = Res[i+1] + P[M]/P[M-i];
   pentru j astfel incat F[j] >= 2 si j >= i+1
       Res[i] = Res[i] - P[j]/P[j-i-1] + P[j-1]/P[j-i-1];
   sfarsit pentru
sfarsit pentru

Polig

Exista mai multe solutii care se incadreaza in timp pentru limitele date, o idee ar fi ca punctele sa fie sortate dupa unghiul cu axa Ox. Apoi, folosind programare dinamica vom construi o matrice cu semnificatia a[i][j] = costul maxim astfel incat sa plecam din orginea planului si sa construim un drum care are ultimele puncte i si j. In total, memoria este O(n2) si complexitatea in timp O(n3). Exista o solutie O(n2 lg2n) data de Mugurel Ionut Andreica, gasirea ei o lasam ca un exercitiu pentru cititori :-). Daca aveti nevoie de ajutor nu ezitati sa folositi forumul.