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 \dots \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^{\text{'}}=A_0\cdot A_1$ – koszt $2\cdot 20\cdot 1=40$ mnożeń; macierz $A^{\text{'}}$ ma rozmiary 2×1;
• obliczenie iloczynu $A^{\text{'}}\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^{{\text{'}}^{\prime }}=A_1\cdot A_2$ – koszt $20\cdot 1\cdot 10=200$ mnożeń; macierz $A^{{\text{'}}^{\prime }}$ ma rozmiary 20×10;
• obliczenie iloczynu $A_0\cdot A^{{\text{'}}^{\prime }}$ – 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]=\underset{i⩽m<j}{\min }\{k[i][m]+k[m+1][j]+a_i\cdot a_{m+1}\cdot a_{j+1}\}$