Considerăm un vector A cu N elemente numere întregi. Un subșir a lui A este o secvență de elemente nu neapărat consecutive ale lui A, dar a căror ordine relativă în A este păstrată. Un subșir crescător al lui A este un subșir al lui A ale cărui elemente sunt ordonate crescător. Un subșir crescător maximal este un subșir crescător la care nu se mai pot adăuga elemente fără a strica proprietatea de subșir crescător. Se cere determinarea celui mai lung subșir crescător maximal al vectorului A.

Datele de intrare se citesc din fișierul subsir.in. In fișierul subsir.out se va afișa pe prima linie lungimea lg a celui mai lung subșir crescător maximal găsit, iar pe următoarea linie se vor afișa valorile (în număr de lg) care constituie un astfel de subșir. Se poate afișa orice soluție dacă există mai multe.

subsir.in	subsir.out
10 6 3 8 9 1 2 10 4 -1 11	5 6 8 9 10 11

Problema admite o rezolvare prin programare dinamică în timp O(N²), dar și o rezolvare greedy în timp O(N·log N). Vom prezenta ambele rezolvări.

Rezolvarea prin programare dinamică presupune găsirea unei formule de recurență care fie va furniza direct răspunsul problemei, fie va fi doar un pas intermediar în rezolvarea problemei. In acest caz, putem găsi o formulă de recurență pentru Lg care va conduce direct la calcularea acestei valori. Raționamentul este unul similar cu cel de la problema anterioară. Fie L[i] = lungimea celui mai lung subșir crescător maximal care se termină e poziția i. Inițial vom considera L[i] = 1 pentru fiecare 1 ≤ i ≤ N. Evident, L[1] va rămâne întotdeauna 1, deoarece singurul subșir al unui vector cu un singur element este însuși acel vector.

Să presupunem acum că avem calculate valorile L[1], L[2], …, L[k] pentru un k < N. Ne propunem să calculăm L[k + 1]. Folosind definiția lui L, ne propunem așadar să calculăm lungimea celui mai lung subșir crescător maximal care se termină pe poziția k + 1, știind lungimile celor mai lungi subșiruri crescătoare maximal care se termină pe pozițiile 1, 2, …, k. Stiind aceste valori, este evident că pentru a maximiza lungimea subșirului care se termină pe poziția k + 1 trebuie adăugat A[k + 1] unui subșir maximal care se termină pe o poziție j < k + 1, pentru care L[j] are valoarea maximă și pentru care A[j] < A[k + 1], deoarece subșirul trebuie să fie crescător. Așadar obținem recurența:

    L[1] = 1
    L[i] = 1 + max{L[j] | A[j] < A[i]} sau 1 dacă mulțimea respectivă e vidă, unde 1 ≤ j < i.

( n.e. Trebuie adăugat A[k + 1] ca o continuare la subșirul crescător maximal de lungime maximă descoperit până la k, acest subșir se termină pe o poziție j < k + 1 și e necesar ca A[j] < A[k + 1]. )

Timpul O(N²) rezultă din faptul că pentru fiecare i trebuie să determinăm minimul subsecvenței [1, i – 1], rezultând un număr pătratic de operații. Valoarea lg este dată de valoarea maximă din vectorul L.

Pentru determinarea valorilor care fac parte din subșirul crescător maximal vom folosi un vector P unde P[i] = poziția ultimului element care a intrat în calculul lui L[i] sau 0 dacă nu există. In alte cuvinte, dacă L[i] = 1 + max{L[j] | A[j] <  A[i]} = 1 + L[max], 1 ≤ j < i, atunci vom avea P[i] = max.

Vom evidenția în continuare modul de execuție al algoritmului pe exemplul dat. Inițial avem:

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	1	1	1	1	1	1	1	1	1	1
P[i]	0	0	0	0	0	0	0	0	0	0

La pasul i = 2 căutăm poziția max a celui mai mare element din subsecvența [1, 1] a vectorului L pentru care A[max] < A[2]. Nu se găsește nicio astfel de poziție, așa că totul rămâne neschimbat.

La pasul i = 3 căutăm același max din subsecvența [1, 2] a vectorului L pentru care are loc A[max] < A[3]. Putem alege de data aceasta fie max = 1, fie max = 2, ambele poziții respectând condițiile impuse. Vom alege max = 1. Așadar, L[3] devine L[max]+1 = L[1]+1 = 2, iar P[3] devine max, adică 1. Am marcat cu roșu actualizările:

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	1	1	2	1	1	1	1	1	1	1
P[i]	0	0	1	0	0	0	0	0	0	0

Se procedează în acest fel până la completarea vectorilor L și P. Forma lor finală este prezentată mai jos. Este ușor de verificat corectitudinea calculării acestor vectori conform definiției lor.

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	1	1	2	1	3	1	4	3	1	5
P[i]	0	0	1	3	0	5	4	6	0	7

Am marcat mai sus coloanele care identifică o soluție optimă. Vom explica în continuare cum putem folosi vectorul P pentru a obține valorile soluției optime. Fie sol poziția celui mai mare element din vectorul L. In acest caz, sol = 10. Este clar că ultima valoare din subșirul crescător maximal este atunci A[10]. Deoarece P[i] reprezintă ultima valoare care a intrat în calcului lui L[i] (sau predecesorul lui i), P[10] reprezintă poziția penultimei valori a subșirului crescător maximal găsit. Atunci A[ P[10] ] reprezintă penultima valoare a soluției. Mergând în continuare cu acest raționament, A[ P[ P[10] ] ] va reprezenta antepenultima valoare și așa mai departe până când ajungem la o valoare k pentru care P[k] = 0. Când acest lucru se întâmplă, am găsit prima valoare a subșirului soluție.

Vom folosi așadar o funcție recursivă care va reconstitui soluția folosind vectorul P. Acest vector se numește vector de predecesori, iar ideea folosită în construcția sa poate fi aplicată la orice problemă de programare dinamică la care se cere afișarea unor obiecte care constituie un optim cerut. Prezentăm întregul program care rezolvă problema.

Această rezolvare poate fi optimizată folosind structuri de date avansate, cum ar fi arbori de intervale sau arbori indexați binar, dar aceste structuri nu vor fi prezentate în cadrul acestui capitol și nu sunt nici cea mai bună metodă de a rezolva optim această problemă.

Vom prezenta în continuare o rezolvare optimă cu timpul de execuție O(N · log N) care nu presupune decât noțiuni algoritmice elementare.

Vom considera A ca fiind vectorul citit și vom folosi încă doi vectori L și P, dar care nu vor avea aceeași semnificație ca până acum.

Mai întâi inițializăm vectorul L cu valoarea infinit. Aplicăm apoi următorul algoritm:

• Pentru fiecare i de la 1 la N execută
• Suprascrie A[i] peste cel mai mic element din L, dar care este strict mai mare decât A[i]. (1)
• Fie k poziția peste care a fost suprascris A[i]. P[i] ia valoarea k.
• Lungimea vectorului L (făcând abstracție de pozițiile marcate cu infinit) reprezintă lungimea celui mai lung subșir crescător maximal.
• Fie lg lungimea vectorului L. Pentru a reconstitui soluția, se caută în vectorul P poziția ultimei apariții a valorii lg. Fie această poziție k_lg. Se caută apoi ultima apariție a valorii lg – 1, dar care apare înainte de poziția k_lg. Aceasta va fi așadar pe o poziție k_{lg – 1} < k_lg. Se procedează similar pentru valorile lg – 2, lg – 3, …, 2, 1. Soluția va fi dată de subșirul: A[k₁], A[k₂], …, A[k_lg]. Putem implementa reconstituirea tot recursiv.

Rezolvarea care folosește programarea dinamică este funcția subsecv6.

#include <fstream>
#include <iostream>
using namespace std;

const int inf = 1 << 30;
const int maxn = 2001;

float subsecv4(float A[], int N,
 int &inceput, int &sfarsit)
{
 float max = -inf;

 for (int st = 1; st <= N; ++st)
 {
  for (int dr = st; dr <= N; ++dr)
  {
   float temp = 1;
   for (int i = st; i <= dr; ++i)
    temp *= A[i];

   if (temp > max)
   {
    inceput = st;
    sfarsit = dr;
    max = temp;
   }
  }
 }

 return max;
}


float subsecv5(float A[], int N,
 int &inceput, int &sfarsit)
{
 float max = -inf;

 for (int st = 1; st < N; ++st)
 {
  float temp = 1;
  for (int dr = st; dr <= N; ++dr)
  {
   temp *= A[dr];
   if (temp > max)
   {
    inceput = st;
    sfarsit = dr;
    max = temp;
   }
  }
 }

 return max;
}

float subsecv6(float A[], int N,
 int &inceput, int &sfarsit)
{
 float max = A[1];
 int inceput_temp = 1;
 float S[maxn];
 S[1] = A[1];
 inceput = sfarsit = 1;

 for (int i = 2; i <= N; ++i)
 {
  if (S[i - 1] * A[i] > A[i])
  {
   S[i] = S[i - 1] * A[i];
  }
  else
  {
   inceput_temp = i;
   S[i] = A[i];
  }

  if (S[i] > max)
  {
   inceput = inceput_temp;
   sfarsit = i;
   max = S[i];
  }
 }

 return max;
}

int main()
{
 float A[maxn], N;

 ifstream in("subsecv.in");
 in >> N;
 for (int i = 1; i <= N; ++i)
 {
  in >> A[i];
 }
 in.close();

 ofstream out("subsecv.out");
 int inceput, sfarsit;
 // Toate cele 3 functii de mai sus se
 // apeleaza identic.
 float max = subsecv6(A, N,
  inceput, sfarsit);
 out << max << " " << inceput <<
  " " << sfarsit << endl;
 out.close();

 return 0;
}

#include <fstream>
#include <vector>
using namespace std;

const int inf = 1 << 30;
const int maxn = 100001;

double produs(vector<double> &A, int a, int b)
{
    double r = A[a];
    for (int i = a + 1; i <= b; ++i)
    {
        r *= A[i];
    }
    return r;
}

double produs_maxim_secv_fara_0(vector<double> &A, int a, int b,
    int &inceput, int &sfarsit)
{
    if (a == b)
    {
        inceput = a;
        sfarsit = a;
        return A[a];
    }

    int primul_negativ = -1;
    int negative = 0;
    int ultimul_negativ;

    for (int i = a; i <= b; ++i)
    {
        if (A[i] >= 0)
        {
            continue;
        }

        ++negative;
        if (primul_negativ < 0)
        {
            primul_negativ = i;
        }
        ultimul_negativ = i;
    }

    if (negative % 2 == 0)
    {
        inceput = a;
        sfarsit = b;
        return produs(A, a, b);
    }

    if (primul_negativ + 1 > b)
    {
        inceput = a;
        sfarsit = b - 1;
        return produs(A, a, b - 1);
    }

    if (ultimul_negativ - 1 < a)
    {
        inceput = a + 1;
        sfarsit = b;
        return produs(A, a + 1, b);
    }

    double p1 = produs(A, primul_negativ + 1, b);
    double p2 = produs(A, a, ultimul_negativ - 1);
    if (p1 > p2)
    {
        inceput = primul_negativ + 1;
        sfarsit = b;
        return p1;
    }

    inceput = a;
    sfarsit = ultimul_negativ - 1;
    return p2;
}

double subsecv(vector<double> &A, int N,
    int &inceput, int &sfarsit)
{
    double maxim = A[1];
    int i = 1, j;
    while (i <= N)
    {
        while (i <= N && A[i] == 0)
        {
            ++i;
        }
        j = i;
        while (j <= N && A[j] != 0)
        {
            ++j;
        }

        int inceput_temp, sfarsit_temp;
        double p_nou = produs_maxim_secv_fara_0(A, i, j - 1,
            inceput_temp, sfarsit_temp);
        if (maxim <= p_nou)
        {
            maxim = p_nou;
            inceput = inceput_temp;
            sfarsit = sfarsit_temp;
        }

        i = j;
    }

    return maxim;
}

rezultă ieșirea:

5
2 2 0.1 2 2

Considerăm un număr natural N și un vector A cu N elemente numere întregi. O subsecvență [st, dr] a vectorului A reprezintă suma tuturor elementelor acelei subsecvențe. Se cere determinarea unei subsecvențe de sumă maximă.

Datele de intrare se citesc din fișierul subsecv.in, iar suma maximă se va afișa în fișierul subsecv.out.

subsecv.in	subsecv.out
6 1 -3 4 5 -1 3 -8 -9 1	11

Vom prezenta trei metode de rezolvare, începând de la o metodă trivială și sfârșind cu metoda optimă de rezolvare, care constă într-o singură parcurgere a vectorului.

In implementările oferite ca model vom prezenta doar o funcție subsecvi(A, N) care primește ca parametri vectorul A respectiv dimensiunea acestuia și returnează suma maximă a unei subsecvențe. Considerăm citirea și afișarea ca fiind cunoscute.

Prima metodă constă în verificarea tuturor subsecvențelor vectorului de intrare A. Pentru fiecare subsecvență [st, dr] vom parcurge elementele A[st], A[st + 1], …, A[dr] și vom face suma acestora. Dacă această sumă este mai mare decât maximul curent (inițializat la început cu o valoare foarte mică: -infinit), actualizăm maximul curent. Complexitatea acestei metode este O(N³), deoarece există O(N²) subsecvențe și fiecare dintre acestea trebuie parcursă pentru a-i afla suma.

Putem implementa această metodă în felul următor:

A doua metodă de rezolvare are complexitatea O(N²) și este o simplă optimizare a primei metode. Vom încerca să eliminăm parcurgerea prin care facem suma subsecvenței [st, dr], sau, altfel spus, vom încerca să calculăm suma fiecărei subsecvențe pe măsură ce acestea sunt generate și nu pentru fiecare în parte printr-o parcurgere. Să presupunem că știm care este suma temp a unei subsecvențe [st, dr]. Atunci suma subsecvenței [st, dr + 1] va fi temp + A[dr + 1]. Vom inițializa așadar temp cu 0 pentru fiecare st, iar apoi vom aduna, pentru fiecare dr, pe A[dr] la temp și îl vom compara pe temp cu max:

Această implementare este deja relativ eficientă pentru vectori cu un număr de elemente de până la ordinul miilor, spre deosebire de prima implementare care este aplicabilă doar pentru un număr de elemente de ordinul sutelor. Putem obține însă o rezolvare și mai eficientă, care funcționează rapid pe vectori cu sute de mii sau chiar milioane de elemente.

Cea de-a treia metodă folosește paradigma programării dinamice pentru a obține o rezolvare în O(N). Fie S[i] = suma maximă a unei subsecvențe care se termină cu elementul i. Să presupunem că, pentru un anume 1 ≤ k < N, cunoaștem valoarea lui S[k]. Ne interesează să-l obținem pe S[k + 1] din S[k]. Observăm că avem două posibilități:

1. Adăugăm elementul k + 1 la sfârșitul subsecvenței de sumă maximă care se termină cu elementul k, obținând o subsecvență de sumă A[k + 1] + S[k],

2. Ignorăm subsecvența de sumă maximă care se termină cu elementul k și considerăm subsecvența formată doar din elementul k + 1, aceasta având suma A[k + 1].

Evident vom alege maximul sumelor aferente celor două cazuri. Așadar, obținem următoarea formulă de recurență:

S[k + 1] = max(A[k + 1] + S[k], A[k + 1]).

Să evidențiem modul de execuție al algoritmului pe exemplul dat. Inițial avem:

i	1	2	3	4	5	6	7	8	9	10
A[i]	-6	1	-3	4	5	-1	3	-8	-9	1
S[i]	-6

Pentru S[2] luăm maximul dintre S[1] + A[2] și A[2].
S[1] + A[2] = -1, iar A[2] = 1. Maximul este așadar A[2] = 1:

i	1	2	3	4	5	6	7	8	9	10
A[i]	-6	1	-3	4	5	-1	3	-8	-9	1
S[i]	-6	1

Se observă ușor că subsecvența de sumă maximă care se termină pe poziția 2 are suma 1 (cealaltă posibilitate fiind doar subsecvența [1, 2] care are suma -5), deci se respectă definiția lui S.

La sfârșit, vectorul S este următorul. Se poate verifica, folosind eventual implementările precedente, că acesta este corect calculat.

i	1	2	3	4	5	6	7	8	9	10
A[i]	-6	1	-3	4	5	-1	3	-8	-9	1
S[i]	-6	1	-2	4	9	8	11	3	-6	1

[ n.e. In loc de max = -inf trebuia max = A[1]. ]

Exerciții:

a) Modificați implementările date pentru a afișa și pozițiile de început și de sfârșit a unei subsecvențe de sumă maximă.

b) Se cere o subsecvență de produs maxim, iar numerele sunt reale. Rezolvați problema atât pentru numere strict pozitive cât și pentru numere nenule (dar care pot fi negative).

c) Se dă o matrice și se cere determinarea unui dreptunghi de sumă maximă. Ultimul algoritm prezentat poate fi extins pentru rezolvarea problemei în O(N³). Cum?

Introducere în problema labirintului aici.

void toate_drumurile_nerec(int D[maxn][maxn],
 int N, ofstream &out)
{
 Nod *nod = new Nod;
 nod->x = 2; // aici se înlocuiește (2, 5) cu poziția de pornire
 nod->y = 5;

 queue<Nod *> Q;
 Q.push(nod);

 while (!Q.empty())
 {
  Nod *p = Q.front();
  Q.pop();

  for (int i = 0; i < 4; ++i)
  {
   int newx = p->x + dx[i];
   int newy = p->y + dy[i];

   if (valid(N, newx, newy))
    if (D[newx][newy] == D[p->x][p->y] + 1)
    {
     Nod *v = new Nod;
     v->x = newx;
     v->y = newy;
     v->parinte = p;
     
     if (p->copil1 == NULL)
     {
      p->copil1 = v;
     }
     else if (p->copil2 == NULL)
     {
      p->copil2 = v;
     }
     else if (p->copil3 == NULL)
     {
      p->copil3 = v;
     }
     else if (p->copil4 == NULL)
     {
      p->copil4 = v;
     }
     else
     {
      // eroare
     }

     Q.push(v);
    }
  }
 }

 // afisare:

 stack<Nod *> s;
 s.push(nod);

 // parcurgere in adancime pentru gasirea tuturor frunzelor
 while (!s.empty())
 {
  Nod *n = s.top();
  s.pop();

  bool are_descendenti_directi = false;
  if (n->copil1 != NULL)
  {
   s.push(n->copil1);
   are_descendenti_directi = true;
  }
  if (n->copil2 != NULL)
  {
   s.push(n->copil2);
   are_descendenti_directi = true;
  }
  if (n->copil3 != NULL)
  {
   s.push(n->copil3);
   are_descendenti_directi = true;
  }
  if (n->copil4 != NULL)
  {
   s.push(n->copil4);
   are_descendenti_directi = true;
  }

  // daca este frunza (nu are descendenti directi)
  if (!are_descendenti_directi)
  {
   afiseaza_drum_radacina_frunza(n, out);
   // sau: afiseaza_drum_frunza_radacina(n);
  }
 }
}

struct Nod
{
 Nod *parinte = NULL;
 Nod *copil1 = NULL;
 Nod *copil2 = NULL;
 Nod *copil3 = NULL;
 Nod *copil4 = NULL;
 int x = -1,
  y = -1;
};

// afiseaza drumul de la o frunza la radacina
void afiseaza_drum_frunza_radacina(Nod *f, ofstream &out)
{
 while (f != NULL)
 {
  out << f->x << " " << f->y << endl;

  f = f->parinte;
 }
 out << endl;
}

// afiseaza drumul de la radacina la o frunza
void afiseaza_drum_radacina_frunza(Nod *f, ofstream &out)
{
 stack<Nod *> s;

 while (f != NULL)
 {
  s.push(f);

  f = f->parinte;
 }

 while (!s.empty())
 {
  f = s.top();
  s.pop();

  out << f->x << " " << f->y << endl;
 }
 out << endl;
}

toate_drumurile_nerec(D, N, out);

Am prezentat problema labirintului în cadrul secțiunii despre backtracking. Similar, se dă o matrice pătratică de dimensiune N, cu valori de 0 sau de 1, codificând un labirint. Valoarea 0 reprezintă o cameră deschisă, iar valoarea unu o cameră închisă. Se cere de data aceasta cel mai scurt drum de la poziția (1, 1) la poziția (N, N), mergând doar prin camere deschise și doar la stânga, dreapta, în jos sau în sus. Nu se poate trece de două ori prin același loc. Lungimea unui drum este dată de numărul de pași necesari parcurgerii drumului.

Vom citi datele de intrare din fișierul lee.in, iar în fișierul de ieșire lee.out vom afișa pe prima linie lungimea drumului minim, iar pe următoarele linii coordonatele care descriu un drum de lungime minimă.

lee.in	lee.out
4 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	6 1 1 2 1 3 1 3 2 3 3 3 4 4 4

Rezolvarea prin metoda backtracking de la problema în care se cereau toate ieșirile din labirint se poate aplica și la această variantă a problemei. Trebuie doar să generăm toate drumurile, iar apoi să-l alegem pe cel de lungime minimă. Această rezolvare nu este însă eficientă, deoarece are la bază o căutare exhaustivă.

Problema se poate rezolva eficient în timp O(N²) folosind algoritmul lui Lee (care este de fapt o parcurgere în lățime pentru cei familiarizați cu noțiuni de teoria grafurilor). Algoritmul poate fi privit ca un algoritm de programare dinamică. Pentru a evidenția acest lucru, să presupunem că vrem să aflăm lungimea drumului minim de la poziția (1, 1) a matricei până la poziția (p, q). Deoarece dintr-o poziție (x, y) ne putem deplasa în pozițiile învecinate cu (x, y) la nord, sud, est sau vest, putem scrie următoarea formulă:

D[p][q] = 1 + min(D[p – 1][q], D[p + 1][q], D[p][q – 1], D[p][q + 1]), unde D[x][y] reprezintă distanța minimă de la (1, 1) la (x, y). Pentru indici invalizi sau care reprezintă un zid, distanța minimă va fi infinit.

Există mai multe metode de implementare a acestui algoritm. Fie A matricea dată. Prima metodă reprezintă implementarea relației de recurență exact așa cum este dată, cu ajutorul unei funcții recursive. Vom folosi pentru această metodă o matrice D cu semnificația anterioară și o funcție recursivă Lee(A, N, x, y, D) care va construi această matrice. Vom iniția D[1][1] cu 0, iar în restul matricei cu infinit, semnificând faptul că acele valori nu au fost calculate încă.

Funcția Lee poate fi implementată astfel:

După apelul inițial lee(A, N, 1, 1, D), matricea D va fi calculată conform definiției sale, deci D[N][N] va conține distanța minimă.

Deși această metodă este cel mai ușor de implementat, nu este cea mai eficientă, deoarece funcția lee poate fi apelată de mai multe ori pentru aceeași poziție. Pentru a evidenția acest lucru vom prezenta modul de execuție al funcției de mai sus pe exemplul dat. Vom considera că vectorii de direcție (acest concept a fost definit la secțiunea dedicată metodei backtracking) sunt:

Inițial avem:

A	D
0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

Primul vecin al poziției (1, 1), conform vectorilor de direcție folosiți este (2, 1). Această poziție este validă, nu conține un zid și ∞ > 0 + 1. Se observă că și al doilea pas va conduce la poziția validă (3, 1). Așadar, după primii doi pași avem:

A	D
0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞

Primul vecin al poziției (3, 1), este (4, 1), poziția invalidă deoarece conține un zid. Al doilea vecin este poziția (3, 2), poziție validă. Funcția se autoapelează pentru această poziție și obținem:

A	D
0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 3 ∞ ∞ ∞ ∞ ∞ ∞

Din poziția (3, 2) prima dată se încearcă vecinul (4, 2), care este însă un zid. Se va merge în continuare la stânga încă doi pași, până obținem:

A	D
0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 3  4  5 ∞ ∞ ∞ ∞

Din poziția (3, 4) funcția se va apela prima dată pentru poziția (4, 4), obținându-se următoarea configurație:

A	D
0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 3  4  5 ∞ ∞ ∞ 6

Deoarece niciun vecin al poziției (4, 4) nu este valid pentru a se efectua apeluri recursive, se revine din recursivitate la poziția (3, 4), din care se efectuează apoi un autoapel pentru vecinul de sus, (2, 4):

A	D
0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	0 ∞ ∞ ∞ 1 ∞ ∞ 6 2 3  4  5 ∞ ∞ ∞ 6

Singurul apel recursiv valid din poziția (2, 4) este pentru poziția (2, 3), obținându-se:

A	D
0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	0 ∞ ∞ ∞ 1 ∞ 7  6 2 3  4  5 ∞ ∞ ∞ 6

Se revine din recursivitate până la poziția (3, 3), de unde, când se verifică vecinul (2, 3) se vor îndeplini toate condițiile necesare efectuării unui apel recursiv deoarece 7 > 4 + 1 = 5 și poziția (2, 3) este validă și conține o cameră deschisă. Forma finală a matricei D va fi:

A	D
0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	0 ∞ ∞ ∞ 1 ∞ 5  6 2 3  4  5 ∞ ∞ ∞ 6

Așadar, am actualizat de două ori valoarea D[2][3]. Vom încerca să găsim un algoritm care actualizează fiecare valoare o singură dată, dar vom prezenta mai întâi implementarea acestei metode:

Precizăm că am omis intenționat funcția care determină coordonatele ce descriu un drum de lungime minimă. Această funcție va fi prezentată la sfârșit.

Am afirmat la începutul acestei secțiuni că algoritmul lui Lee este de fapt o parcurgere in lățime. Acei cititori care cunosc parcurgerea în lățime și cea în adâncime probabil au observat că prima metodă este de fapt o parcurgere în adâncime, deoarece se merge în aceeași direcție până când se întâlnește un obstacol și abia apoi se revine la un pas anterior sau se schimbă direcția. Parcurgerile grafurilor vor fi prezentate într-un alt capitol, așa că nu vom detalia aici parcurgerea în lățime. Ideea de bază este să verificăm la fiecare pas toți vecinii poziției curente, iar apoi toți vecinii acestora și așa mai departe, până când se parcurge întreaga matrice. Datorită faptului că vom parcurge matricea uniform, fiecare element va fi analizat o singură dată.

Datorită modului în care parcurgem matricea, toate drumurile posibile vor fi parcurse în același timp, deci nu va exista posibilitatea completării unei părți a matricei D cu valori care vor trebui ulterior corectate, așa cum a fost cazul în implementarea inițială. Pentru a evidenția acest lucru vom prezenta modul de execuție al algoritmului pe exemplul dat.

Inițial avem:

A	D
0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0	0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

In C++ această funcție poate fi implementată în felul următor. Funcția funcționează atât pentru implementarea deja prezentată, cât și pentru implementările ce vor urma.

Soluția recursivă efectuează mai mulți pași decât soluția nerecursivă cu cât se fac mai multe apeluri recursive pentru poziții deja calculate, ceea ce echivalează cu cât există mai multe poziții în care se poate ajunge prin multiple căi.

	Exemplul din carte	Exemplul 4×4 doar cu camere deschise
Algoritm recursiv	10 apeluri recursive	52 de apeluri recursive
Algoritm optim nerecursiv	9 pași	16 pași

După parcurgerea din figură urmează revenirea din apelurile recursive care poate începe alte apeluri recursive.

#include <fstream>
#include <queue>
#include <utility>

using namespace std;

const int maxn = 101;
const int inf = 1 << 30;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

void citire(bool A[maxn][maxn], int &N)
{
 ifstream in("ex-a.in");
 in >> N;
 for (int i = 1; i <= N; ++i)
 {
  for (int j = 1; j <= N; ++j)
  {
   in >> A[i][j];
  }
 }
 in.close();
}

bool valid(int N, int x, int y)
{
 return x >= 1 && y >= 1 &&
  x <= N && y <= N;
}

void Lee_optim(bool A[maxn][maxn], int N,
 int x, int y,
 int D[maxn][maxn])
{
 queue<pair<int, int>> Q;
 Q.push(make_pair(x, y));

 while (!Q.empty())
 {
  pair<int, int> poz = Q.front();
  Q.pop();

  for (int i = 0; i < 4; ++i)
  {
   int newx = poz.first + dx[i];
   int newy = poz.second + dy[i];

   if (valid(N, newx, newy))
   {
    if (!A[newx][newy] &&
     D[newx][newy] > D[poz.first][poz.second] + 1)
    {
     D[newx][newy] = D[poz.first][poz.second] + 1;
     Q.push(make_pair(newx, newy));
    }
   }
  }
 }
}

void init(int D[maxn][maxn], int N, int x, int y)
{
 for (int i = 1; i <= N; ++i)
 {
  for (int j = 1; j <= N; ++j)
  {
   D[i][j] = inf;
  }
 }
 D[x][y] = 0;
}

int main()
{
 int N;
 bool A[maxn][maxn];
 int D1[maxn][maxn];
 int D2[maxn][maxn];

 citire(A, N);

 init(D1, N, 1, 1);
 Lee_optim(A, N, 1, 1, D1);

 init(D2, N, N, N);
 Lee_optim(A, N, N, N, D2);

 int max = -inf;
 int x = -1, y = -1;
 for (int i = 1; i <= N; ++i)
 {
  for (int j = 1; j <= N; ++j)
  {
   if (!A[i][j] &&
    D1[i][j] == D2[i][j])
   {
    if (D1[i][j] > max)
    {
     max = D1[i][j];
     x = i;
     y = j;
    }
   }
  }
 }

 ofstream out("ex-a.out");
 out << x << ' ' << y << endl;
 out.close();

 return 0;
}

Fișierul de intrare este ex-a.in și cel de ieșire este ex-a.out.

Se folosesc două matrice D construite din matricea de intrare A, se aplică același algoritm pt. ambele (algoritmul lui Lee) dar din puncte de pornire diferite (cele specificate în enunț). Se lasă algoritmul să ruleze pe toată suprafața matricelor. Se compară fiecare celulă din matricea D1 cu cea din matricea D2 de pe aceeași poziție, și dacă au aceeași valoare, se calculează treptat poziția valorii minime care se găsește în ambele matrice D pe aceeași poziție. Se ignoră valorile de 1 care reprezintă ziduri.

    D[p + 1][q + 1] = 1 + minim(D[p][q], D[p + 1][q], D[p][q + 1]).

a) Complexitatea algoritmului de calcul a distanței Levenshtein este O(N·M), unde N și M reprezintă lungimile celor două șiruri. Putem însă optimiza algoritmul dacă știm că putem transforma șirul A în șirul B într-un număr relativ mic de operații k. Cum ne poate ajuta această informație?

b) Considerăm existența unor costuri pentru fiecare operație precum și pentru caracterele asupra cărora se efectuează operații. Scrieți un program care rezolvă această variantă a problemei.

c) Scrieți un program care afișează noul șir A pentru fiecare operație efectuată.

d) Scrieți un program care determină numărul minim de caractere care trebuie inserate într-un șir pentru a-l transforma într-un palindrom.