Изменения

'''Задача о порядке перемножения матриц''' — классическая задача, которая может быть решена с помощью динамического программирования. В этой задаче нам дана последовательность матриц, в которой мы хотим найти самый эффективный способ перемножения их. На самом деле задача заключается не в нахождении результата перемножения, а просто нужно найти порядокв нахождении нужного порядока, в котором нам надо их перемножитьмы будем перемножать.

У нас есть много способов, потому что перемножение ассоциативнооперация перемножения ассоциативна. Другими словами, нет разницы как мы расставим скобки между множителями, результат будет один и тот же. Например, если у нас есть четыре матрицы ''A'', ''B'', ''C'' и ''D'', то у нас есть следующие варианты:

Однако, порядок в котором мы расставим скобки в нашем выражении повлияет на количество простых арифметических операций, которые мы потратим на вычисление ответа, или, другими словами, на ''эффективность''.

Как это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнение этого алгоритма будет эксапаненциально рости от ''n'' количества матриц. Решение данной проблемы, как мы увидим — это разбить нашу задачу на подзадачи. С Так же мы увидим, что с помощю решения подзадач по одному разу однократного решения подзадачи и повторного использования решенияответа, мы сможем заметно сократить асимптотику. Эта задача входит в классические задачи

== A Dynamic Programming Algorithm Решение динамическим программированием ==

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, we save it. If we are ever asked to compute it again, we simply give the saved answer, and do not recompute it. Since there are about ''nмеморизация''²/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''Хоть у нас <supmath>3<n^2/sup>) from O(2<sup>''n''</supmath>), which is more than efficient enough for real applications. This is [[Top-down and bottom-up design|top-down]] dynamic programming.

Pseudocode Одно из простых решений — это меморизация. Каждый раз, когда мы считаем минимальную стоимость перемножения определенной подпоследовательности, давайте мы будем запоминать ответ. Если мы когда либо ещё раз захотим посчитать это ещё раз, то мы уже будет иметь ответ и не будем пересчитывать. Поскольку существует всего около <math>n^2/2</math>, где ''n'' — это количество матриц, то память занимаемая программой будет не так велика. Можно сказать, что с помощью этого простого трюка мы уменьшили асимптотику алгоритма с O(without memoization<math>2n</math>)до O(<math>n^3</math>), что является достаточно эффективным для реальных приложений. Псевдокод:

 int dp[1000][1000];vector<pair<int, int> > v;// Matrix Ai has dimension pv[i].first — размер i-1той матрицы по горизонтали // v[i] x p.second — размер i-той матрицы по вертикали// dp[i] for [j] — меморизация на отрезке [i = 1..n, j)Matrix-Chain-Orderint matrixChainMultiplication(int p[]l, int r)

// length[p] = n + 1 n = p.length - 1;l — включая в отрезок // m[i,j] = Minimum number of scalar multiplications (i.e., cost)r — исключая из отрезка // needed to compute the matrix A if dp[il]A[i+1]...A[jr] = A[i..j]= -1 // cost is zero when multiplying one matrix for (i if l == r - 1; i <= n; i++) m dp[i,il][r] = 0; else for (L dp[l][r] =21000 * 1000 * 1000; L<=n; L++) { // L is chain length for (int i=l + 1; i<=n-L+1r; i++) { j = i+L-1; m dp[l][i,jr] = MAXINT; for min(k=i; k<=j-1; k++) { // q = cost/scalar multiplications q = mdp[i,kl] + m[k+1r],j] + pv[i-1l].first *pv[ki].first *pv[jr - 1]; if .second + matrixChainMultiplication(q < m[l, i,j]) { m[+ matrixChainMultiplication(i,j] = qr)); // s return dp[i,jl] = Second auxiliary table that stores k // k = Index that achieved optimal cost s[i,jr] = k; } } } }

*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 ''np''начинается с нуля, the number of matrices:** Compute the minimum costs of each subsequence of length а у массивов ''km'', using the costs already computed.When weи 're done, we have the minimum cost for the full sequence. Although it also requires O('s'n''³) 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с единицы.