Clasa VII/VIII lecția 11 - 17 dec 2013

Tema - rezolvări

Rezolvări aici [1].

Lecție

În această lecție vom introduce noțiunea de programare dinamică.

Programare dinamică

Introducere

Wikipedia definește programarea dinamică drept "... o metodă pentru rezolvarea unor probleme complexe prin descompunerea lor în subprobleme mai simple. Se poate aplica problemelor care prezintă proprietățile de suprapunere a subproblemelor și de substructură optimală. Atunci cînd se poate aplica, metoda ia mult mai puțin timp decît alte soluții naive.

Drumul cel mai scurt între două orașe poate fi rezolvat cu programare dinamică

Substructura optimală înseamnă că soluția unei problemei de optimizare date poate fi obținută prin combinarea unor soluții optimale ale subproblemelor. Ca atare, primul pas către găsirea unei rezolvări prin această metodă este verificarea dacă problema are proprietatea substructurii optimale. Astfel de substructuri optimale sînt în mod usual descrise prin recurență. De exemplu, date niște orașe și distanțele între ele, drumul cel mai scurt de la orașul u la orașul v are proprietatea de substructură optimală: să luăm orice oraș intermediar w pe drumul cel mai scurt, d. Dacă d este cu adevărat drumul cel mai scurt, atunci drumul d1 de la u la w și d2 de la w la v sînt cu adevărat cele mai scurte drumuri între orașele corespunzătoare. Dacă drumul de la u la w nu ar fi cel mai scurt posibil ar însemna că am avea un alt drum mai scurt, ceea ce ar duce la un drum total d, de la u la v, mai scurt decît cel original. Așadar, putem formula soluția problemei găsirii celui mai scurt drum într-o manieră recursivă, ceea ce fac algoritmii Bellman-Ford și Floyd-Warshall.

Suprapunerea subproblemelor înseamnă că ele nu sînt independente, adică subproblemele au în comun alte subprobleme. Nu vom insista pe această proprietate decît atît cît să menționăm că dacă subproblemele nu se suprapun dar prezintă substructură optimală atunci putem aplica tehnica de programare divide et impera (divide and conquer). De aceea quicksort și mergesort nu sînt clasificate ca probleme de programare dinamică.

Metodă

Cînd încercăm să rezolvăm o problemă de programare dinamică întrebarea crucială la care trebuie să răspundem este putem calcula soluția finală pe baza unor subprobleme care sînt la rîndul lor optimale? Pentru a răspunde la întrebare trebuie mai întîi să formulăm subproblemele. Dar pentru a formula subproblemele trebuie să avem în minte principiul substructurii optimale. Altfel s-ar putea să împărțim problema în subprobleme care nu au substructură optimală.

Să recapitulăm: pentru a putea răspunde la întrebarea dacă o problemă admite o soluție prin programare dinamică trebuie să aflăm dacă are substructură optimală. Dar pentru a afla dacă are substructură optimală trebuie să găsim subproblemele. Pe care încercăm să le găsim folosind programarea dinamică.

Nu cumva ne învîrtim în cerc? Așa pare și așa și este, într-o oarecare măsură. Experiența este cea care ne învață cum să căutăm împarțirea în subprobleme astfel încît să obținem proprietatea de optimalitate. Tot experiența este cea care ne ajută să ne dăm seama rapid dacă împărțirea găsită are această proprietate sau nu.

Odată ce demonstrăm că o împărțire în subprobleme se bazează doar pe subprobleme optimale, restul decurge, de obicei, destul de simplu: găsim o formulă de recurență, apoi o implementăm de jos în sus (sau bottom-up), pornind de la cele mai mici probleme, către cele mai mari, pînă la soluția cerută.

Să luăm cîteva exemple.

Subsecvența crescătoare de lungime maximă

Această problemă cere să găsim o subsecvență a unei secvențe de numere în care elementele sînt în ordine crescătoare, iar subsecvența este de lungime maximă. Subsecvența nu este neapărat contiguă, nici unică.

Exemplu

În secvența

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, …

o secvență crescătoare de lungime maximă este

0, 2, 6, 9, 13, 15.

Această secvență are lungime șase. Nu există nici o secvență crescătoare de lungime șapte. Cea mai lungă subsecvență crescătoare nu este unică. De exemplu

0, 4, 6, 9, 11, 15

este o altă subsecvență crescătoare de aceeași lungime, în secvența de intrare.

Soluție

Cum împărțim problema în subprobleme? Să încercăm astfel:

L[i] = lungimea celei mai lungi subsecvențe care începe la poziția i

Are această împărțire proprietatea de optimalitate? Să presupunem că avem o subsecvență optimală crescătoare care trece prin indicii

i₁, i₂, …, i_k, …, i_m

Este secvența i₁, i₂, …, i_k optimală? Dar secvența i_k, …, i_m? Amîndouă sînt optimale deoarece altfel le-am putea înlocui cu secvențe mai lungi, ceea ce ar duce la o subsecvență mai lungă decît cea inițială, care era optimală.

Următorul pas este să găsim relația de recurență:

L[i] = max(L[j]+1), j > i și V[j] ≥ V[i]

Următorul pas este să construim subproblemele bottom-up, de la problemele mai mici la cele mai mari. Pentru aceasta vom calcula vectorul L de la coadă la cap, căutînd pentru fiecare element L[i] cel mai mare element L[j] de după el (j > i) astfel încît V[j] ≥ V[i].

Soluția problemei este maximul din vectorul L. Acest algoritm are complexitate O(n²), unde n este lungimea secvenței. Memoria folosită este O(n). Putem reconstrui o subsecvență maximală folosind încă un vector de indice următor în secvență. Există și un algoritm mai rapid, de complexitate O(n log n).

Subșirul de sumă maximală

Această problemă cere să găsim un subșir de sumă maximă într-un șir de numere. Un subșir este contiguu. Un subșir vid are sumă zero.

Exemplu

Să considerăm șirul:

12, 14, 0, -4, 61, -39

subșirul de sumă maximală este:

12, 14, 0, -4, 61

și are sumă 83.

Soluție

Cum împărțim problema în subprobleme? Să încercăm astfel:

S[i] este suma maximală a unui șir care se termină la poziția i

Are această împărțire proprietatea de optimalitate? Să presupunem că avem un subșir optimal între indicii i și j. Să considerăm și un indice k între i și j. Are șirul care se termină în k sumă maximală? Dar șirul care începe cu k? Amîndouă sînt optimale deoarece altfel le-am putea înlocui cu șiruri de sumă mai mare, ceea ce ar duce la o sumă mai mare decît cea inițială, care era optimală.

Următorul pas este să găsim relația de recurență. Observăm că pentru poziția i avem două variante: fie continuăm secvența anterioară, fie începem una nouă. Vom continua secvența anterioară dacă adunînd numărul curent obținem o sumă strict pozitivă. Altfel vom porni o sumă nouă. Relația de recurență este:

S[i] = max(0, S[i-1]+V[i])

Următorul pas este să construim subproblemele bottom-up, de la problemele mai mici la cele mai mari. Pentru aceasta vom calcula vectorul S calculînd pentru fiecare element S[i] maximul dintre S[i-1]+V[i] și 0.

Soluția problemei este maximul din vectorul S. Acest algoritm are complexitate O(n), unde n este lungimea șirului. Memoria folosită este O(1). Putem ține minte șirul maximal ținînd minte începutul și sfîrșitul subșirului maximal atunci cînd îl găsim.

Subșirul comun maximal al două șiruri

Această problemă cere să găsim lungimea unui subșir de lungime maximă inclus în două șiruri..

Exemplu

Date șirurile

ABABC

și

CBABA

un subșir maximal are lungime 3 și este

BAB

Soluție

Cum împărțim problema în subprobleme? Să observăm că deoarece subșirul maximal face parte din ambele șiruri el se va termina la o poziție i în șirul X și la o poziție j în șirul Y. Și atunci să încercăm astfel:

M[i][j] = lungimea celui mai lung subșir care se termină la poziția i în X și la poziția j în Y.

Are această împărțire proprietatea de optimalitate? Să presupunem că avem o un subșir optimal care se termină la pozițiile i, respectiv j. Atunci este subșirul M[i-1][j-1] la rîndul lui optimal? Cu alte cuvinte subșirul mai scurt cu unu, care se termină la pozițiile anterioare în X, respectiv Y, este optimal? Da, el este optimal, caci altfel l-am putea înlocui cu un șir mai lung, care ar duce la o soluție mai bună, ceea ce ar însemna că soluția originală nu a fost optimă.

Următorul pas este să găsim relația de recurență:

$M[i][j]={\begin{cases}M[i-1][j-1]+1,&{\mbox{dacă }}X[i]=Y[j]\\0,&{\mbox{în caz contrar }}.\end{cases}}$

Următorul pas este să construim subproblemele bottom-up, de la problemele mai mici la cele mai mari. Pentru aceasta vom calcula matricea M pe linii, folosind formula de recurență.

Soluția problemei este maximul din matrice. Acest algoritm are complexitate O(m · n), unde m și n sînt lungimile șirurilor. Memoria folosită este O(min(m,n)) dacă memorăm doar o linie din matrice. Există și algoritmi mai eficienți bazați pe arbori sufix, despre care nu vom discuta aici.

Subsecvența comună maximală a două siruri

Această problemă cere să găsim lungimea unei subsecvențe de lungime maximă inclusă în două secvențe. Prin secvență înțelegem caractere în ordinea originală, nu neapărat consecutive ca poziție.

Exemplu

Date secvențele

X: ABCDEFG (n elemente)

Y: BCDGK (m elemente)

o secvență maximală are lungime 4 și este

BCDG

Soluție

Cum împărțim problema în subprobleme? Să încercăm să o împărțim în mod similar cu subșirul comun maximal:

M[i][j] = lungimea celei mai lungi subsecvențe incluse în prefixele care se termină la poziția i în X, respectiv la poziția j în Y.

Are această împărțire proprietatea de optimalitate?

Să presupunem că avem o soluție a problemei. Ea va trece prin caracterul i în X și prin caracterul j în Y. Rezultă de aici că prefixul pînă la i al soluției este o subsecvență optimală pentru X[1..i] și Y[1..j]? Să presupunem că nu ar fi optimală. Atunci ar exista o subsecvență comună mai lungă, pe care am putea-o folosi pentru a construi o soluție globală mai bună, deci soluția originală nu era optimă.

Următorul pas este să găsim relația de recurență:

$M[i][j]={\begin{cases}0,&{\mbox{dacă }}i=0sauj=0\\M[i-1][j-1]+1,&{\mbox{dacă }}X[i]=Y[j]\\max(M[i-1][j],M[i][j-1]),{\mbox{dacă }}X[i]&\neq Y[j].\end{cases}}$

Cum demonstrăm această relație de recurență? Avem două cazuri de demonstrat:

Egalitate

Prefixele X[1..i] și Y[1..j] se termină în același caracter. În acest caz orice subsecvență maximală a celor două prefixe va include ultimul caracter. Putem, deci exclude acel caracter și calcula subsecvența maximală în prefixele X[1..i-1] și Y[1..j-1]. La lungimea ei vom aduna unu.

Diferență

Prefixele X[1..i] și Y[1..j] se termină în caractere diferite. Să luăm cazul anterior, avem secvențele:

X: ABCDEFG (n elemente)

Y: BCDGK (m elemente)

Avem iarăși două cazuri:

• Cazul 1: subsecvența optimă se termină în G. În acest caz ea nu se poate termina și în K. Deci putem elimina ultimul caracter din Y și calcula M[i][j-1].
• Cazul 2: subsecvența optimă nu se termină în G. În acest caz putem elimina acest G și calcula M[i-1][j].

Următorul pas este să construim subproblemele bottom-up, de la problemele mai mici la cele mai mari. Pentru aceasta vom calcula matricea M pe linii, folosind formula de recurență.

Soluția problemei este M[n][m]. Acest algoritm are complexitate O(m · n), unde m și n sînt lungimile șirurilor. Memoria folosită este O(min(m,n)) dacă memorăm doar o linie din matrice. Dacă dorim să aflăm și o secvență, nu doar lungimea ei, vom avea nevoie de memorie O(m · n). Există un algoritm care reduce necesarul de memorie la O(min(m,n))

Temă

Următoarele probleme vor fi portate pe vianuarena. Reveniți la această pagină pentru update-uri. Între timp am încercat să găsesc probleme echivalente pe infoarena.

• Problema dreptunghiuri pentru subsecvența crescătoare maximală
• Neportată pe varena: subșirul de sumă maximă
• Neportată pe varena: cel mai lung subșir comun
• Neportată pe varena: subsecvența comună maximală
• Neportată pe varena: distanța edit
• Problema pdm pentru înmulțirea optimală a unui șir de matrice
• Neportată pe varena: problema rucsacului 0-1

Temă vacanţă

Nu vă dau teme specifice. În ordinea greutății problemelor, lucraţi:

• probleme date la ONI şi OJI în anii trecuţi
• probleme date la ONI și OJI în anii trecuți la clasă mai mare
• probleme date la barajul de gimnaziu