Clasa a IX-a lecția 24 - 09 mai 2020

From Algopedia
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Clasament teme lecțiile 1 - 23

Pe categorii

Divizori / Primalitate / Ciur
Sortări
Matrici
Căutare binară
Stivă
Recursivitate
Parcurgeri matrice
Divide et Impera
Generale

Concursuri

Probleme OȘI
Probleme OJI

Lecție

Programare dinamică

Introducere

Similar cu tehnica Divide et impera, programarea dinamică este o metodă prin care rezolvăm probleme mai complexe, descompunându-le în subprobleme mai simple. Este însă o diferență majoră între cele două tehnici: Divide et impera poate fi aplicată doar dacă subproblemele în care descompunem problema originală nu se suprapun. De exemplu, Mergesort și Quicksort se pot folosi de tehnica Divide et impera pentru că la fiecare pas se împarte vectorul în două submulțimi complet distincte.

În general, problemele care se rezolvă folosind metoda programării dinamice sunt cele care necesită găsirea unei soluții optime. Folosind programarea dinamică, vom împărți în subprobleme pentru care găsim mai ușor soluția optimă și le vom combina pentru a calcula soluția optimă în problema originală.

Metodă

Înainte de a aplica programarea dinamică, trebuie să ne dăm seama dacă problema noastră se poate rezolva folosind această metodă. Altfel spus, trebuie să ne dăm seama dacă putem ajunge la o soluție optimă, din soluții optime obținute în subprobleme mai mici. Și pentru asta, avem de răspuns la două întrebări:

  • Cum știm în ce subprobleme mai mici putem împărți problema mare?
  • Cum știm să combinăm rezultatele optime obținute în subprobleme, pentru a răspunde la problema mare?

Nu există un răspuns generic la aceste întrebări. Totul depinde de problema pe care vrem să o rezolvăm. Experiența este foarte importantă în lucrul cu programarea dinamică, ea ne va ajuta să răspundem mai rapid la aceste întrebări.

Odată ce descoperim cum putem împărți problema și cum putem combina rezultatele, implementarea este cel de-al treilea pas. Acesta este, de obicei, cel mai simplu. Vom implementa o formulă de recurență prin care combinâm rezultatele, implementată de jos în sus (pornind de la cele mai mici probleme, către cele mai mari, până la soluția cerută).

Subsecvența de sumă maximă

Se dă un șir V de N elemente. Să se găsească subsecvența de sumă maximă.

Exemplu

Avem șirul: 5, -6, 3, 4, -2, 3, -3. Subsecvența de sumă maximă este formată din elementele 3, 4, -2, 3.

Soluție

Împărțim problema în subprobleme:

  • S[i] = Suma maximală a unei subsecvențe care se termină pe poziția i

Putem scoate răspunsul la problema originală combinând răspunsul acestor subprobleme? Da, răspunsul este chiar max(S[i]).

Cum calculăm S[i]? Vom presupune că am calculat deja toate sumele până la i - 1. Secvența de sumă maximă care se termină pe poziția i are două cazuri:

  • Dacă S[i - 1] este pozitiv, atunci S[i] = S[i - 1] + V[i] (adăugăm V[i] la subsecvența de sumă maximă care se termină pe i - 1
  • Dacă S[i - 1] este negativ, atunci S[i] = V[i] (subsecvența de sumă maximă care se termină pe i este formată doar din elementul V[i])

Complexitate

Algoritmul este liniar, având complexitate de timp O(N). Ca memorie, algoritmul are nevoie de O(1) memorie suplimentară, nefiind nevoie să reținem toate valorile din vectorul S, ci doar valoarea anterioară în sensul parcurgerii.

Subșir crescător maximal

Se dă un șir V de N elemente. Să se găsească un subșir ordonat strict crescător care are lungimea maximă.

Exemplu

Avem șirul: 24, 12, 15, 15, 19. Subșirul crescător maximal este format din elementele 12, 15, 19.

Soluție

Împărțim în subprobleme:

  • D[i] = lungimea celui mai lung subșir care se termină cu elementul de pe poziția i

Putem scoate răspunsul la problema originală combinând răspunsul acestor subprobleme? Da, răspunsul este chiar max(D[i]).

Cum calculăm D[i]? Vom presupune că am calculat deja toate lungimile până la D[i - 1]. Astfel, avem:

  • D[i] = max(D[j] + 1]), unde j < i și V[j] < V[i].

În alte cuvinte, încercăm să adăugăm elementul V[i] la toate șirurile din stânga, pentru care V[i] > V[j].

Complexitate

Complexitatea de timp a algoritmului este O(N2). Există și o implementare de complexitate O(N logN), pe care o vom discuta cu altă ocazie.

Complexitatea de spațiu adițional este O(N).

Subsecvență comună maximală

Se dau două șiruri de numere. Să se găsească o subsecvență de valori inclusă în ambele șiruri.

Exemplu

Primul șir: 1, 2, 1, 2, 3, 7. Cel de-al doilea șir: 3, 2, 1, 2, 1, 4, 3, 7.

Sunt două subsecvențe comune de lungime maximă: 1, 2, 1 și 2, 1, 2.

Soluție

Împărțim problema în subprobleme. Având în vedere că sunt două șiruri în cazul de față, avem nevoie de subprobleme mai "complexe":

  • D[i][j] = lungimea subsecvenței comune maximale care se termină pe poziția i în primul șir, respectiv pe poziția j în cel de-al doilea șir.

Ne putem aceleași întrebări ca și în problemele precedente.

Putem scoate răspunsul la problema originală combinând răspunsul acestor subprobleme? Da, răspunsul este chiar max(D[i][j]).

Cum calculăm D[i][j]? Vom presupune că avem calculate toate valorile precedente din parcurgere și avem două cazuri:

  • A[i] == B[j], atunci D[i][j] = D[i - 1][j - 1] + 1 (putem continua subsecvența maximală care se termină pe pozițiile de dinainte în ambele șiruri)
  • A[i] != B[j], atunci D[i][j] = 0 (nu avem o subsecvență care se termină pe aceste poziții, pentru că ele diferă)

Complexitate

Complexitatea de timp este O(N * M), unde N și M sunt lungimile celor două șiruri.

Complexitatea de spațiu poate fi redusă la O(min(N, M)). Din câte se observă, la fiecare pas al parcurgerii avem nevoie doar de linia / coloana precedentă din matrice, deci nu este nevoie să reținem toată matricea.

Subșir comun maximal (Cel mai lung subșir comun)

Se dau două șiruri de numere. Să se găsească un subșir de valori care apare în ambele șiruri.

Exemplu

Primul șir: 1, 7, 3, 9, 8. Cel de-al doilea șir: 7, 5, 8.

Subșirul comun de lungime maximă este format din elementele 7, 8.

Soluție

Împărțim problema în subprobleme. Similar ca la problema anterioară, cu o mică schimbare care să ne ajute să luăm în considerare subșiruri, nu subsecvențe:

  • D[i][j] = lungimea celui mai lung subșir inclus în șirurile A[1..i] și B[1..j]

Putem scoate răspunsul pentru problema originală? Da, este chiar D[N][M], unde N și M sunt lungimile șirurilor.

Cum calculăm D[i][j]? Vom presupune din nou că avem calculate toate valorile precedente:

  • A[i] == B[j], atunci D[i][j] = D[i - 1][j - 1] + 1 (putem continua subșirul de dinainte cu această valoare)
  • A[i] != B[j], atunci D[i][j] = max(D[i - 1][j], D[i][j - 1] (avem elemente diferite, deci luăm în considerare doar subșirurile de dinaintea lor)

Complexitate

Complexitatea de timp este O(N * M), unde N și M sunt lungimile celor două șiruri.

Complexitatea de memorie este tot O(N * M).

Reconstrucția soluției

Pentru a reconstrui soluția, pentru fiecare (i, j) vom reține atât lungimea subșirului si direcția din care a provenit. Direcția poate fi stânga (D[i][j - 1]), sus (D[i - 1][j]), sau diagonală (D[i - 1][j - 1]). Vom porni din poziția finală (N, M) și vom urmări aceste direcții, reținând fiecare literă pentru care direcția în care ne ducem este diagonală (asta înseamnă că această literă se găsește în subșir). Ne oprim evident, când ieșim din matrice.

Temă

infoarena - Subsecvență de sumă maximă
infoarena - Subșir crescător maximal
infoarena - Subșir comun maximal (Cel mai lung subșir comun)
varena - Subșir comun de lungime maximă