Fişierul intrare/ieşire:podm.in, podm.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Parantezare optima de matrici

Se dă un produs matricial M = M1M2...Mn. Cum înmulţirea matricelor este asociativă, toate parantezările conduc la acelaşi rezultat. Însă, numărul total de înmulţiri scalare al produsului matricial poate să difere substanţial în funcţie de ordinea efectuării calculelor, ordine dată de paranteze. Dimensiunile celor n matrici se dau sub forma unui şir d astfel încât perechea (di-1, di) reprezintă dimensiunile matricii Mi.

Cerinţă

Se cere să se minimizeze numărul total de înmulţiri scalare al produsului matricial M, valoare ce corespunde unei parantezări optime.

Date de intrare

Fişierul de intrare podm.in conţine pe prima linie un număr natural n, reprezentând numărul matricelor. Pe următoarea linie se găsesc n + 1 numere naturale, reprezentând valorile şirului d.

Date de ieşire

În fişierul de ieşire podm.out se va găsi un singur număr natural egal cu valoarea minimă a numărului total de înmulţiri scalare a produsului matricial M.

Restricţii

  • 1 ≤ n ≤ 500
  • 1 ≤ di ≤ 10 000, unde 0 ≤ i ≤ n

Exemplu

podm.inpodm.out
4
13 5 89 3 34
2856

Explicaţie

În exemplu se dau 4 matrici: A de dimensiuni (13, 5), B de (5, 89), C de (89, 3), D de (3, 34). În funcţie de ordinea efectuării înmulţirilor matriciale , numărul total de înmulţiri scalare poate să fie foarte diferit:

  • (((AB)C)D) : 10582 înmulţiri
  • ((AB)(CD)) : 54201 înmulţiri
  • ((A(BC))D) : 2856 înmulţiri
  • (A((BC)D)) : 4055 înmulţiri
  • ...

Rezultatul optim se obţine pentru cea de a treia parantezare: ((A(BC))D).

Indicaţii de rezolvare

Pentru cei care nu sunt familiarizaţi cu înmulţirea matricilor, recomand acest articol de pe wikipedia.

Înmulţirea matricilor este asociativă, motiv pentru care putem efectua aceste înmulţiri în mai multe moduri.

Înainte de a continua, să observăm că înmulţirea unei matrici cu p x q elemente cu o matrice de q x r elemente necesită pqr înmulţiri scalare.

O soluţie directă de a determina ordinea optimă de efectuare a înmulţirilor matriciale este de a paranteza expresia în toate modurile posibile şi de a calcula de fiecare dată care este numărul de înmulţiri scalare necesare. Însă, numărul de moduri de a scrie un şir cu n paranteze deschise şi n paranteze închise, astfel încât să fie închise corect, este egal cu  C(n) = \dfrac{1}{n+1} * \dbinom{2n}{n} . Şirul (C(n)) se numeşte şirul numerelor lui Catalan. Aşadar, rezolvarea are o complexitate exponenţială.

Din fericire, principiul optimalităţii al metodei programării dinamice se poate aplica la această problemă. Dacă cel mai bun mod de a înmulţi toate matricele presupune o tăietură între a i-a şi a i + 1 a matrice a produsului, atunci subprodusele M1M2...Mi şi Mi+1Mi+2...Mn trebuie calculate la rândul lor într-un mod optim.

Vom construi tabloul m[1..n, 1..n], unde m[i, j] este numărul minim de înmulţiri scalare necesare pentru a calcula partea MiMi+1...Mj a produsului iniţial. Soluţia problemei iniţiale va fi m[1, n]. Presupunem că tabloul d[0..n] conţine dimensiunile matricilor, astfel încât matricea Mi este de dimensiuni (d[i-1], d[i]), 1 ≤ i ≤ n. Construcţia tabloului se face diagonală cu diagonală:

  •  d = 0: m[i, i] = 0, 1 \le i \le n
  •  d = 1: m[i, i + 1] = d[i - 1] * d[i] * d[i + 1], 1 \le i \le n - 1
  •  1 < d < n: m[i, i + d] = Min\{m[i, k] + m[k + 1, i + d] + d[i - 1] * d[k] * d[i + d] : i \le k < i + d\}, 1 \le i \le n - d

Timpul de execuţie este de ordinul O(N3), iar sursa demonstrativă se găseşte aici.

Pentru a studia în detaliu problema înmulţirii înlănţuite de matrici puteţi consulta capitolul 16 din Introducere în algoritmi de Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.

Aplicaţii

Parantezarea optimă de matrici este o aplicaţie clasică ce ilustrează cele două caracteristici care permit o rezolvare folosind metoda programării dinamice: substructură optimală, suprapunerea subproblemelor. Pentru a vă însuşi această tehnică vă recomand să rezolvaţi următoarele probleme:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content