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.in
|
inmopt.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:
- 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.
- 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:
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.
