Problem nawiasowania ciągu macierzy

Problem nawiasowania ciągu macierzy – problemem znalezienia takiego nawiasowania iloczynu macierzy ${\displaystyle A_{0},A_{1},\dots ,A_{n},}$ by zminimalizować łączny koszt wszystkich mnożeń. Nawiasowanie takie nazywa się optymalnym. Mówimy, że iloczyn macierzy ${\displaystyle 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 ${\displaystyle A_{0},A_{1},A_{2},A_{3}}$ będzie ciągiem macierzy. Ich iloczyn ma następujące ustalone nawiasowania:

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

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

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

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

${\displaystyle (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 ${\displaystyle a\times b}$ i ${\displaystyle b\times c}$ wynosi ${\displaystyle O(a\cdot b\cdot c)}$ (dokładnie – wymaga ${\displaystyle a\cdot b\cdot c}$ mnożeń skalarnych).

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

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

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

• obliczenie iloczynu ${\displaystyle A^{''}=A_{1}\cdot A_{2}}$ – koszt ${\displaystyle 20\cdot 1\cdot 10=200}$ mnożeń; macierz ${\displaystyle A^{''}}$ ma rozmiary 20×10;
• obliczenie iloczynu ${\displaystyle A_{0}\cdot A^{''}}$ – koszt ${\displaystyle 2\cdot 20\cdot 10=400}$ mnożeń;
• razem: ${\displaystyle 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 ${\displaystyle A_{i},A_{i+1},\dots ,A_{j}}$ występuje podział między ${\displaystyle A_{p}}$ i ${\displaystyle A_{p+1}}$ oraz, niewprost, że dla tego nawiasowania nawiasowanie ${\displaystyle A_{i},A_{i+1},\dots ,A_{p}}$ nie jest optymalne. Wówczas można by w nawiasowaniu ${\displaystyle A_{i},A_{i+1},\dots ,A_{j}}$ „podmienić” nawiasowanie ${\displaystyle A_{i},A_{i+1},\dots ,A_{p}}$ na optymalne, w wyniku czego otrzymalibyśmy nowe nawiasowanie ${\displaystyle 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 ${\displaystyle k[i][j]}$ oznacza minimalny koszt wymnożenia macierzy ${\displaystyle A_{i},A_{i+1},\dots ,A_{j}}$ o rozmiarach odpowiednio ${\displaystyle a_{i}\times a_{i+1},a_{i+1}\times a_{i+2},\dots ,a_{j}\times a_{j+1}.}$
${\displaystyle k[i][j]}$ może być zdefiniowane następująco:

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

${\displaystyle 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}\}}$