| dbpprop:abstract
|
- Matrix chain multiplication is an optimization problem that can be solved using dynamic programming. Given a sequence of matrices, we want to find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications. We have many options because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have: (ABC)D = (AB)(CD) = A(BCD) = A(BC)D = ... However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then, (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations Clearly the first method is the more efficient. Now that we have identified the problem, how do we determine the optimal parenthesization of a product of n matrices? We could go through each possible parenthesization (brute force), but this would require time O(2), which is very slow and impractical for large n. The solution, as we will see, is to break up the problem into a set of related subproblems. By solving subproblems one time and reusing these solutions many times, we can drastically reduce the time required. This is known as dynamic programming.
- Matrix-Kettenmultiplikation bezeichnet die Multiplikation von mehreren Matrizen. Da die Matrizenmultiplikation assoziativ ist, kann man dabei beliebig klammern. Dadurch wächst die Anzahl der möglichen Berechnungswege exponentiell mit der Länge der Matrizenkette an. Mit der Methode der dynamischen Programmierung kann die Klammerung der Matrix-Kette optimiert werden, so dass die Gesamtanzahl arithmetischer Operationen minimiert wird. Der Algorithmus hat eine Laufzeit von <math>O</math><math>(n^3)</math>. Sei beispielsweise <math>A</math> eine <math>10\times 30</math> Matrix, <math>B</math> eine <math>30\times 5</math> Matrix und <math>C</math> eine <math>5\times 60</math> Matrix. Dann gibt es zwei verschiedene Arten, den Term <math>ABC</math> zu klammern: <math>(AB)C</math> <math>A(BC)</math> Die Anzahl der grundlegenden Operationen berechnet sich wie folgt: <math>(AB)C \rightarrow (10\cdot 30\cdot 5) + (10\cdot 5\cdot 60) = 1500 + 3000 = 4500</math> <math>A(BC) \rightarrow (30\cdot 5\cdot 60) + (10\cdot 30\cdot 60) = 9000 + 18000 = 27000</math>
- Problem nawiasowania ciągu macierzy - jest problemem znalezienia takiego nawiasowania ciągu macierzy <math>\! A_0 A_1 \cdots A_n</math>, by zminimalizować koszt poszczególnych mnożeń. Nawiasowanie takie nazywa się optymalnym. Mówimy, że iloczyn macierzy <math>\! A_0\cdot A_1\cdot \cdots \cdot A_n</math> ma ustalone nawiasowanie, jeżeli tworzy go pojedyncza macierz, lub iloczyn dwóch iloczynów macierzy o ustalonym nawiasowaniu.
- Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц <math> A_1, A_2, ... , A_n и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов <math> A_{i - 1 совпадает с количеством строк <math> A_i матрицы).
- 矩阵链乘积是可用動態規劃解决的最佳化问题。給定一序列矩陣，期望求出相乘這些矩陣的最有效方法。此問題並不是真的去執行其乘法，而只是決定執行乘法的順序而已。 因為矩陣乘法具有結合律，所有其運算順序有很多種選擇。換句話說，不論如何括號其乘積，最後結果都會是一樣的。例如，若有四個矩陣A、B、C和D，將可以有： (ABC)D = (AB)(CD) = A(BCD) = A(BC)D = ... 但括號其乘積的順序是會影響到需計算乘積所需簡單算術運算的數目，即其效率。例如，設A為一10×30矩陣，B為30×5矩陣與C為5×60矩陣，則 (AB)C 有 (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 個運算 A(BC) 有 (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 個運算 明顯地，第一種方式要有效多了。既然以確認過此問題了，那要如何決定n個矩陣相乘的最佳順序呢？可以比較每一順序的運算量(使用蠻力)，但這將需要時間O(2)，是一種非常慢且對大n不實在的方法。那解決方法，如我們將看到的，是將問題分成一套相關的子問題。以解答子問題一次而再使用其解答數次，即可以徹底地得出其所需時間。此一方法稱為動態規劃。
|
| rdfs:comment
|
- Matrix chain multiplication is an optimization problem that can be solved using dynamic programming. Given a sequence of matrices, we want to find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications. We have many options because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same.
- Matrix-Kettenmultiplikation bezeichnet die Multiplikation von mehreren Matrizen. Da die Matrizenmultiplikation assoziativ ist, kann man dabei beliebig klammern. Dadurch wächst die Anzahl der möglichen Berechnungswege exponentiell mit der Länge der Matrizenkette an. Mit der Methode der dynamischen Programmierung kann die Klammerung der Matrix-Kette optimiert werden, so dass die Gesamtanzahl arithmetischer Operationen minimiert wird.
- Problem nawiasowania ciągu macierzy - jest problemem znalezienia takiego nawiasowania ciągu macierzy <math>\! A_0 A_1 \cdots A_n</math>, by zminimalizować koszt poszczególnych mnożeń. Nawiasowanie takie nazywa się optymalnym. Mówimy, że iloczyn macierzy <math>\! A_0\cdot A_1\cdot \cdots \cdot A_n</math> ma ustalone nawiasowanie, jeżeli tworzy go pojedyncza macierz, lub iloczyn dwóch iloczynów macierzy o ustalonym nawiasowaniu.
- Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц <math> A_1, A_2, ... , A_n и требуется минимизировать количество скалярных операций для вычисления их произведения.
- 矩阵链乘积是可用動態規劃解决的最佳化问题。給定一序列矩陣，期望求出相乘這些矩陣的最有效方法。此問題並不是真的去執行其乘法，而只是決定執行乘法的順序而已。 因為矩陣乘法具有結合律，所有其運算順序有很多種選擇。換句話說，不論如何括號其乘積，最後結果都會是一樣的。例如，若有四個矩陣A、B、C和D，將可以有： (ABC)D = (AB)(CD) = A(BCD) = A(BC)D = ...
|
![[RDF Data]](/statics/sw-cube.png)
