Перемножение цепочки матриц: оптимальная расстановка скобок за O(n³)

Задача о цепочке матриц (Matrix Chain Multiplication): почему порядок умножения меняет стоимость в разы, где ломаются жадные идеи, таблица ДП по шагам, восстановление скобок и связь с триангуляцией.

12 мин чтенияалгоритмы · динамическое программирование · python

Коротко

ПараметрЗначение
Входмассив размеров dims длины n + 1: матрица AiA_i — dims[i-1] × dims[i]
Выходминимум скалярных умножений и расстановка скобок
Состояниеcost[i][j] — минимальная стоимость произведения Ai…AjA_i \dots A_j
Переходперебор последнего умножения k: cost[i][k] + cost[k+1][j] + dims[i]·dims[k+1]·dims[j+1]
СложностьO(n3)O(n^3) по времени, O(n2)O(n^2) по памяти

Главная идея: у любой расстановки скобок есть последнее умножение. Оно делит цепочку на две независимые половины, и каждую из них выгодно посчитать оптимально. Это классическая динамика по отрезкам; общий шаблон и родственные задачи (Burst Balloons, разрезание палки, слияние камней) разобраны в статье про ДП по отрезкам. Здесь — только цепочка матриц, но подробно: откуда берётся экспонента, почему не работает жадность, как заполняется таблица и где задача встречается в реальном коде.

Постановка и почему она вообще интересна

Умножение матрицы p × q на матрицу q × r стандартным алгоритмом требует p⋅q⋅rp \cdot q \cdot r скалярных умножений и даёт матрицу p × r. Умножение ассоциативно: (AB)C=A(BC)(AB)C = A(BC), результат одинаковый. А вот стоимость — нет.

Возьмём три матрицы: AA размером 1000×10, BB — 10×1000, CC — 1000×5.

  • (AB)C(AB)C: сначала 1000⋅10⋅1000=1071000 \cdot 10 \cdot 1000 = 10^7, получаем огромную 1000×1000, потом ещё 1000⋅1000⋅5=5⋅1061000 \cdot 1000 \cdot 5 = 5 \cdot 10^6. Итого 1,5⋅1071{,}5 \cdot 10^7.
  • A(BC)A(BC): 10⋅1000⋅5=5⋅10410 \cdot 1000 \cdot 5 = 5 \cdot 10^4, получаем 10×5, потом 1000⋅10⋅5=5⋅1041000 \cdot 10 \cdot 5 = 5 \cdot 10^4. Итого 10510^5.

Разница в 150 раз, и это всего три матрицы. Причём второй вариант ещё и не создаёт промежуточную матрицу на миллион элементов.

Это не учебная абстракция. В NumPy есть np.linalg.multi_dot, которая выбирает порядок умножения как раз этой динамикой (внутри функция _multi_dot_matrix_chain_order). Оператор @ так не умеет: A @ B @ C всегда считается слева направо.

import numpy as np from timeit import timeit A = np.random.rand(1000, 10) B = np.random.rand(10, 1000) C = np.random.rand(1000, 5) naive = timeit(lambda: A @ B @ C, number=20) # (A B) C smart = timeit(lambda: np.linalg.multi_dot([A, B, C]), number=20) # A (B C) print(f'{naive / smart:.0f}x') # на моей машине около 75x print(np.allclose(A @ B @ C, np.linalg.multi_dot([A, B, C]))) # True

Тот же вопрос решают оптимизаторы запросов в базах данных (порядок соединения таблиц), einsum с параметром optimize и автоматическое дифференцирование: прямой и обратный режим — это два крайних порядка умножения цепочки якобианов.

Сколько всего вариантов

Почему бы просто не перебрать все расстановки скобок? Потому что их число для n матриц — это число Каталана Cn−1C_{n-1}:

Матриц23456811
Вариантов125144242916 796

Растёт это примерно как 4n/n1.54^n / n^{1.5}. Для 20 матриц вариантов уже больше миллиарда. Откуда Каталан и где ещё всплывают эти числа — в статье про числа Каталана.

Жадность не работает

На собеседовании первым часто предлагают жадный алгоритм. Две самые популярные идеи — и обе ломаются.

«Сначала самое дешёвое умножение соседей». Для dims = [40, 20, 30, 10, 30] (четыре матрицы: 40×20, 20×30, 30×10, 10×30) самая дешёвая пара — A3A4A_3 A_4 за 30⋅10⋅30=900030 \cdot 10 \cdot 30 = 9000. Жадный алгоритм в итоге набирает 36 000. Оптимум — 26 000: ((A1(A2A3))A4)((A_1 (A_2 A_3)) A_4).

«Сначала избавиться от самой большой внутренней размерности». Для dims = [1, 2, 3, 4] самая большая внутренняя размерность — 3, жадность умножает A2A3A_2 A_3 за 2⋅3⋅4=242 \cdot 3 \cdot 4 = 24 и получает итог 32. Оптимум — (A1A2)A3(A_1 A_2) A_3 за 6+12=186 + 12 = 18.

Проблема в том, что решение в одном месте цепочки меняет размеры, с которыми работают все последующие умножения. Локально выгодный шаг может испортить глобальную картину — классический признак того, что нужна динамика, а не жадный алгоритм.

Оптимальная подструктура

Пусть в оптимальной расстановке для Ai…AjA_i \dots A_j последнее умножение стоит между AkA_k и Ak+1A_{k+1}:

(Ai…Ak)⋅(Ak+1…Aj)(A_i \dots A_k) \cdot (A_{k+1} \dots A_j)

Левая скобка даёт матрицу dims[i-1] × dims[k], правая — dims[k] × dims[j], и последнее умножение стоит di−1⋅dk⋅djd_{i-1} \cdot d_k \cdot d_j. Эта стоимость не зависит от того, как расставлены скобки внутри половин. Значит, каждую половину выгодно посчитать оптимально: если бы внутри левой части был способ дешевле, его можно было бы подставить и улучшить общий ответ. Это и есть оптимальная подструктура.

Получаем рекуррентность (индексы матриц с единицы):

m[i][j]={0,i=jmin⁡i≤k<j(m[i][k]+m[k+1][j]+di−1dkdj),i<jm[i][j] = \begin{cases} 0, & i = j \\ \min\limits_{i \le k < j} \big( m[i][k] + m[k+1][j] + d_{i-1} d_k d_j \big), & i < j \end{cases}

Различных пар (i, j) всего n(n+1)/2n(n+1)/2, а наивная рекурсия пересчитывает их экспоненциально много раз. Запоминаем — и задача решена. Как перейти от рекурсии к кэшу, разобрано в статье про мемоизацию; ниже сразу итеративная версия.

Итеративное решение

m[i][j] зависит от более коротких отрезков, поэтому заполняем таблицу по возрастанию длины цепочки. В коде индексы с нуля: матрица i имеет размер dims[i] × dims[i+1].

def matrix_chain(dims: list[int]) -> tuple[list[list[int]], list[list[int]]]: n = len(dims) - 1 # число матриц cost = [[0] * n for _ in range(n)] split = [[0] * n for _ in range(n)] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 cost[i][j] = float('inf') for k in range(i, j): c = ( cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1] ) if c < cost[i][j]: cost[i][j] = c split[i][j] = k return cost, split def parenthesize(split: list[list[int]], i: int, j: int) -> str: if i == j: return f'A{i + 1}' k = split[i][j] return f'({parenthesize(split, i, k)} {parenthesize(split, k + 1, j)})' dims = [40, 20, 30, 10, 30] cost, split = matrix_chain(dims) print(cost[0][-1]) # 26000 print(parenthesize(split, 0, len(dims) - 2)) # ((A1 (A2 A3)) A4)

Таблица split хранит, где был оптимальный разрез. Без неё ответ «26 000» есть, а самой расстановки нет — интервьюер почти наверняка попросит её вывести.

Разбор таблицы на примере

Возьмём тот же пример: A1A_1 — 40×20, A2A_2 — 20×30, A3A_3 — 30×10, A4A_4 — 10×30.

Длина 1. Одна матрица ничего не стоит: диагональ нулевая.

Длина 2. Вариант один, просто считаем:

  • A1A2A_1 A_2: 40⋅20⋅30=24 00040 \cdot 20 \cdot 30 = 24\,000;
  • A2A3A_2 A_3: 20⋅30⋅10=600020 \cdot 30 \cdot 10 = 6000;
  • A3A4A_3 A_4: 30⋅10⋅30=900030 \cdot 10 \cdot 30 = 9000.

Длина 3. Уже есть выбор.

  • A1A2A3A_1 A_2 A_3: разрез после A1A_1 — 0+6000+40⋅20⋅10=14 0000 + 6000 + 40 \cdot 20 \cdot 10 = 14\,000; разрез после A2A_2 — 24 000+0+40⋅30⋅10=36 00024\,000 + 0 + 40 \cdot 30 \cdot 10 = 36\,000. Берём 14 000.
  • A2A3A4A_2 A_3 A_4: после A2A_2 — 0+9000+20⋅30⋅30=27 0000 + 9000 + 20 \cdot 30 \cdot 30 = 27\,000; после A3A_3 — 6000+0+20⋅10⋅30=12 0006000 + 0 + 20 \cdot 10 \cdot 30 = 12\,000. Берём 12 000.

Длина 4. Три варианта последнего умножения:

  • после A1A_1: 0+12 000+40⋅20⋅30=36 0000 + 12\,000 + 40 \cdot 20 \cdot 30 = 36\,000;
  • после A2A_2: 24 000+9000+40⋅30⋅30=69 00024\,000 + 9000 + 40 \cdot 30 \cdot 30 = 69\,000;
  • после A3A_3: 14 000+0+40⋅10⋅30=26 00014\,000 + 0 + 40 \cdot 10 \cdot 30 = 26\,000.

Итоговая таблица cost (строка — начало, столбец — конец):

A1A_1A2A_2A3A_3A4A_4
A1A_1024 00014 00026 000
A2A_20600012 000
A3A_309000
A4A_40

Заполняется она диагоналями: сначала главная, потом соседняя, и так до правого верхнего угла. Восстановление идёт сверху вниз: split[0][3] = 2 (разрез после A3A_3), затем split[0][2] = 0 (после A1A_1) — получаем ((A1(A2A3))A4)((A_1 (A_2 A_3)) A_4).

Сложность

Три вложенных цикла: длина, начало, точка разреза. Точное число итераций внутреннего цикла — ∑len(n−len+1)(len−1)=(n3−n)/6\sum_{len} (n - len + 1)(len - 1) = (n^3 - n)/6, то есть O(n3)O(n^3) с маленькой константой. Для n = 500 это около 20 миллионов операций: в C++ мгновенно, в чистом Python — несколько секунд.

Память — две таблицы n×nn \times n, O(n2)O(n^2). Сэкономить её, как в одномерных задачах, не получится: ячейке нужны все отрезки внутри неё, а не только соседняя строка.

Для любопытных: существует алгоритм Ху и Шинга (Hu, Shing, 1980-е), который решает задачу за O(nlog⁡n)O(n \log n) через триангуляцию многоугольника. Он сложный, и на собеседованиях его не спрашивают; достаточно знать, что он есть.

Та же задача на JavaScript

function matrixChainOrder(dims) { const n = dims.length - 1 const cost = Array.from({ length: n }, () => new Array(n).fill(0)) const split = Array.from({ length: n }, () => new Array(n).fill(0)) for (let len = 2; len <= n; len++) { for (let i = 0; i + len - 1 < n; i++) { const j = i + len - 1 cost[i][j] = Infinity for (let k = i; k < j; k++) { const c = cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1] if (c < cost[i][j]) { cost[i][j] = c split[i][j] = k } } } } const build = (i, j) => i === j ? `A${i + 1}` : `(${build(i, split[i][j])} ${build(split[i][j] + 1, j)})` return { cost: cost[0][n - 1], order: build(0, n - 1) } } console.log(matrixChainOrder([40, 20, 30, 10, 30])) // { cost: 26000, order: '((A1 (A2 A3)) A4)' }

Связь с триангуляцией многоугольника

На LeetCode отдельной задачи «Matrix Chain Multiplication» нет, зато есть её двойник — 1039. Minimum Score Triangulation of Polygon. Дан выпуклый многоугольник с весами вершин, его нужно разрезать на треугольники; вес треугольника — произведение весов вершин, минимизировать сумму.

Фиксируем сторону (i, j). В любой триангуляции она входит ровно в один треугольник, третья вершина k лежит между ними. Треугольник делит многоугольник на две независимые части:

def min_score_triangulation(values: list[int]) -> int: n = len(values) dp = [[0] * n for _ in range(n)] for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = min( dp[i][k] + dp[k][j] + values[i] * values[k] * values[j] for k in range(i + 1, j) ) return dp[0][n - 1] print(min_score_triangulation([3, 7, 4, 5])) # 144 print(min_score_triangulation([1, 3, 1, 4, 1, 5])) # 13

Это та же задача: если подать в триангуляцию массив dims, ответ совпадёт с ответом для цепочки матриц (я проверил на сотнях случайных массивов). Многоугольник с n + 1 вершинами соответствует цепочке из n матриц, сторона (di−1,dj)(d_{i-1}, d_j) — подцепочке Ai…AjA_i \dots A_j, а треугольник di−1dkdjd_{i-1} d_k d_j — последнему умножению. Именно на этом соответствии построен алгоритм Ху–Шинга.

Отличие только в индексах: в триангуляции у отрезков общая граница k, поэтому переход dp[i][k] + dp[k][j], а не dp[k+1][j].

Типичные ошибки

  • Путаница в размерах. Матрица i (с нуля) — это dims[i] × dims[i+1]. Стоимость последнего умножения — dims[i] * dims[k + 1] * dims[j + 1]. Самый частый баг — dims[k] вместо dims[k + 1]. Проверяйте на [10, 30, 5, 60]: ответ должен быть 4500.
  • Неверный порядок обхода. Если идти for i in range(n): for j in range(i, n), то cost[k + 1][j] ещё не посчитан. Нужен обход по длине или i от конца к началу.
  • Инициализация нулём. Если перед поиском минимума не поставить inf, минимум всегда будет 0.
  • n — это число матриц, а не длина dims. Матриц на одну меньше.
  • Восстановление без split. Пытаться восстановить скобки по одной таблице cost можно (перебрать k и найти, где достигается равенство), но это лишняя работа и лишний шанс ошибиться.

Как это выглядит на собеседовании

Задачу дают как в чистом виде («расставьте скобки оптимально»), так и в замаскированном: триангуляция, оптимальное бинарное дерево поиска, Boolean Parenthesization (сколькими способами расставить скобки в выражении T|F&T^F, чтобы получить True). Последняя — тоже перебор последнего оператора, только вместо минимума — подсчёт.

Хороший ответ строится так:

  1. Пример на трёх матрицах, показывающий, что порядок важен.
  2. Число вариантов — Каталан, перебор не годится; жадность ломается на контрпримере.
  3. Наблюдение про последнее умножение и рекуррентность.
  4. Мемоизация или таблица по длинам, O(n3)O(n^3) и O(n2)O(n^2).
  5. Восстановление скобок через split.

Если после этого интервьюер спросит «а где ещё такое бывает», вспомните multi_dot в NumPy и порядок JOIN в базах данных. Чтобы закрепить шаблон, разберите задачи из статьи про ДП по отрезкам и наибольшую палиндромную подпоследовательность.

Потренироваться в спокойной обстановке

Все задачи