Problem nawiasowania ciągu macierzy

Problem nawiasowania ciągu macierzy – problemem znalezienia takiego nawiasowania iloczynu macierzy $A_{0},A_{1},\dots ,A_{n},$ by zminimalizować łączny koszt wszystkich mnożeń. Nawiasowanie takie nazywa się optymalnym. Mówimy, że iloczyn macierzy $A_{0}\cdot A_{1}\cdot \ldots \cdot A_{n}$ ma ustalone nawiasowanie, jeżeli tworzy go pojedyncza macierz lub iloczyn dwóch iloczynów macierzy o ustalonym nawiasowaniu.

Przykład ustalonych nawiasowań

Niech $A_{0},A_{1},A_{2},A_{3}$ będzie ciągiem macierzy. Ich iloczyn ma następujące ustalone nawiasowania:

$(((A_{0}\cdot A_{1})\cdot A_{2})\cdot A_{3})$

$((A_{0}\cdot (A_{1}\cdot A_{2}))\cdot A_{3})$

$((A_{0}\cdot A_{1})\cdot (A_{2}\cdot A_{3}))$

$(A_{0}\cdot ((A_{1}\cdot A_{2})\cdot A_{3}))$

$(A_{0}\cdot (A_{1}\cdot (A_{2}\cdot A_{3})))$

Nawiasowanie a koszt obliczenia iloczynu macierzy

Wybór nawiasowania może mieć znaczący wpływ na liczbę operacji potrzebnych do obliczenia iloczynu macierzy – koszt pomnożenia dwóch macierzy o wymiarach odpowiednio $a\times b$ i $b\times c$ wynosi $O(a\cdot b\cdot c)$ (dokładnie – wymaga $a\cdot b\cdot c$ mnożeń skalarnych).

Niech dane będą trzy macierze $A_{0},A_{1},A_{2}$ o rozmiarach odpowiednio 2×20, 20×1 i 1×10. Dla nawiasowania $((A_{0}\cdot A_{1})\cdot A_{2})$ koszty wyniosą:

• obliczenie iloczynu $A^{'}=A_{0}\cdot A_{1}$ – koszt $2\cdot 20\cdot 1=40$ mnożeń; macierz $A^{'}$ ma rozmiary 2×1;
• obliczenie iloczynu $A^{'}\cdot A_{2}$ – koszt $2\cdot 1\cdot 10=20$ mnożeń;
• razem: $40+20=60$ mnożeń skalarnych.

Dla tych samych macierzy, ale nawiasowania $(A_{0}\cdot (A_{1}\cdot A_{2})),$ koszty wyniosą:

• obliczenie iloczynu $A^{''}=A_{1}\cdot A_{2}$ – koszt $20\cdot 1\cdot 10=200$ mnożeń; macierz $A^{''}$ ma rozmiary 20×10;
• obliczenie iloczynu $A_{0}\cdot A^{''}$ – koszt $2\cdot 20\cdot 10=400$ mnożeń;
• razem: $200+400=600$ mnożeń skalarnych.

Przewaga pierwszego nawiasowania jest oczywista.

Własność optymalnej podstruktury

Można wykazać, że problem nawiasowania macierzy wykazuje własność optymalnej podstruktury.

Dowód

Załóżmy, że dla optymalnego nawiasowania macierzy $A_{i},A_{i+1},\dots ,A_{j}$ występuje podział między $A_{p}$ i $A_{p+1}$ oraz, niewprost, że dla tego nawiasowania nawiasowanie $A_{i},A_{i+1},\dots ,A_{p}$ nie jest optymalne. Wówczas można by w nawiasowaniu $A_{i},A_{i+1},\dots ,A_{j}$ „podmienić” nawiasowanie $A_{i},A_{i+1},\dots ,A_{p}$ na optymalne, w wyniku czego otrzymalibyśmy nowe nawiasowanie $A_{i},A_{i+1},\dots ,A_{j}$ lepsze od optymalnego – sprzeczność.

Rozwiązanie problemu nawiasowania macierzy

Problem nawiasowania ciągu macierzy można łatwo rozwiązać, stosując algorytm dynamiczny. Definiujemy koszt optymalnego nawiasowania jako funkcję optymalnych rozwiązań podproblemów.

Niech $k[i][j]$ oznacza minimalny koszt wymnożenia macierzy $A_{i},A_{i+1},\dots ,A_{j}$ o rozmiarach odpowiednio $a_{i}\times a_{i+1},a_{i+1}\times a_{i+2},\dots ,a_{j}\times a_{j+1}.$
$k[i][j]$ może być zdefiniowane następująco:

• $k[i][i]$ – nawiasowanie tylko jednej macierzy – $k[i][i]=0$
• $k[i][j]$ – nawiasowanie to musi wyznaczać punkt podziału $p$ taki, że (zgodnie z podpunktem o własności optymalnego nawiasowania) $A_{i},\dots ,A_{p}$ i $A_{p+1},\dots ,A_{j}$ są optymalnymi rozwiązaniami podproblemów. Wtedy $k[i][j]$ jest równe sumie minimalnych kosztów obliczenia $A_{i},\dots ,A_{p}$ i $A_{p+1},\dots ,A_{j}$ oraz kosztu pomnożenia macierzy wynikowych tych podrozwiązań:

$k[i][j]=\min _{i\leqslant m<j}\{k[i][m]+k[m+1][j]+a_{i}\cdot a_{m+1}\cdot a_{j+1}\}$