Задача о порядке перемножения матриц

Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц [math] A_1, A_2, ..., A_n [/math] и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов [math] A_{i - 1}[/math] совпадает с количеством строк [math] A_i [/math] матрицы).

Подробное описание задачи

Произведение матриц — ассоциативная операция. Когда матрицы велики по одному измерению и малы по другому, количество скалярных операций может серьёзно зависеть от порядка перемножений матриц. Допустим, нам даны 3 матрицы [math] A_1, A_2, A_3 [/math] размерами соответственно [math] 10 \times 100, 100 \times 5[/math] и [math]5 \times 50[/math]. Существует 2 способа их перемножения (расстановки скобок): [math]((A_1A_2)A_3)[/math] и [math](A_1(A_2A_3))[/math]. В первом случае нам потребуется [math]10\cdot100\cdot5 + 10\cdot5\cdot50 = 7500[/math] скалярных умножений, а во втором случае [math]100\cdot5\cdot50 + 10\cdot100\cdot50 = 75000[/math] умножений — разница налицо. Поэтому может оказаться выгоднее потратить некоторое время на предобработку, решив, в каком порядке лучше всего умножать, чем умножать сразу в лоб. Таким образом, даны [math]n[/math] матриц: [math]A_1: \, p_0 \times p_1[/math], [math]A_2: \, p_1 \times p_2[/math], …, [math]A_n: \, p_{n-1} \times p_{n}[/math]. Требуется определить, в каком порядке перемножать их, чтобы количество операций умножения было минимальным.

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

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

Обозначим результат перемножения матриц [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