podm

Parantezare optimă de matrici

== include(page="template/taskheader" task_id="podm") ==

Poveste şi cerinţă...

Se dă un produs matricial $M = M{~1~}M{~2~}...M{~n~}$. 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 $(d{~i-1~}, d{~i~})$ reprezintă dimensiunile matricii $M{~i~}$.
 
h2. Cerinţă
 
Se cere să se minimizeze numărul total de înmulţiri scalare al produsului matricial $M$, valoare ce corespunde unei parantezări optime.

h2. Date de intrare

Fişierul de intrare $podm.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $podm.out$ ...

Î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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 500$
* $1 ≤ d{~i~} ≤ 10 000$, unde $0 ≤ i ≤ n$

h2. Exemplu
table(example). |_. podm.in |_. podm.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
13 5 89 3 34
| 2856

|
h3. 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)$.
 
h2. Indicaţii de rezolvare
 
Pentru cei care nu sunt familiarizaţi cu înmulţirea matricilor, recomand acest articol de pe 'wikipedia':http://en.wikipedia.org/wiki/Matrix_multiplication.
 
Î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 <tex> C(n) = \dfrac{1}{n+1} * \dbinom{2n}{n} </tex>. Şirul $(C(n))$ se numeşte 'şirul numerelor lui Catalan':http://www.ginfo.ro/revista/15_5/mate1.pdf. 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 $M{~1~}M{~2~}...M{~i~}$ şi $M{~i+1~}M{~i+2~}...M{~n~}$ 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 $M{~i~}M{~i+1~}...M{~j~}$ 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 $M{~i~}$ este de dimensiuni $(d[i-1], d[i]), 1 &le; i &le; n$. Construcţia tabloului se face diagonală cu diagonală:
 
* <tex> d = 0: m[i, i] = 0, 1 \le i \le n </tex>
* <tex> d = 1: m[i, i + 1] = d[i - 1] * d[i] * d[i + 1], 1 \le i \le n - 1 </tex>
* <tex> 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 </tex>
 
Timpul de execuţie este de ordinul $O(N^3^)$, iar sursa demonstrativă se găseşte 'aici':job_detail/262669?action=view-source.
 
Pentru a studia în detaliu problema înmulţirii înlănţuite de matrici puteţi consulta capitolul 16 din '_Introducere în algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm de Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.
 
h2. 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:
 
* 'Redu':problema/redu
* 'Recycling':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2518, _UVa_
* 'Stiva':problema/stiva, _Baraj ONI, 2008_
* 'Expresii algebrice':problema/expresii
* "Game Po":http://acm.sgu.ru/problem.php?contest=0&problem=273, _SGU_

== include(page="template/taskfooter" task_id="podm") ==

4318