Изменения
Опечатка
\begin{array}{ll}
0, & i=j \\
\min\limits_{i \leqslant k < j}{(f(m[i,k] ) + m[f(k+1,j] ) + p_{i-1}p_kp_j | i <= k < j) } & i < j
\end{array}
\right.
</tex>
Объясняется оно просто: для того, чтобы найти произведение матриц <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 n} </tex> или асимптотически <tex dpi="163"> \frac{4^n}{n^{3/2}\sqrt{\pi}}</tex> вариантов выбора , а это быстро возрастающая функция, нам бы хотелось решение, которое работает быстрее. === Псевдокод === '''int''' dp[][] <texfont 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= i "green">// Если значение динамики не посчитано</font> '''if''' l == r - 1 dp[l][r] = j 0 <font color= n"green"> // Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю</font> '''else''' dp[l][r] = <tex> и \infty</tex>O '''for''' i = l + 1 '''to''' r - 1 dp[l][r] = min(dp[l][r], v[l] * v[i] * v[r] + matrixChainMultiplication(l, i) + matrixChainMultiplication(Ni, r))< '''return''' dp[l][r] == См. также == *[[Задача о наибольшей общей подпоследовательности ]]*[[Кратчайший путь в ациклическом графе ]]*[[Задача о расстановке знаков в выражении]]*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами | Aлгоритм Кока-Янгера-Касами ]]*[[Правильные скобочные последовательности | Правильные скобочные последовательности ]]== Источники информации == *[http://tex> точек разделения для каждого вариантаen.wikipedia.org/wiki/Matrix_chain_multiplication Wikipedia {{---}} Matrix chain multiplication]