Как это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнение этого алгоритма будет эксапаненциально рости от ''n'' количества матриц. Решение данной проблемы, как мы увидим — это разбить нашу задачу на подзадачи. С помощю решения подзадач по одному разу и повторного использования решения, мы сможем заметно сократить асимптотику. Эта задача входит в классические задачи
==Динамическое решениеA Dynamic Programming Algorithm =====Сведение задачи к подзадачам ===Обозначим результат перемножения матриц <tex>A_iA_{i+1} \ldots A_j</tex> через <tex>A_{i..j}</tex>, где <tex>i \le j</tex>. Если <tex> i<j</tex>, то при любом способе расстановки скобок, последнее выполненное умножение для вычисления <tex>A_{i..j}</tex> между матрицами <tex>A_k</tex> и <tex>A_{k+1}, i \le k<j</tex>, то есть чтобы вычислить <tex>A_{i..j}</tex> надо сначала вычислить <tex>A_{i..k}</tex>, потом <tex>A_{k+1..j}</tex> и затем их перемножить.Заметим, что если способ расстановки скобок оптимален, то расстановка скобок в этих матрицах должна быть оптимальной, иначе если бы существовал более эффективный способ расстановки скобок в матрицах <tex>A_{i..k}</tex> и <tex>A_{k+1..j}</tex>, то мы могли бы получить <tex>A_{i..j}</tex> за меньшее число умножений, получаем противоречие, что расстановка скобок в <tex>A_{i..j}</tex> оптимальна. Таким образом мы свели задачу к подзадачам. Это означает, что возможно решить задачу, используя динамическое программирование на подотрезке.===Рекурсивное решение ===Обозначим через <tex>m[i, j]</tex> минимальное количество скалярных умножений для вычисления матрицы <tex>A_{i..j}</tex>. Получаем следующее рекуррентное соотношение:<tex> m[i,j] = \left \{ \begin{array}{ll} 0, & i=j \\ min(m[i,k] + m[k+1,j] + p_{i-1}p_kp_j | i \le k < j) & i < j \end{array} \right.</tex>
Объясняется оно простоTo begin, let's assume that all we really want to know is the minimum cost, or minimum number of arithmetic operations, needed to multiply out the matrices. If we're only multiplying two matrices, there's only one way to multiply them, so the minimum cost is the cost of doing this. In general, we can find the minimum cost using the following [[recursion|recursive algorithm]]: * Take the sequence of matrices and separate it into two subsequences.* Find the minimum cost of multiplying out each subsequence.* Add these costs together, and add in the cost of multiplying the two result matrices.* Do this for each possible position at which the sequence of matrices can be split, and take the minimum over all of them. For example, if we have four matrices ''ABCD'', we compute the cost required to find each of (''A'')(''BCD''), (''AB'')(''CD''), and (''ABC'')(''D''), making recursive calls to find the minimum cost to compute ''ABC'', ''AB'', ''CD'', and ''BCD''. We then choose the best one. Better still, this yields not only the minimum cost, but also demonstrates the best way of doing the multiplication: just group it the way that yields the lowest total cost, and do the same for each factor. Unfortunately, if we implement this algorithm we discover that it's just as slow as the naive way of trying all permutations! What went wrong? The answer is that we're doing a lot of redundant work. For example, above we made a recursive call to find the best cost for computing both ''ABC'' and ''AB''. But finding the best cost for computing ABC also requires finding the best cost for ''AB''. As the recursion grows deeper, more and more of this type of unnecessary repetition occurs. One simple solution is called [[memoization]]: для тогоeach time we compute the minimum cost needed to multiply out a specific subsequence, чтобы найти произведение матриц <tex>A_{iwe save it.If we are ever asked to compute it again, we simply give the saved answer, and do not recompute it.j}Since there are about ''n''</texsup> при i=j не нужно ничего делать — это и есть сама матрица 2<tex/sup>A_i</tex>2 different subsequences, where ''n'' is the number of matrices, the space required to do this is reasonable. При нетривиальном случае мы перебираем все точки разбиения матрицы It can be shown that this simple trick brings the runtime down to O(''n''<texsup>A_{i..j}3</texsup> на матрицы ) from O(2<texsup>A_{i..k}''n''</texsup> и <tex>A_{k+1), which is more than efficient enough for real applications.This is [[Top-down and bottom-up design|top-down]] dynamic programming.j} Pseudocode (without memoization):<pre>//tex>, ищем колMatrix Ai has dimension p[i-во операций, необходимое чтобы их получить и затем перемножаем для получения матрицы <tex>A_{1] x p[i] for i= 1..j}<nMatrix-Chain-Order(int p[]){ //tex>length[p] = n + 1 n = p.(Оно будет равно колlength -ву операций1; // m[i, потраченное на решение подзадач + стоимость умножения матриц <tex>A_{j] = Minimum number of scalar multiplications (i.e.k}A_{k, cost) // needed to compute the matrix A[i]A[i+1]...A[j}] = A[i..j] // cost is zero when multiplying one matrix for (i = 1; i </tex>= n; i++). Считаем m[i, что размеры матриц заданы в массиве <tex>pi] = 0; for (L=2; L<=n; L++) { /tex> и размер матрицы <tex>A_i</tex> равен L is chain length for (i=1; i<tex>p_=n-L+1; i++) { j = i+L-1} \times p_i</tex>. В данном случае рекурсивный метод нельзя использовать напрямую — он будет экспоненциальным из-за большого кол-ва перекрывающихся подзадач.; m[i,j] =MAXINT; for (k=i; k<= Динамическое программирование j-1; k++) { // q =cost/scalar multiplications q ==Будем запоминать в двумерном массиве <tex>m</tex> результаты вычислений для подзадач[i, чтобы избежать пересчета для уже вычислявшихся подзадач. После вычислений ответ будет в <tex>k] + m[k+1,nj]</tex>(Сколько перемножений требуется для последовательности матриц от <tex>+ p[i-1</tex> до <tex>n</tex> — то есть ответ на поставленную задачу).Сложность алгоритма будет <tex>O]*p[k]*p[j]; if (n^3)q </tex>m[i, так как у нас <tex>j]) {n \choose 2}< m[i,j] = q; //tex> вариантов выбора <tex>s[i, j : 1 \le ] = Second auxiliary table that stores k // k = Index that achieved optimal cost s[i \le ,j \le n] = k; } } } }}</texpre> и *Note : The first index for p is 0 and the first index for m and s is 1Another solution is to anticipate which costs we will need and precompute them. It works like this:* For each ''k'' from 2 to ''n'', the number of matrices:** Compute the minimum costs of each subsequence of length ''k'', using the costs already computed.When we're done, we have the minimum cost for the full sequence. Although it also requires O(''n''<texsup>O(N)3</texsup> точек разделения для каждого варианта) time, this approach has the practical advantages that it requires no recursion, no testing if a value has already been computed, and we can save space by throwing away some of the subresults that are no longer needed. This is bottom-up dynamic programming: a second way by which this problem can be solved.
==Ссылки==
