macierz ma rozmiary 20×10; obliczenie iloczynu – koszt mnożeń; razem: mnożeń skalarnych.
Przewaga pierwszego nawiasowania jest oczywista.
Własność optymalnej podstruktury Można wykazać, że problem nawiasowania macierzy wykazuje własność optymalnej podstruktury.
Dowód 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 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ń:
Kategoria:Działania na macierzach Kategoria:Programowanie dynamiczne