Problem nawiasowania ciągu macierzy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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ń[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

Dowód[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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}\}