Parantezare optimă de matrice [Programare dinamică]

Parantezare optimă de matrice [Programare dinamică]

Parantezarea optimă de matrice (Matrix chain multiplication) este o problemă fundamentală în studiul programării dinamice, deoarece poate fi generalizată pentru a rezolva următoarea problemă: Dându-se o secvență de obiecte și o operație binară asociativă definită pe mulțimea acestor obiecte, să se determine costul minim pentru a reduce secvența dată la un singur obiect, aplicând în mod repetat operația respectivă. Cu toate că se cunosc deja soluții în O(nlogn)O(n \log n) pentru problema parantezării optime de matrice, în acest articol voi prezenta doar soluția în O(n3)O(n^3) care de obicei este suficient de bună în concursuri.

Enunț

În continuare, ne vom raporta la problema podm din Arhiva educațională InfoArena. Se dă un produs de matrice M=M1M2MnM = M_1 M_2 \cdots M_n pe care dorim să-l calculăm cât mai rapid. Cum înmulțirea matricelor este asociativă, toate parantezările secvenței date conduc la același rezultat. Însă, numărul de înmulțiri scalare ce trebuie efectuate poate diferi considerabil în funcție de ordinea efectuării calculelor, ordine dată de parantezarea aleasă. Dimensiunile matricelor se dau printr-un vector aa construit astfel încât matricea MiM_i are ai1a_{i-1} linii și aia_i coloane. Să se determine costul (numărul de înmulțiri scalare) minim pentru calcularea produsului matriceal dat.

Motivație

Două matrice AA și BB pot fi înmulțite doar dacă numărul de coloane ale lui AA este egal cu numărul de linii ale lui BB De accea dimensiunile matricelor sunt date în forma de mai sus, și nu se specifică pe rând ambele dimensiuni ale fiecărei matrice. Rezultatul înmulțirii a două matrice Am×nA_{m \times n} și Bn×pB_{n \times p} este o matrice Cm×pC_{m \times p} calculată astfel:

for (int i = 1; i <= m; i++)
for (int j = 1; j <= p; j++)
for (int k = 1; k <= n; k++)
C[i][j] += A[i][k] * B[k][j];

Se vede clar că numărul de înmulțiri scalare efectuate este egal cu mnpmnp Când avem de înmulțit două matrice, nu avem decât o modalitate, dar când avem trei matrice Am×nA_{m \times n} Bn×pB_{n \times p} și Cp×qC_{p \times q} putem calcula produsul lor în două moduri:

  • (AB)C(AB)C Calculăm produsul ABAB cu costul mnpmnp obținând o matrice Mm×pM_{m \times p} Apoi calculăm produsul MCMC cu costul mpqmpq Costul total va fi mnp+mpqmnp + mpq
  • A(BC)A(BC) Calculăm produsul BCBC cu costul npqnpq obținând o matrice Mn×qM_{n \times q} Apoi calculăm produsul AMAM cu costul mnqmnq Costul total va fi npq+mnqnpq + mnq

Dacă încă nu vi se pare evident că rezultatele pot diferi substanțial, luați ca exemplu (m,n,p,q)=(10,20,30,40)(m, n, p, q) = (10, 20, 30, 40) Costurile vor fi 1800018000 și respectiv 3200032000 Diferența este destul de mare, cred eu!

Soluție prin programare dinamică

Soluția naivă constă în generarea recursivă a tuturor parantezărilor posibile, dar cum numărul acestora crește exponențial, nici nu are rost să o luăm în calcul. În continuare voi prezenta o soluție mult mai bună, în complexitate O(n3)O(n^3) ce folosește programare dinamică.

Formularea subproblemelor

Intuim că va trebui să analizăm pe rând fiecare subsecvență a șirului de matrice dat. Notăm prin dp[i][j]\mathrm{dp}[i][j] costul minim pentru calcularea produsului MiMi+1MjM_i M_{i+1} \cdots M_j unde 1ijn1 \le i \le j \le n Este evident că acest produs va returna o matrice de dimensiuni ai1×aja_{i-1} \times a_{j}

Găsirea relației de recurență

Cazul de bază în calcularea stărilor dinamicii este i=ji = j Evident, nu ne costă nimic să formăm o singură matrice dintr-o subsecvență care deja are lungimea 11 deci dp[i][i]=0\mathrm{dp}[i][i] = 0 unde 1in1 \le i \le n

Pentru secvențe de forma [i,j][i, j] cu i<ji < j trebuie să ne folosim cumva de costurile minime corespunzătoare unor subsecvențe incluse în [i,j][i, j] Ideea este să împărțim secvența [i,j][i, j] în două subsecvențe [i,k][i, k] și [k+1,j][k + 1, j] unde ik<ji \le k \lt j Altfel spus, facem o „tăietură” în kk ceea ce înseamnă că vom încadra fiecare dintre cele două subsecvențe între paranteze:

MiMi+1Mj=(MiMi+1Mk)(Mk+1Mk+2Mj)M_i M_{i+1} \cdots M_j = (M_i M_{i+1} \cdots M_k)(M_{k+1} M_{k+2} \cdots M_j)

Făcând o tăietură într-un kk fixat, costul minim pentru secvența [i,j][i, j] este:

dp[i][k]+dp[k+1][j]+ai1akaj\mathrm{dp}[i][k] + \mathrm{dp}[k+1][j] + a_{i-1} a_{k} a_{j}

Primii doi termeni sunt costurile minime corespunzătoare celor două subsecvențe, iar al treilea este costul pentru înmulțirea celor două matrice formate. Prima va avea dimensiunile ai1×aka_{i-1} \times a_{k} iar a doua ak×aja_{k} \times a_{j}

Cum aflăm kkul optim, adică cel pentru care costul calculat mai sus este minim? Pur și simplu iterăm printre toate valorile pe care le poate lua și selectăm minimul costurilor calculate. Așadar, recurența dinamicii este:

dp[i][j]={minik<j{dp[i][k]+dp[k+1][j]+ai1akaj}pentru 1i<jn0pentru 1i=jn\mathrm{dp}[i][j] = \begin{cases} \min_{i \le k \lt j} \left\{ \mathrm{dp}[i][k] + \mathrm{dp}[k+1][j] + a_{i-1} a_{k} a_{j} \right\} & \text{pentru } 1 \le i \lt j \le n\\ 0 & \text{pentru } 1 \le i = j \le n \end{cases}

Problema parantezării optime de matrice este un bun exemplu pentru a ilustra cele două principii ale programării dinamice:

  • substructura optimală: Costul minim al unei secvențe [i,j][i, j] cu tăietura în kk implică la rândul lui costuri minime pentru subsecvențele [i,k][i, k] și [k+1,j][k+1, j]
  • suprapunerea subproblemelor: Fie două secvențe [a,b][a, b] și [c,d][c, d] cu cbc \le b Intersecția lor este [c,b][c, b] Ei bine, pentru a calcula atât dp[a][b]\mathrm{dp}[a][b] cât și dp[c][d]\mathrm{dp}[c][d] avem nevoie de dp[c][b]\mathrm{dp}[c][b]

Ordinea în care se calculează stările

Mereu când calculăm o stare dp[i][j]\mathrm{dp}[i][j] folosim valorile unor stări de lungime mai mică decât cea curentă, care este ji+1j - i + 1 Deci, cea mai simplă idee este să calculăm stările crescător după lungimea secvențelor corespunzătoare lor. Dacă ne uităm mai atent, asta înseamnă să completăm matricea dp\mathrm{dp} diagonală cu diagonală, pornind de la cea principală, până la cea formată doar din dp[1][n]\mathrm{dp}[1][n] unde se află și răspunsul problemei noastre. Putem face această parcurgere elegant astfel:

for (int len = 2; len <= n; len++)
for (int i = 1, j = len; j <= n; i++, j++)
compute(i, j);

Un alt mod corect de parcurgere a stărilor, poate chiar mai elegant, este cel de mai jos. Totuși, îl prefer pe primul, pentru claritate.

for (int i = n - 1; i >= 1; i--)
for (int j = i + 1; j <= n; j++)
compute(i, j);

Complexitate

Avem ni+1n-i+1 secvențe de lungime ii Pentru fiecare dintre acestea există i1i-1 tăieturi posibile. În total, algoritmul efectuează următorul număr de pași (intrări în al doilea for):

T=i=1n1i(ni)=n(1+2++(n1))(12+22++(n1)2)=n(n1)n2(n1)n(2n1)6=n3n6=O(n3)\begin{align*} T &= \sum_{i=1}^{n-1} i(n - i)\\ &= n \cdot (1 + 2 + \cdots + (n-1)) - (1^2 + 2^2 + \cdots + (n-1)^2)\\ &= n \cdot \frac{(n-1)n}{2} - \frac{(n-1)n(2n-1)}{6}\\ &= \frac{n^3-n}{6} = O(n^3) \end{align*}

Așadar, complexitatea în timp a algoritmului nostru este O(n3)O(n^3) cu o constantă de 1/61/6 ceea ce-l face fezabil pentru n500n \le 500 Având în vedere numărul de stări ale dinamicii, complexitatea în spațiu este de ordinul O(n2)O(n^2) cu o constantă de 1/21/2 (Completăm doar jumătate din matricea dp\mathrm{dp}

Sursă C++

Iată mai jos o sursă ce obține 100 de puncte la problema Parantezare optimă de matrice de pe InfoArena. În caz că nu știați, int64_t se referă de fapt la tipul long long int, iar 1e18 este egal cu 101810^{18} și l-am folosit pentru a reprezenta infinitul.

#include <bits/stdc++.h>
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
int main() {
int n; fin >> n;
vector<int64_t> a(n + 1);
for (int i = 0; i <= n; i++)
fin >> a[i];
vector dp(n + 1, vector<int64_t>(n + 1));
for (int len = 2; len <= n; len++)
for (int i = 1, j = len; j <= n; i++, j++) {
dp[i][j] = 1e18;
for (int k = i; k < j; k++)
dp[i][j] = min(
dp[i][j],
dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j]
);
}
fout << dp[1][n] << '\n';
return 0;
}

Reconstituirea soluției

Pe InfoArena nu se cere și afișarea unei parantezări optime, însă voi prezenta și cum se poate reconstitui o astfel de soluție. Trebuie doar să mai luăm o matrice cut\mathrm{cut} ca în cut[i][j]\mathrm{cut}[i][j] să reținem poziția unde a fost făcută o tăietură ce a condus la costul minim pentru secvența [i,j][i, j] Având această matrice la îndemână, putem afișa recursiv o parantezare optimă foarte simplu:

Deschidem o paranteză rotundă, afișăm parantezarea pentru [i,k][i, k] închidem paranteza, deschidem o nouă paranteză, afișăm parantezarea pentru [k+1,j][k+1, j] și închidem paranteza. Dacă am ajuns la o secvență de lungime 11 pur și simplu afișăm litera corespunzătoare matricei. Iată deci o sursă ce afișează atât costul minim, cât și o parantezare optimă:

#include <bits/stdc++.h>
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
void print(int i, int j, vector<vector<int>>& cut) {
if (i == j) {
fout << char('A' + i - 1);
return;
}
// Încadrăm subsecvențele între paranteze
// doar dacă au lungimea mai mare decât 1:
int k = cut[i][j];
if (k - i > 0) fout << '(';
print(i, k, cut);
if (k - i > 0) fout << ')';
if (j - k > 1) fout << '(';
print(k + 1, j, cut);
if (j - k > 1) fout << ')';
}
int main() {
int n; fin >> n;
vector<int64_t> a(n + 1);
for (int i = 0; i <= n; i++)
fin >> a[i];
vector cut(n + 1, vector<int>(n + 1));
vector dp(n + 1, vector<int64_t>(n + 1));
for (int len = 2; len <= n; len++)
for (int i = 1, j = len; j <= n; i++, j++) {
dp[i][j] = 1e18;
for (int k = i; k < j; k++) {
int64_t cost = dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j];
if (cost < dp[i][j]) {
dp[i][j] = cost;
cut[i][j] = k;
}
}
}
fout << "Costul minim: " << dp[1][n] << '\n';
fout << "O parantezare optima: "; print(1, n, cut); fout << '\n';
return 0;
}

Probleme recomandate

După cum am zis și în introducere, parantezarea optimă de matrice poate fi adaptată pentru a rezolva o gamă largă de probleme. Iată câteva dintre acestea:

Dacă aveți vreo întrebare despre problema parantezării optime de matrice, nu ezitați să o lăsați într-un comentariu mai jos :smile:

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii