Изменения

'''{{Задача о порядке перемножения матриц''' (англ. ''chain matrix multiplication'') — классическая задача, которая может быть решена с помощью динамического программирования. В этой задаче нам дается |definition = Дана последовательность из <tex>n</tex> матриц, в которой мы хотим требуется найти самый эффективный способ их перемножения.}}

[[Правильные скобочные последовательности | Расстановок скобок]] достаточно много и их количество очень быстро растет. Точное количество всевозможных вариантов равно ''<tex>n''</tex>–ому [http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 [Числа Каталана | числу Каталана]].

Например, предположим, что А <tex>\dim{A}= (10 &\times; 30)</tex>, <tex>\dim{B } = (30 &\times; 5)</tex>, <tex>\dim{C } = (5 &\times; 60)</tex>. Тогда:

:Для <tex> (''AB''A \times B)''\times C'' = </tex> будет <tex>(10&times;30&times;5\times30\times5) + (10&times;5&times;60\times5\times60) = 1500 + 3000 = 4500 </tex> операций:''Для <tex> A''\times(''BC''B \times C) = </tex> будет <tex>(30&times;5&times;60\times5\times60) + (10&times;30&times;60\times30\times60) = 9000 + 18000 = 27000 </tex> операций.

В данной задаче нужно узнать минимальное количество операций (или минимальную стоимость), необходимых для перемножения матриц. Если перемножить только две матрицы, то можно осуществить это едиственным способом, следовательно минимальная стоимость — это стоимость перемножения этих двух матриц. В общем, можно найти минимальную стоимость используя следующий [[Динамическое программирование | рекурсивный алгоритм]]:

* Взять взять последовательность матриц и разделить её на две части.,* Найти найти минимальную стоимость перемножения на каждой подпоследовательности.,* Сложить сложить эти две стоимости и прибавить к этому стоимость перемножения двух получившихся матриц.,* Сделать сделать это для каждой возможной позиции в последовательности, в которой она может быть разделена и взять минимум среди всех результатов.

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

Объясняется оно просто: для того, чтобы найти произведение матриц <tex>M_{i..j}</tex> при <tex>i=j </tex> не нужно ничего делать — это и есть сама матрица <tex>M_i</tex>. При нетривиальном случае мы перебираем все точки разбиения матрицы <tex>M_{i..j}</tex> на матрицы <tex>M_{i..k}</tex> и <tex>M_{k+1..j}</tex>, ищем кол-во количество операций, необходимое чтобы их получить и затем перемножаем для получения матрицы <tex>M_{i..j}</tex>.(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц <tex>M_{i..k}M_{k+1..j}</tex>). Считаем, что размеры матриц заданы в массиве <tex>p</tex> и размер матрицы <tex>M_i</tex> равен <tex>p_{i-1} \times p_i</tex>.

Чтобы привести пример, давайте вернемся к нашим матрицам. Если у нас есть четыре матрицы ''<tex>ABCD''</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>ABC'' </tex> так же требует нахождения лучшей стоимости для ''<tex>AB''</tex>. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется ''<tex>n''</tex>–ому [http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 [Числа Каталана | числу Каталана]], да плюс вычисление для каждой [[Правильные скобочные последовательности | правильной скобочной последовательности ]] ''затрат'' на перемножение (то есть <tex>O(n \cdot C_n)</tex>). <!--Так как <tex>N</tex>­-ое [[Числа Каталана | число Каталана ]] равняется <texdpi="163"> \frac{1}{n+1}{2 n \choose n} </tex> или асимптотически <texdpi="163"> \frac{4^n}{n^{3/2}\sqrt{\pi}} </tex>, а это быстро возрастающая функциия, нам бы хотелось решение, которое работает быстрее.-->

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

'''int''' dp[][] <font color="green">// dp[i][j] — ответ на отрезке [i, j)</font> '''int''' v[] <font color="green">// Массив v[] — хранит все размеры матриц по порядку // Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократно // l — включая в отрезок, r — исключая из отрезка. Изначально l =0, r =n, где n {{---}} длина последовательности</font> '''int''' matrixChainMultiplication('''int''' l, '''int''' r) '''if''' dp[l][r] = Псевдокод =-1 <font color="green">// Если значение динамики не посчитано</font> '''if''' l == r - 1 dp[l][r] = 0 <prefont color="green"> // Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю</font> '''else''' dp[l][r] = <tex>\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] == См. также ==

int dp*[][Задача о наибольшей общей подпоследовательности ];int v[];// dp[i][j] — меморизация на отрезке *[i, j)// Массив v[] — хранит все размеры матриц по порядку// Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократноint matrixChainMultiplication(int l, int r){ //l — включая Кратчайший путь в отрезок //r — исключая из отрезка if dp[lациклическом графе ][r] == -1 //Если значение динамики не посчитано if l == r - 1 dp*[l][r] = 0; //Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю else dp[lЗадача о расстановке знаков в выражении][r] = infinity; for (int i = l + 1; i < r; i++) dp[l]*[r] = min(dp[l][r]Задача о выводе в контекстно-свободной грамматике, v[lалгоритм Кока-Янгера-Касами | Aлгоритм Кока-Янгера-Касами ] * v[i] * v[r - 1] + matrixChainMultiplication(l, i) + matrixChainMultiplication(i, r)); return dp[lПравильные скобочные последовательности | Правильные скобочные последовательности ][r];}</pre>== Источники информации ==