Черновик:Перемножение матриц

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

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

(ABC)D = (AB)(CD) = A(BCD) = A(BC)D = ....

Однако, порядок в котором мы расставим скобки в нашем выражении повлияет на количество арифметических операций, которые мы потратим на вычисление ответа, или, другими словами, на эффективность.

Например, предположим, что А = (10 × 30), B = (30 × 5), C = (5 × 60). Тогда:

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 операций

A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 операций.

Очевидно, что первый способ гораздо эффективней. Теперь мы поняли, что нам надо найти оптимальную расстановку скобок в нашем выражении из n матриц. Как это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнение этого алгоритма будет эксапаненциально рости от n количества матриц. Решение данной проблемы, как мы увидим — это разбить нашу задачу на подзадачи. С помощю решения подзадач по одному разу и повторного использования решения, мы сможем заметно сократить асимптотику. Эта задача входит в классические задачи

Динамическое решение

Сведение задачи к подзадачам

Обозначим результат перемножения матриц [math]A_iA_{i+1} \ldots A_j[/math] через [math]A_{i..j}[/math], где [math]i \le j[/math]. Если [math] i\lt j[/math], то при любом способе расстановки скобок, последнее выполненное умножение для вычисления [math]A_{i..j}[/math] между матрицами [math]A_k[/math] и [math]A_{k+1}, i \le k\lt j[/math], то есть чтобы вычислить [math]A_{i..j}[/math] надо сначала вычислить [math]A_{i..k}[/math], потом [math]A_{k+1..j}[/math] и затем их перемножить. Заметим, что если способ расстановки скобок оптимален, то расстановка скобок в этих матрицах должна быть оптимальной, иначе если бы существовал более эффективный способ расстановки скобок в матрицах [math]A_{i..k}[/math] и [math]A_{k+1..j}[/math], то мы могли бы получить [math]A_{i..j}[/math] за меньшее число умножений, получаем противоречие, что расстановка скобок в [math]A_{i..j}[/math] оптимальна. Таким образом мы свели задачу к подзадачам. Это означает, что возможно решить задачу, используя динамическое программирование на подотрезке.

Рекурсивное решение

Обозначим через [math]m[i, j][/math] минимальное количество скалярных умножений для вычисления матрицы [math]A_{i..j}[/math]. Получаем следующее рекуррентное соотношение: [math] m[i,j] = \left \{ \begin{array}{ll} 0, & i=j \\ min(m[i,k] + m[k+1,j] + p_{i-1}p_kp_j | i \le k \lt j) & i \lt j \end{array} \right. [/math]

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

Динамическое программирование

Будем запоминать в двумерном массиве [math]m[/math] результаты вычислений для подзадач, чтобы избежать пересчета для уже вычислявшихся подзадач. После вычислений ответ будет в [math]m[1,n][/math](Сколько перемножений требуется для последовательности матриц от [math]1[/math] до [math]n[/math] — то есть ответ на поставленную задачу).Сложность алгоритма будет [math]O(n^3)[/math], так как у нас [math]{n \choose 2}[/math] вариантов выбора [math]i, j : 1 \le i \le j \le n[/math] и [math]O(N)[/math] точек разделения для каждого варианта.

Ссылки

использованы материалы ru.wikipedia.org [1]

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ
• Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms