Silviu Bogan: ianuarie 2019

[C++, programare dinamică] Problema celui mai lung subșir comun

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Se dau două șiruri de caractere A și B, formate din litere mici ale alfabetului englez. Se cere găsirea unui șir de caractere C de lungime maximă care este subșir atât a lui A cât și a lui B.

Șirurile A și B se citesc din fișierul sircom.in, fiecare pe câte o linie. In fișierul sircom.out se va afișa pe prima linie lungimea celui mai lung subșir comun, iar pe a doua linie șirul găsit.

Rezolvare

Pentru a rezolva problema vom încerca să găsim o formulă de recurență pentru calculul lungimii celui mai lung subșir comun. Fie L[i][j] = lungimea celui mai lung subșir comun al subsecvențelor A[1, i] și B[1, j], pentru 1 ≤ i ≤ lungime(A) și 1 ≤ j ≤ lungime(B). Să presupunem că avem calculate toate valorile matricii L care preced elementul (p + 1, q + 1) (sunt fie pe aceeași linie și pe o coloană precedentă, fie pe o linie precedentă). Se disting două cazuri:

Dacă A[p + 1] == B[q + 1], atunci putem adăuga caracterul A[p + 1] celui mai lung subșir comun al secvențelor A[1, p] și B[1, q], obținând, pentru secvențele A[1, p + 1] și B[1, q + 1] un subșir comun de lungime maximă care este mai lung cu un caracter. Așadar, L[p + 1][q + 1] = L[p][q] + 1.
Dacă A[p + 1] != B[q + 1], atunci nu putem extinde niciun subșir de lungime maximă calculat anterior și va trebui să salvăm în L[p + 1][q + 1] lungimea celui mai lung subșir de lungime maximă calculat până acuma. Această valoare este dată de maximul dintre L[p][q + 1] și L[p + 1][q].

Timpul de execuție al acestei metode este O(N·M), unde N este lungimea primului șir, iar M este lungimea celui de-al doilea șir. Memoria folosită de algoritm este tot O(N·M), deoarece matricea L are N linii și M coloane. Putem reduce memoria folosită la O(N + M), dar sacrificăm astfel posibilitatea reconstituirii soluției. Vom descrie însă și această metodă.

Pentru a reconstitui soluția vom proceda similar cu metoda de reconstituire a unui drum a cărui lungime minimă a fost calculată cu algoritmul lui Lee. Vom folosi o functie recursivă reconst(x, y) care va afișa un subșir comun de lungime maximă. In primul rând, condiția de ieșire din recursivitate va fi dacă x < 1 sau y < 1. Dacă nu, verificăm dacă A[x] == B[y], iar dacă da, apelăm recursiv reconst(x - 1, y - 1) și afișăm A[x]. Dacă A[x] != B[y] atunci apelăm recursiv fie reconst(x - 1, y), în cazul în care L[x - 1][y] > L[x][y - 1], fie reconst(x, y - 1) altfel.

Pentru a simplifica implementarea am folosit tipul de date string pentru reținerea șirurilor de caractere. Indicii șirurilor de caractere încep de la 0, așa că trebuie să fim atenți la cum comparăm caracterele individuale, deoarece indicii matricei L încep de la 1. Singura inițializare care trebuie făcută este completarea liniei și coloanei 0 a matricei L cu valoarea 0, pentru a evita cazurile particulare ale recurenței descrise.

Prezentăm în continuare implementarea algoritmului de rezolvare.

Pentru a reduce memoria folosită la O(N + M) trebuie observat că pentru calculul unei valori L[i][j] nu avem nevoie decât de valori de pe linia curentă (L[i][j - 1]) și de pe linia precedentă (L[i - 1][j] și L[i - 1][j - 1]). Așadar, este de ajuns să folosim doar doi vectori de lungime egală cu lungimea șirului B. Unul dintre vectori, L1 va reprezenta linia precedentă liniei curente, iar celălalt vector, L2, va reprezenta chiar linia curentă. Noua formă a formulei de recurență este:

După fiecare calculare completă a lui L2, înainte de începerea unei noi iterații vectorul L2 va trebui copiat în L1, pentru ca valorile calculate la pasul curent să poată fi folosite la pasul următor. La sfârșitul algoritmului, cei doi vectori vor avea același conținut, deci răspunsul problemei va fi dat fie de L1[lungime(B)] fie de L2[lungime(B)].

Prezentăm doar modificările relevante:

Această implementare este preferabilă dacă memoria disponibilă este limitată și dacă nu se cere reconstituirea unei soluții, acest lucru fiind imposibil deoarece algoritmul păstrează doar valorile finale ale recurenței, nu și pe cele inițiale.

Exerciții:

a) Afișați întreaga matrice L pentru a înțelege mai bine formula de recurență.

b) Afișați toate subșirurile comune de lungime maximă.

c) In implementarea de mai sus am transmis parametrii A și B prin referință. Unde era indicat să se folosească transmitere prin referință constantă?

d) Scrieți o implementare care folosește vectori clasici de caractere în loc de tipul string.

e) Scrieți un program care afișează acel subșir comun de lungime maximă care este primul din punct de vedere alfabetic.

f) Se poate evita copierea vectorului L2? Dacă da, cum?

[C++, programare dinamică] Problema subșirului crescător maximal

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

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.

Exemplu:

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.

La pasul (1), dacă A[i] este mai mare decât toate elementele diferite de infinit din L, atunci A[i] se va suprascrie peste cea mai din stânga valoare egală cu infinit. Putem implementa acest pas eficient în timp O(log N) folosind o căutare binară.

Să prezentăm 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]	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf
P[i]

La pasul i = 1, se suprascrie A[1] = 6 peste cea mai mică valoare din L, dar care este strict mai mare decât 6. Singura posibilitate este să suprascriem elementul A[1] peste primul inf. In P[1] vom reține 1:

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]	6	inf	inf	inf	inf	inf	inf	inf	inf	inf
P[i]	1

La pasul i = 2, A[2] = 3 se va suprascrie peste L[1] = 6, iar P[2] devine 1:

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]	3	inf	inf	inf	inf	inf	inf	inf	inf	inf
P[i]	1	1

A[3] se va suprascrie peste L[2], iar P[3] va deveni 2. Se procedează în acest mod pentru fiecare element din A, iar forma finală a vectorilor este:

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	2	4	10	11	inf	inf	inf	inf	inf
P[i]	1	1	2	3	1	2	4	3	1	5

Lungimea lg este așadar 5, deoarece există 5 elemente diferite de inf în L. Soluția este dată de A[2], A[3], A[4], A[7] și A[10].

Prezentăm în continuare implementarea acestei metode de rezolvare.

Deși acest algoritm este mai eficient, spre deosebire de metoda clasică, nu poate fi adaptat la toate variațiunile problemei.

Exercițiu: scrieți un program care determină cel mai scurt subșir crescător maximal și altul care determină numărul de subșiruri crescătoare maximal.

[C++, programare dinamică] Problema subsecvenței de produs maxim

Problema este de la finalul acestui fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Enunțul problemei

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).

Rezolvarea completă

Este aici. Mai jos sunt rezolvări care funcționează doar pe anumite date de intrare.

Cod sursă 1

In această secțiune se rezolvă problema pentru cazul numerelor reale strict pozitive, rezolvarea fiind foarte asemănătoare cu problema subsecvenței de sumă maximă.

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;
}

Cod sursă 2

In această secțiune se rezolvă problema pentru cazul numerelor întregi (negative, zero și pozitive).

#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;
}

Intrări și ieșiri

1. (pentru primul cod sursă)

6
2 3 4 2 3 1

rezultă ieșirea:

144 1 5

2. (pentru primul cod sursă)

5
2 2 0.1 2 2

rezultă ieșirea:

4 1 2

Alte intrări

3 5 1 2

-6 1 -3 4 5 -1 3 -8 -9 1

-2 -3 -4 -2 -3 1

2 5 -1 -2 -4

1 2 0 -4 5 6 0 7 1

3 -8

-8 3

-3