Изменения

|definition = Дана последовательность из <tex>n</tex> матриц, в которой мы хотим требуется найти самый эффективный способ их перемножения.

:<tex>(AB)\dim{A}\times\dim{B}\times\dim{C } = (10\times30\times5) + (10\times5\times60) = 1500 + 3000 = 4500</tex> операций:<tex>\dim{A}\times(BC\dim{B}\times\dim{C}) = (30\times5\times60) + (10\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>ABC</tex> и <tex>AB</tex>. Но нахождение наилучшей стоимости для подсчета <tex>ABC</tex> так же требует нахождения лучшей стоимости для <tex>AB</tex>. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется <tex>n</tex>–ому числу Каталана, да плюс вычисление для каждой правильной скобочной последовательности ''затрат'' на перемножение (то есть <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>, что является быстро возрастающей функцией, нам бы хотелось решение, которое работает быстрее.

<code> '''int ''' dp[][]; '''int ''' v[]; <font color="green">// dp[i][j] — меморизация ответ на отрезке [i, j) // Массив v[] — хранит все размеры матриц по порядку // Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократно</font> '''int ''' matrixChainMultiplication(int l, int r) { <font color="green">//l — включая в отрезок //r — исключая из отрезка</font> '''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] = infinity; '''for ''' (int i = l + 1; i < r; i++) dp[l][r] = min(dp[l][r], v[l] * v[i] * v[r - 1] + matrixChainMultiplication(l, i) + matrixChainMultiplication(i, r)); return dp[l][r]; }</precode>

*[http://en.wikipedia.org/wiki/Matrix_chain_multiplication Wikipedia {{---}} Matrix chain multiplication]*[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 числа Каталана]