Изменения

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

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

[[Правильные скобочные последовательности | Расстановок скобок]] достаточно много и их количество очень быстро растет. Точное количество всевозможных вариантов равно <tex>n</tex>–ому [[Числа Каталана | числу Каталана]]. Однако, порядок в котором мы расставим расставляются скобки между матрицами повлияет на количество арифметических операций, которые потребуются на вычисление ответа, или, другими словами, на ''эффективность''.

Например, предположим, что А <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> операций.

Как мы видим, первый способ гораздо эффективней. Теперь стало понятно, что нам надо найти оптимальную расстановку скобок в нашем выражении из <tex>n</tex> матриц. Как бы это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнения этого алгоритма будет расти экспоненциально от <tex>n</tex> количества матриц, так как навскидку в каждую позицию мы можем поставить открывающуюся и закрывающуюся скобку, то асимптотика будет равна ''n''­-ому [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 * C_n)</tex>. Решение данной задачи, как мы увидим — это разбить нашу задачу на подзадачи. Так же мы увидим, что с помощю решения однократного решения подзадачи и повторного использования ответа, мы сможем заметно сократить асимптотику.

== Решение задачи = Перебор всех вариантов ===

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

* Взять последовательность матриц и разделить её на две частиИли другими словами, давайте обозначим через <tex>f(i, j)</tex> минимальное количество скалярных умножений для вычисления матрицы <tex>M_{i..j}</tex>, то получаем следующее рекуррентное соотношение:<tex> f(i,j) = \left \{ * Найти минимальную стоимость перемножения на каждой подпоследовательности.\begin{array}{ll}* Сложить эти две стоимости и прибавить к этому стоимость перемножения двух получившихся матриц. 0, & i=j \\* Сделать это для каждой возможной позиции в последовательности \min\limits_{i \leqslant k < j}{(f(i,k) + f(k+1, в которой она может быть разделена и взять минимум среди всех результатовj) + p_{i-1}p_kp_j)} & i < j \end{array} \right.</tex>

НапримерОбъясняется оно просто: для того, если у нас чтобы найти произведение матриц <tex>M_{i..j}</tex> при <tex>i=j</tex> не нужно ничего делать — это и есть четыре сама матрица <tex>M_i</tex>. При нетривиальном случае мы перебираем все точки разбиения матрицы <tex>M_{i..j}</tex> на матрицы ''ABCD''<tex>M_{i..k}</tex> и <tex>M_{k+1..j}</tex>, то мы посчитаем для (''A'')(''BCD''), (''AB'')(''CD'')ищем количество операций, необходимое чтобы их получить и затем перемножаем для получения матрицы <tex>M_{i..j}</tex>.(''ABC'')(''D'')Оно будет равно кол-ву операций, делая рекурсивные вызовы потраченное на отрезках ''ABC'', ''AB'', ''CD'', и ''BCD'', чтобы найти минимальную решение подзадач + стоимостьумножения матриц <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>O(n^2ABC)(D)</tex> подотрезков, где делая рекурсивные вызовы на отрезках <tex>nABC</tex> — это количество матриц, то память занимаемая программой будет не так велика. Можно сказать<tex>AB</tex>, что с помощью этого простого трюка мы уменьшили асимптотику алгоритма (перебор) с <tex>O(n * C_n)CD</tex> до , и <tex>O(n^3)BCD</tex>, что является достаточно эффективным для реальных приложенийчтобы найти минимальную стоимость. Потом среди них выбираем лучший вариант. Так же, этот алгоритм дает не только минимальную стоимость, но и показывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом матрицы, каким дается нам минимальная стоимость.

=== Восстановление ответа ===С помощью вышеописанного алгоритма мы можем восстановить порядокОднако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех [[Правильные скобочные последовательности | скобочных последовательностей]]. Делается значительное количество ненужной работы. Например, в котором нам необходимо перемножать матрицывыше описанном алгоритме, осуществляется рекурсивный вызов, чтобы достичь минимального количества арифметических операцийнайти наилучшую стоимость для подсчета <tex>ABC</tex> и <tex>AB</tex>. Но нахождение наилучшей стоимости для подсчета <tex>ABC</tex> так же требует нахождения лучшей стоимости для <tex>AB</tex>. Так как рекурсия растет вглубь все больше и больше, затрачиваемых на вычисление ответато и число ненужных повторений увеличивается. Когда мы узнаемИтоговая асимптотика, как нам нужно разбить отрезок было сказано выше, равняется <tex>n</tex>–ому [[Числа Каталана | числу Каталана]], да плюс вычисление для каждой [[Правильные скобочные последовательности | правильной скобочной последовательности]] ''затрат'' на два подотрезка, перемножение (то при восстановлении ответа мы заключаем эти два подотрезкаесть <tex>O(последовательности матрицn \cdot C_n)</tex>) в скобки и передаем получившийся ответ выше по рекурсии. Так как <tex>N</tex>­-ое [[Числа Каталана | число Каталана]] равняется <tex dpi="163"> \frac{1}{n+1}{2 n \choose n} </tex> или асимптотически <tex dpi="163"> \frac{4^n}{n^{3/2}\sqrt{\pi}} </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 <font 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] == См. также == *[[Задача о наибольшей общей подпоследовательности ]]*[[Кратчайший путь в ациклическом графе ]]*[[Задача о расстановке знаков в выражении]]*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами | Aлгоритм Кока-Янгера-Касами ]]*[[Правильные скобочные последовательности | Правильные скобочные последовательности ]]== Источники информации == *[http://en.wikipedia.org/wiki/Matrix_chain_multiplication Wikipedia {{---}} Matrix chain multiplication]