Problem nawiasowania macierzy

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Problem nawiasowania macierzy - jest problemem znalezienia takiego nawiasowania ciągu macierzy $\! A_0 A_1 \cdots A_n$ , by zminimalizować koszt poszczególnych mnożeń. Nawiasowanie takie nazywa się optymalnym. Mówimy, że iloczyn macierzy $\! A_0\cdot A_1\cdot \cdots \cdot A_n$ ma ustalone nawiasowanie, jeżeli tworzy go pojedyńcza macierz, lub iloczyn dwóch iloczynów macierzy o ustalonym nawiasowaniu.

Spis treści

1 Przykład ustalonych nawiasowań
2 Nawiasowanie a koszt obliczenia iloczynu macierzy
3 Własność optymalnej podstruktury
- 3.1 Dowód
4 Rozwiązanie problemu nawiasowania macierzy

[edytuj] Przykład ustalonych nawiasowań

Niech $\! A_0 A_1 A_2 A_3 A_4$ 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)))$

[edytuj] Nawiasowanie a koszt obliczenia iloczynu macierzy

Łatwo przekonać się, że wybór nawiasowania może mieć znaczący wynik 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)$ koszt iloczynu wyniesie:

$\! 2\cdot 20 \cdot 1\ =\ 40$ (koszt obliczenia $\! A_0\cdot A_1\ = \ A^{'}$ ) + $\! 2\cdot 1 \cdot 10\ =\ 20$ (koszt obliczenia $\! A^{'}\cdot A_2$ ). Razem: $\! 60$

Dla tych samych macierzy, ale nawiasowania $\! (A_0\cdot (A_1\cdot A_2))$ koszt mnożenia wyniesie:

$\! 20 \cdot 1 \cdot 10$ mnożeń dla $\! A_1\cdot A_2$ plus $\! 2\cdot 1\cdot 10$ mnożeń skalarnych

co daje łącznie $\! 220$ mnożeń skalarnych potrzebnych do pomnożenia wyniku przez $\! A_0$ . Oszczędność nawiasowania pierwszego jest oczywista.

[edytuj] Własność optymalnej podstruktury

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

[edytuj] 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ść.

[edytuj] 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} \cdots A_j$ $\! k[i][j]$ Może być zdefiniowane następująco:

$\! k[i][i]$ - nawiasowanie tylko jednej macierzy - $\! k[i][i]\ =\ 0$
$\! k[i][j]$ - nawiasonie 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$ plus koszt pomnożenia macierzy wynikowych tych podrozwiązań: