Произведение матриц

Пусть мы хотим вычислить произведение $n$ матриц $A_{1} \times \cdots \times A_{n}$; матрица $A_{i}$ имеет размер $m_{i-1} \times m_{i}$. Сами умножения мы будем производить, пользуясь определением произведения матриц, то есть на вычисление произведения матриц размеров $m \times n$ и $n \times p$ мы потратим $O(m n p)$ действий. Однако мы вольны выбирать порядок, в котором будем производить умножения (то есть расставлять скобки в выражении выше). Хочется минимизировать суммарное количество действий, которые придётся сделать, чтобы вычислить произведение всех матриц.

Пусть, например, мы перемножаем матрицы размеров $100 \times 10$, $10 \times 20$ и $20 \times 2$. Если производить вычисления в порядке $\left(A_{1} \times A_{2}\right) \times A_{3}$, то понадобится совершить $100 \cdot 10 \cdot 20+100 \cdot 20 \cdot 2=24000$ действий; если же использовать порядок $A_{1} \times\left(A_{2} \times A_{3}\right)$, понадобится всего $10 \cdot 20 \cdot 2+100 \cdot 10 \cdot 2=2400$ действий.

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

Как решить эту задачу методом динамического программирования? Попробуем свести задачу к подзадачам попроще. Посмотрим на последнюю операцию умножения, которую мы проведём: мы перемножим матрицы $A_{1} \times \cdots \times A_{j}$ и $A_{j+1} \times \cdots \times A_{n}$ для некоторого $j$. Операции, которые мы сделали до этого, соответствуют оптимальному вычислению этих двух матриц: получились две независимых подзадачи.

Таким образом, состояния на этот раз соотвествуют не только префиксам (как во многих рассмотренных ранее задачах), но и суффиксам последовательности, соответствующей текущей задаче. Если же мы попытаемся свести задачу для префикса или суффикса к подзадачам попроще, то нам понадобится решать подзадачи уже для подотрезков последовательности, соответствующей исходной задаче.

Итак, на этот раз состояния соответствуют подотрезкам исходной задачи. Пусть $c[l, r]$ минимальное количество операций, необходимое для вычисления $A_{l} \times \cdots \times A_{r}$. Начальные состояния: $c[i, i]=0$. Для того, чтобы выписать переходы, переберём, какую пару матриц мы будем умножать в самом конце:

Один из порядков, соответствующий топологической сортировке на графе состояний — рассматривать состояния в порядке увеличения длины подотрезка.

Получилось решение с временем работы $O\left(n^{3}\right)$, использующее $O\left(n^{2}\right)$ дополнительной памяти. Восстановление ответа делается стандартными методами.

✍️ Эту задачу умеют решать за $O(n \log n)$ (Hu, Shing, 1984).

1
2
3
4
5
6
7
8
9

fill(c, inf)
for i = 1..n:
    c[i, i] = 0
for s = 1..n:
    for l = 1..(n - s):
        r = l + s # подзадача [l, r]
        for i = l..(r - 1):
            c[l, r] = min(c[l, r],
                c[l, i] + c[i + 1,r] + m[l - 1] * m[i] * m[r])