Перемножение нескольких матриц

Пусть мы хотим найти произведение последовательности матриц

А₁*А₂*…*А_n. (*)

Будем пользоваться стандартным алгоритмом перемножения двух матриц в качестве подпрограммы. Но прежде надо расставить скобки в (*), чтобы указать порядок умножений. Будем говорить, что в произведении матриц полностью расставлены скобки, если это произведение либо состоит из одной единственной матрицы, либо является заключенным в скобки произведением двух произведений с полностью расставленными скобками. Поскольку умножение матриц ассоциативно, конечный результат вычислений не зависит от расстановки скобок. Например, в произведении А₁*А₂*А₃*А₄ можно полностью расставить скобки пятью разными способами:

(А₁*(А₂*(А₃*А₄)))

((А₁*А₂)*(А₃*А₄))

((А₁*(А₂*А₃))*А₄)

(((А₁*А₂)*А₃)*А₄)

(А₁*((А₂*А₃)*А₄))

во всех случаях ответ будет один и тот же.

Не влияя на ответ, способ расстановки скобок может сильно повлиять на стоимость перемножения матриц.

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

typedef struct

{

int **matr;

int rows;

int columns;

} MATRIX;

// выделение памяти под матрицы a, b, c и заполнение матриц a, b

void MatrixMultiply(MATRIX a, MATRIX b, MATRIX c)

{

int i, j, k;

if (a.columns != b.rows)

{ //умножить нельзя, обработка ошибки

}

else

for(i=0;i<a.rows;i++)

for(j=0;j<b.columns;j++)

{

c.matr[i][j]=0;

for(k=0;k<a.columns;k++)

c.matr[i][j]+=a.matr[i][k]*b.matr[k][j];

}

}

Матрицы а и b можно перемножать, только если число столбцов матрицы а равно числу строк матрицы b. Если а – это (pq)-матрица, а b – это (qr)-матрица, то их произведение с является (pr)-матрицей. При выполнении этого алгоритма делается pqr умножений и примерно столько же сложений. Для простоты будем учитывать только умножения.

Чтобы увидеть, как расстановка скобок может повлиять на стоимость, рассмотрим последовательность из трех матриц А₁,А₂, А₃ размеров 10100, 1005 и 550.

При вычислении ((А₁*А₂)* А₃) нужно 10*100*5 + 10*5*50=5000+2500=7500 умножений.

При вычислении (А₁*(А₂* А₃)) нужно 100*5*50 + 10*100*50=25000+50000=75000 умножений. Тем самым первый способ расстановки скобок в 10 раз выгоднее.

Задача об умножении последовательности матриц может быть сформулирована следующим образом: дана последовательность из n матриц А₁,А₂,…,А_n заданных размеров (матрица А_i имеет размер p_i-1p_i); требуется найти такую полную расстановку скобок в произведении А₁*А₂*…*А_n, чтобы вычисление произведения требовало наименьшего числа умножений.

Очевидно, что число расстановок скобок экспоненциально зависит от n, так что полный перебор неэффективен.

Построим алгоритм, основанный на динамическом программировании.

Шаг 1: строение оптимальной расстановки скобок

Обозначим для удобства через А_i…j матрицу, являющуюся произведением А_i*А_i+1*…*А_j.

Оптимальная расстановка скобок в произведении А₁*А₂*…*А_n разрывает последовательность между А_k и А_k+1 для некоторого k, удовлетворяющего неравенству 1  k < n. То есть, мы сначала вычисляем произведения А_1…k и А_k+1…n, а затем перемножаем их и получаем окончательный ответ А_1…n.

Следовательно, стоимость оптимальной расстановки равна стоимости вычисления матрицы А_1…k плюс стоимость вычисления матрицы А_k+1…n плюс стоимость перемножения этих двух матриц.

То же самое происходит и с двумя подпоследовательностями.

Чем меньше умножений нам потребуется для вычисления А_1…k и А_k+1…n, тем меньше будет общее число умножений. Следовательно, оптимальное решение задачи содержит оптимальные решения её подзадач, что позволяет применить метод динамического программирования.