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(n \log n)$ pentru problema parantezării optime de matrice, în acest articol voi prezenta doar soluția în $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 = 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 $a$ construit astfel încât matricea $M_i$ are $a_{i-1}$ linii și $a_i$ coloane. Să se determine costul (numărul de înmulțiri scalare) minim pentru calcularea produsului matriceal dat.

Motivație

Două matrice $A$ și $B$ pot fi înmulțite doar dacă numărul de coloane ale lui $A$ este egal cu numărul de linii ale lui $B$ 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 $A_{m \times n}$ și $B_{n \times p}$ este o matrice $C_{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 $mnp$ Când avem de înmulțit două matrice, nu avem decât o modalitate, dar când avem trei matrice $A_{m \times n}$ $B_{n \times p}$ și $C_{p \times q}$ putem calcula produsul lor în două moduri:

• $(AB)C$ Calculăm produsul $AB$ cu costul $mnp$ obținând o matrice $M_{m \times p}$ Apoi calculăm produsul $MC$ cu costul $mpq$ Costul total va fi $mnp + mpq$
• $A(BC)$ Calculăm produsul $BC$ cu costul $npq$ obținând o matrice $M_{n \times q}$ Apoi calculăm produsul $AM$ cu costul $mnq$ Costul total va fi $npq + 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)$ Costurile vor fi $18000$ și respectiv $32000$ 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(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 $\mathrm{dp}[i][j]$ costul minim pentru calcularea produsului $M_i M_{i+1} \cdots M_j$ unde $1 \le i \le j \le n$ Este evident că acest produs va returna o matrice de dimensiuni $a_{i-1} \times a_{j}$

Găsirea relației de recurență

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

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

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

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 $a_{i-1} \times a_{k}$ iar a doua $a_{k} \times a_{j}$

Cum aflăm $k$ul 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:

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]$ cu tăietura în $k$ implică la rândul lui costuri minime pentru subsecvențele $[i, k]$ și $[k+1, j]$
• suprapunerea subproblemelor: Fie două secvențe $[a, b]$ și $[c, d]$ cu $c \le b$ Intersecția lor este $[c, b]$ Ei bine, pentru a calcula atât $\mathrm{dp}[a][b]$ cât și $\mathrm{dp}[c][d]$ avem nevoie de $\mathrm{dp}[c][b]$

Ordinea în care se calculează stările

Mereu când calculăm o stare $\mathrm{dp}[i][j]$ folosim valorile unor stări de lungime mai mică decât cea curentă, care este $j - 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 $\mathrm{dp}$ diagonală cu diagonală, pornind de la cea principală, până la cea formată doar din $\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 $n-i+1$ secvențe de lungime $i$ Pentru fiecare dintre acestea există $i-1$ tăieturi posibile. În total, algoritmul efectuează următorul număr de pași (intrări în al doilea for):

Așadar, complexitatea în timp a algoritmului nostru este $O(n^3)$ cu o constantă de $1/6$ ceea ce-l face fezabil pentru $n \le 500$ Având în vedere numărul de stări ale dinamicii, complexitatea în spațiu este de ordinul $O(n^2)$ cu o constantă de $1/2$ (Completăm doar jumătate din matricea $\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 $10^{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 $\mathrm{cut}$ ca în $\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]$ 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]$ închidem paranteza, deschidem o nouă paranteză, afișăm parantezarea pentru $[k+1, j]$ și închidem paranteza. Dacă am ajuns la o secvență de lungime $1$ 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:

• Redu
• Minerale
• Stiva
• Nunta

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