Problem nawiasowania ciągu macierzy

Problem nawiasowania ciągu macierzy – problemem znalezienia takiego nawiasowania iloczynu macierzy $\! A_0, A_1, \ldots 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×b i b×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 nawiasowania pierwszego 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} \cdots 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} \cdots A_p$ nie jest optymalne. Wówczas można by w nawiasowaniu $\! A_i A_{i+1} \cdots A_j$ "podmienić" nawiasowanie $\! A_i A_{i+1} \cdots A_p$ na optymalne, w wyniku czego otrzymalibyśmy nowe nawiasowanie $\! A_i A_{i+1} \cdots 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} \cdot \ldots \cdot A_j$ o rozmiarach odpowiednio $a_i\times a_{i+1},\ a_{i+1}\times a_{i+2},\ \ldots 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 \cdots A_p$ i $\! A_{p+1} \cdots A_j$ są optymalnymi rozwiązaniami podproblemów. Wtedy $\! k[i][j]$ jest równe sumie minimalnych kosztów obliczenia $\! A_i \cdots A_p$ i $\! A_{p+1} \cdots A_j$ oraz kosztu pomnożenia macierzy wynikowych tych podrozwiązań:

$\! k[i][j] = \min_{i\le m <j} \{k[i][m]\ +\ k[m+1][j]\ +\ a_i\cdot a_{m+1} \cdot a_{j+1}\}$