Как это сделать? Мы можем перебрать все расстановки скобок (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''<sup>2</sup>/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''<sup>3</sup>) from O(2<sup>''n''</sup>), which is more than efficient enough for real applications. This is [[Top-down and bottom-up design|top-down]] dynamic programming.
Pseudocode (without memoization):
