Изменения

'''{{Задача о порядке перемножения матриц''' — классическая задача динамического программирования, в которой дана |definition = Дана последовательность матриц из <tex> A_1, A_2, ..., A_n n</tex> и матриц, требуется минимизировать количество скалярных операций для вычисления найти самый эффективный способ их произведенияперемножения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то }} У нас есть множество способов перемножить матрицы, потому что операция перемножения ассоциативна. Другими словами, нет разницы в каком порядке расставляются скобки между множителями, результат будет один и тот же.  [[Правильные скобочные последовательности | Расстановок скобок]] достаточно много и их количество столбцов очень быстро растет. Точное количество всевозможных вариантов равно <tex> A_{i - 1}n</tex> совпадает с количеством строк <tex> A_i </tex> матрицы)–ому [[Числа Каталана | числу Каталана]].== Подробное описание задачи ==Произведение матриц — ассоциативная операция. Когда матрицы велики по одному измерению и малы по другомуОднако, порядок в котором расставляются скобки между матрицами повлияет на количество скалярных арифметических операций может серьёзно зависеть от порядка перемножений матриц, которые потребуются на вычисление ответа, или, другими словами, на ''эффективность''. Допустим Например, нам даны 3 матрицы предположим, что <tex> A_1, A_2, A_3 \dim{A}= 10 \times 30</tex> размерами соответственно , <tex> 10 \times 100, 100 dim{B} = 30 \times 5</tex> и , <tex>\dim{C} = 5 \times 5060</tex>. Существует 2 способа их перемножения (расстановки скобок)Тогда: : Для <tex>((A_1A_2)A_3A \times B)\times C</tex> и будет <tex>(A_1(A_2A_3))</tex>. В первом случае нам потребуется <tex>10\cdot100times30\cdot5 times5) + (10\cdot5times5\cdot50 times60) = 7500</tex> скалярных умножений, а во втором случае <tex>100\cdot5\cdot50 1500 + 10\cdot100\cdot50 3000 = 750004500</tex> умножений — разница налицо. Поэтому может оказаться выгоднее потратить некоторое время на предобработку, решив, в каком порядке лучше всего умножать, чем умножать сразу в лоб.операцийТаким образом, даны <tex>n</tex> матриц: Для <tex>A_1: A \, p_0 times(B \times p_1C)</tex>, будет <tex>A_2: (30\, p_1 times5\times p_2</tex>, …, <tex>A_n: times60) + (10\, p_{n-1} times30\times p_{n}times60) = 9000 + 18000 = 27000</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[f(i, j])</tex> минимальное количество скалярных умножений для вычисления матрицы <tex>A_M_{i..j}</tex>. Получаем , то получаем следующее рекуррентное соотношение:<tex> m[f(i,j] ) = \left \{

\min\limits_{i \leqslant k < j}{(f(m[i,k] ) + m[f(k+1,j] ) + p_{i-1}p_kp_j | i \le k < j) } & i < j

Объясняется оно просто: для того, чтобы найти произведение матриц <tex>A_M_{i..j}</tex> при <tex>i=j </tex> не нужно ничего делать — это и есть сама матрица <tex>A_iM_i</tex>. При нетривиальном случае мы перебираем все точки разбиения матрицы <tex>A_M_{i..j}</tex> на матрицы <tex>A_M_{i..k}</tex> и <tex>A_M_{k+1..j}</tex>, ищем кол-во количество операций, необходимое чтобы их получить и затем перемножаем для получения матрицы <tex>A_M_{i..j}</tex>.(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц <tex>A_M_{i..k}A_M_{k+1..j}</tex>). Считаем, что размеры матриц заданы в массиве <tex>p</tex> и размер матрицы <tex>A_iM_i</tex> равен <tex>p_{i-1} \times p_i</tex>. В данном случае рекурсивный метод нельзя использовать напрямую — он будет экспоненциальным из-за большого кол-ва перекрывающихся подзадач.=== Динамическое программирование ===Будем запоминать в двумерном массиве Чтобы привести пример, давайте вернемся к нашим матрицам. Если у нас есть четыре матрицы <tex>mABCD</tex> результаты вычислений , то мы посчитаем для подзадач<tex>(A)(BCD)</tex>, <tex>(AB)(CD)</tex>, и <tex>(ABC)(D)</tex>, делая рекурсивные вызовы на отрезках <tex>ABC</tex>, <tex>AB</tex>,<tex>CD</tex>, и <tex>BCD</tex>, чтобы найти минимальную стоимость. Потом среди них выбираем лучший вариант. Так же, этот алгоритм дает не только минимальную стоимость, но и показывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом матрицы, каким дается нам минимальная стоимость. Однако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех [[Правильные скобочные последовательности | скобочных последовательностей]]. Делается значительное количество ненужной работы. Например, в выше описанном алгоритме, осуществляется рекурсивный вызов, чтобы избежать пересчета найти наилучшую стоимость для уже вычислявшихся подзадачподсчета <tex>ABC</tex> и <tex>AB</tex>. После вычислений ответ будет в Но нахождение наилучшей стоимости для подсчета <tex>m[1,n]ABC</tex>(Сколько перемножений требуется так же требует нахождения лучшей стоимости для последовательности матриц от <tex>1AB</tex> до . Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется <tex>n</tex> — –ому [[Числа Каталана | числу Каталана]], да плюс вычисление для каждой [[Правильные скобочные последовательности | правильной скобочной последовательности]] ''затрат'' на перемножение (то есть ответ на поставленную задачу).Сложность алгоритма будет <tex>O(n^3\cdot C_n)</tex>, так ). Так как у нас <tex>N</tex>­-ое [[Числа Каталана | число Каталана]] равняется <tex dpi="163"> \frac{1}{n+1}{2 n \choose 2n}</tex> вариантов выбора или асимптотически <texdpi="163">i\frac{4^n}{n^{3/2}\sqrt{\pi}} </tex>, а это быстро возрастающая функциия, нам бы хотелось решение, j : 1 \le которое работает быстрее. === Псевдокод ===   '''int''' dp[][] <font color="green">// dp[i][j] — ответ на отрезке [i , j)</font> \le '''int''' v[] <font color="green">// Массив v[] — хранит все размеры матриц по порядку // Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократно // l — включая в отрезок, r — исключая из отрезка. Изначально l = 0, r = n, где n {{---}} длина последовательности</font> j \le n'''int''' matrixChainMultiplication('''int''' l, '''int''' r) '''if''' dp[l][r] == -1 <font color="green">// Если значение динамики не посчитано</font> '''if''' l == r - 1 dp[l][r] = 0 <font color="green"> // Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю</texfont> и '''else''' dp[l][r] = <tex>O(N)\infty</tex> точек разделения для каждого варианта '''for''' i = l + 1 '''to''' r - 1 dp[l][r] = min(dp[l][r], v[l] * v[i] * v[r] + matrixChainMultiplication(l, i) + matrixChainMultiplication(i, r)) '''return''' dp[l][r] == См.также == *[[Задача о наибольшей общей подпоследовательности ]]*[[Кратчайший путь в ациклическом графе ]]*[[Задача о расстановке знаков в выражении]]*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами | Aлгоритм Кока-Янгера-Касами ]]*[[Правильные скобочные последовательности | Правильные скобочные последовательности ]]== Источники информации ==

==Ссылки==использованы материалы ru.wikipedia.org *[http://ruen.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B5_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86Matrix_chain_multiplication Wikipedia {{---}} Matrix chain multiplication]== Литература ==

* Томас Х. Кормен и др. Алгоритмы[[Категория: построение Дискретная математика и анализалгоритмы]]* Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms[[Категория:Динамическое_программирование]]