Problem nawiasowania ciągu macierzy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Problem nawiasowania ciągu macierzy – problemem znalezienia takiego nawiasowania iloczynu macierzy , by zminimalizować łączny koszt wszystkich mnożeń. Nawiasowanie takie nazywa się optymalnym. Mówimy, że iloczyn macierzy ma ustalone nawiasowanie, jeżeli tworzy go pojedyncza macierz, lub iloczyn dwóch iloczynów macierzy o ustalonym nawiasowaniu.

Przykład ustalonych nawiasowań[edytuj]

Niech będzie ciągiem macierzy. Ich iloczyn ma następujące ustalone nawiasowania:

Nawiasowanie a koszt obliczenia iloczynu macierzy[edytuj]

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 (dokładnie – wymaga mnożeń skalarnych)

Niech dane będą trzy macierze o rozmiarach odpowiednio 2×20, 20×1 i 1×10. Dla nawiasowania koszty wyniosą:

  • obliczenie iloczynu – koszt mnożeń; macierz ma rozmiary 2×1;
  • obliczenie iloczynu – koszt mnożeń;
  • razem: mnożeń skalarnych.

Dla tych samych macierzy, ale nawiasowania koszty wyniosą:

  • obliczenie iloczynu – koszt mnożeń; macierz ma rozmiary 20×10;
  • obliczenie iloczynu – koszt mnożeń;
  • razem: mnożeń skalarnych.

Przewaga nawiasowania pierwszego jest oczywista.

Własność optymalnej podstruktury[edytuj]

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

Dowód[edytuj]

Załóżmy, że dla optymalnego nawiasowania macierzy występuje podział między i , oraz, niewprost, że dla tego nawiasowania nawiasowanie nie jest optymalne. Wówczas można by w nawiasowaniu "podmienić" nawiasowanie na optymalne, w wyniku czego otrzymalibyśmy nowe nawiasowanie , lepsze od optymalnego – sprzeczność.

Rozwiązanie problemu nawiasowania macierzy[edytuj]

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 oznacza minimalny koszt wymnożenia macierzy o rozmiarach odpowiednio
Może być zdefiniowane następująco:

  • – nawiasowanie tylko jednej macierzy –
  • – nawiasowanie to musi wyznaczać punkt podziału p, taki, że (zgodnie z podpunktem o własności optymalnego nawiasowania) i są optymalnymi rozwiązaniami podproblemów. Wtedy jest równe sumie minimalnych kosztów obliczenia i oraz kosztu pomnożenia macierzy wynikowych tych podrozwiązań: