Problem nawiasowania ciągu macierzy

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

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

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 i 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 pierwszego nawiasowania 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 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 | 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 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 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ń: