[C++, programare dinamică] Problema înmulțirii optime a matricelor

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

Se dau N matrice, considerate cu elemente numere reale, identificate printr-un vector de dimensiuni D. Astfel, matricea 1 ≤ i ≤ N are dimensiunea (D[i – 1], D[i]). Se cere găsirea numărului minim de înmulțiri scalare necesare pentru calcularea produsului celor N matrice.

Fișierul de intrare inmopt.in conține pe prima linie numărul N al matricelor, iar pe linia următoare N + 1 valori ce reprezintă vectorul de dimensiuni. Numărul minim de înmulțiri scalare se va afișa în fișierul inmopt.out.

Exemplu:

inmopt.ininmopt.out
3
4 3 2 5
64

Explicație: notăm cele trei matrice cu A, B și C. Numărul minim de înmulțiri scalare necesare se obține înmulțind matricele astfel: (A∙B)∙C. Daă am folosi parantezarea A∙(B∙C), am efectua 90 de înmulțiri.


Precizăm în primul rând că înmulțirea matricelor este asociativă, deci putem să parantezăm înmulțirea matricelor în orice mod valid fără a afecta rezultatul final.

În al doilea rând, numărul de înmulțiri scalare necesare pentru a înmulți două matrice de dimensiuni (x, y) și (y, z) este egal cu x∙y∙z.


Vom încerca să exprimăm recursiv problema. Notăm matricele date cu A1, A2, …, AN. Să presupunem că știm un k între 1 și N astfel încât parantezarea (A1∙A2∙…∙Ak)∙(Ak+1∙…∙AN) să fie o parte a soluției optime. Atunci, pentru a obține soluția optimă, trebuie să știm cum putem paranteza optim înmulțirile A1∙A2∙…∙Ak și Ak+1∙…∙AN.

Pentru a putea exprima matematic acest lucru, fie M[i][j] = numărul minim de înmulțiri scalare necesare înmulțirii secvenței de matrice [i, j]. Dacă știm calcula matricea M, atunci răspunsul problemei va fi M[1][N].


Se disting următoarele cazuri:

  1. Dacă avem o singură matrice, atunci nu trebuie efectuată nicio înmulțire scalară. Acesta este cazul de bază al recurenței, deci M[i][i] = 0 pentru orice 1 ≤ i ≤ N.
  2. Pentru aflarea numărului minim de înmulțiri scalare necesare pentru înmulțirea unei secvențe de matrice [i, j], 1 ≤ i < j N este necesar să știm poziția i ≤ k < j în care vom „împărți” secvența [i, j] în două secvențe parantezate separat [i, k] și [k + 1, j]. Dimensiunea matricei rezultate din înmulțirea matricelor din secvența [i, k] va fi dat de (D[i – 1], D[k]), iar dimensiunea celei rezultate din înmulțirea matricelor din secvența [k + 1, j] va fi dată de (D[k], D[j]). Avem așadar:

(n.e. Se adună la nr. de înmulțiri scalare optim pentru Ai * Ak, numărul de înmulțiri scalare optim pentru Ak+1 * Aj, și apoi se adaugă produsul celor 3 elemente ale D.)


Timpul de execuție al algoritmului este O(N3), deoarece pentru fiecare dintre cele O(N2) secvențe efectuăm o parcurgere în timp O(N) pentru a găsi k care verifică minimul de mai sus. Memoria folosită este O(N2), deoarece folositm o matrice pătratică de dimensiune N.

#include <fstream>

using namespace std;

const int maxn = 101;
const int inf = 1 << 30;

void citire(int D[], int &N)
{
       ifstream in("inmopt.in");

       in >> N;
       for (int i = 0; i <= N; ++i)
       {
              in >> D[i];
       }

       in.close();
}

int rezolvare(int D[], int N)
{
       int M[maxn][maxn];

       for (int i = 1; i <= N; ++i)
       {
              M[i][i] = 0;
       }

       for (int i = N - 1; i; --i)
       {
              for (int j = i + 1; j <= N; ++j)
              {
                     M[i][j] = inf;

                     for (int k = i; k < j; ++k)
                     {
                           int t = M[i][k] + M[k + 1][j] +
                                  D[i - 1] * D[k] * D[j];
                           M[i][j] = min(M[i][j], t);
                     }
              }
       }

       return M[1][N];
}

int main()
{
       int N, D[maxn];

       citire(D, N);

       ofstream out("inmopt.out");
       out << rezolvare(D, N);
       out.close();

       return 0;
}

Exerciții:

a) De ce i trebuie să pornească de la N – 1 și nu de la 1? Ce se întâmplă dacă i merge de la 1 la N?

b) Concepeți o modalitate de a reconstitui soluția. Pentru exemplul dat, o reconstituire a soluției ar putea fi (A1*A2)*A3.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Fotografie Google

Comentezi folosind contul tău Google. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

%d blogeri au apreciat: