Изменения

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

== Подробное описание задачи ==Произведение матриц — ассоциативная операция. Когда матрицы велики по одному измерению и малы по другому, количество скалярных операций может серьёзно зависеть от порядка перемножений матриц. Допустим, нам даны 3 матрицы <tex> A_1, A_2, A_3 </tex> размерами соответственно <tex> 10 \times 100, 100 \times 5</tex> и <tex>5 \times 50</tex>. Существует 2 способа их перемножения (расстановки скобок): <tex>((A_1A_2)A_3)</tex> и <tex>(A_1(A_2A_3))</tex>. В первом случае нам потребуется <tex>10\cdot100\cdot5 + 10\cdot5\cdot50 = 7500</tex> скалярных умножений, а во втором случае <tex>100\cdot5\cdot50 + 10\cdot100\cdot50 = 75000</tex> умножений — разница налицо. Поэтому может оказаться выгоднее потратить некоторое время на предобработку, решивОднако, порядок в каком порядке лучше всего умножать, чем умножать сразу котором мы расставим скобки в лоб.Таким образом, даны <tex>n</tex> матриц: <tex>A_1: \, p_0 \times p_1</tex>, <tex>A_2: \, p_1 \times p_2</tex>, …, <tex>A_n: \, p_{n-1} \times p_{n}</tex>. Требуется определить, в каком порядке перемножать их, чтобы нашем выражении повлияет на количество простых арифметических операций умножения было минимальным.==Динамическое решение=====Сведение задачи к подзадачам ===Обозначим результат перемножения матриц <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(10 &times; 30), B = (30 & itimes; 5), C =j \\ min(m[i,k] + m[k+1,j] + p_{i-1}p_kp_j | i \le k < j5 &times; 60) & i < j \end{array} \right.</tex>Тогда:

Объясняется оно просто: для того(''AB'')''C'' = (10&times;30&times;5) + (10&times;5&times;60) = 1500 + 3000 = 4500 операций:''A''(''BC'') = (30&times;5&times;60) + (10&times;30&times;60) = 9000 + 18000 = 27000 операций. Очевидно, что первый способ гораздо эффективней. Теперь мы поняли, чтобы что нам надо найти произведение оптимальную расстановку скобок в нашем выражении из ''n'' матриц <tex>A_{i. Как это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнение этого алгоритма будет эксапаненциально рости от ''n'' количества матриц.j}</tex> при i=j не нужно ничего делать — Решение данной проблемы, как мы увидим — это разбить нашу задачу на подзадачи. Так же мы увидим, что с помощю решения однократного решения подзадачи и есть сама матрица <tex>A_i</tex>повторного использования ответа, мы сможем заметно сократить асимптотику. == Решение динамическим программированием == Сначала, давайте считать то, что мы хотим знать минимальное количесвто операций (или минимальную стоимость), необходимых для перемножения матриц. При нетривиальном случае Если мы перебираем все точки разбиения перемножаем только две матрицы <tex>A_{i, то мы можем осуществить это только едиственным способом, следовательно минимальная стоимость — это стоимость этого перемножения.В общем, мы можем найти минимальную стоимость используя следующий рекурсивный алгоритм: * Взять последовательность матриц и разделить её на две части.j}</tex> * Найти минимальную стоимость перемножения на матрицы <tex>A_{iкаждой подпоследовательности.* Сложить эти две стоимости и прибавить к этому стоимость перемножения двух получившихся матриц.k}</tex> * Сделать это для каждой возможной позиции в последовательности, в которой она может быть разделена и <tex>A_{k+1взять минимум среди всех результатов..j}</tex> Например, если у нас есть четыре матрицы ''ABCD'', мы посчитаем для (''A'')(''BCD''), (''AB'')(''CD''), и (''ABC'')(''D''), ищем кол-во операцийделая рекурсивные вызовы, необходимое чтобы их получить найти минимальную стоимость на ''ABC'', ''AB'', ''CD'', и затем перемножаем для получения матрицы <tex>A_{i''BCD''.Потом среди них мы выбираем лучший вариант.j}</tex>Так же, этот алгоритм дает не только минимальную стоимость, но и показывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом, каким дается нам минимальная стоимость и перемножить их между собой.(Оно будет равно кол-ву операций Внезапно, если мы применим этот алгоритм, то мы обнаружим, что это так же медленно, потраченное как и наивный способ перебирания всех скобочных последовательностей! Что пошло не так? Ответом на решение подзадач + этот вопрос является то факт, что мы делаем много ненужной работы. Например, в выше описанном алгоритме, мы сделали рекурсивный вызов, чтобы найти наилучшую стоимость умножения матриц <tex>A_{iдля подсчета ''ABC'' и ''AB''.Но нахождение наилучшей стоимости для подсчета ''ABC'' так же требует нахождения лучшей стоимости для ''AB''.k}A_{k+1Так как рекурсия растет вглбь все больше и больше, то и число ненужных повторений увеличивается. Одно из простых решений: ''меморизация''.j}</tex>)Каждый раз, когда мы считаем минимальную стоимость на отрезке, мы сохраняем ответ. СчитаемКогда у нас просят посчитать это ещё раз, что размеры матриц заданы в массиве <tex>p</tex> то мы сразу же выдадим ответ и размер матрицы не будем пересчитывать. Хоть у нас <texmath>A_i<n^2/tex> равен <tex>p_{i-1} \times p_i2 </texmath>. В данном случае рекурсивный метод нельзя использовать напрямую — он будет экспоненциальным  Одно из-за большого кол-ва перекрывающихся подзадачпростых решений — это меморизация.=== Динамическое программирование ===Будем Каждый раз, когда мы считаем минимальную стоимость перемножения определенной подпоследовательности, давайте мы будем запоминать в двумерном массиве <tex>m</tex> результаты вычислений для подзадачответ. Если мы когда либо ещё раз захотим посчитать это ещё раз, чтобы избежать пересчета для то мы уже вычислявшихся подзадачбудет иметь ответ и не будем пересчитывать. После вычислений ответ будет в Поскольку существует всего около <texmath>m[1,n]^2/2</texmath>, где ''n'' — это количество матриц, то память занимаемая программой будет не так велика. Можно сказать, что с помощью этого простого трюка мы уменьшили асимптотику алгоритма с O(Сколько перемножений требуется для последовательности матриц от <texmath>12n</texmath> ) до O(<texmath>n^3</texmath> — то есть ответ на поставленную задачу), что является достаточно эффективным для реальных приложений.Сложность алгоритма будет  Псевдокод:<texpre>O(n^3) int dp[1000][1000];vector<pair<int, int> > v;// v[i].first — размер i-той матрицы по горизонтали // v[i].second — размер i-той матрицы по вертикали//tex>dp[i][j] — меморизация на отрезке [i, j)int matrixChainMultiplication(int l, так как у нас <tex>int r){n \choose 2}< //l — включая в отрезок //tex> вариантов выбора r — исключая из отрезка if dp[l][r] == -1 if l == r - 1 dp[l][r] = 0; else dp[l][r] = 1000 * 1000 * 1000; for (int i = l + 1; i <tex>r; i++) dp[l][r] = min(dp[l][r], j : v[l].first * v[i].first * v[r - 1 \le ].second + matrixChainMultiplication(l, i \le j \le n</tex> и <tex>O) + matrixChainMultiplication(Ni, r)); return dp[l][r];}</texpre> точек разделения для каждого варианта *Замечания : Индексирование массива ''p'' начинается с нуля, а у массивов ''m'' и ''s'' с единицы.