Problem nawiasowania ciągu macierzy

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 macierzyEdytuj

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 podstrukturyEdytuj

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

DowódEdytuj

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 macierzyEdytuj

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ń: