Перемножение цепочки матриц: оптимальная расстановка скобок за O(n³)
Задача о цепочке матриц (Matrix Chain Multiplication): почему порядок умножения меняет стоимость в разы, где ломаются жадные идеи, таблица ДП по шагам, восстановление скобок и связь с триангуляцией.
Коротко
| Параметр | Значение |
|---|---|
| Вход | массив размеров dims длины n + 1: матрица — dims[i-1] × dims[i] |
| Выход | минимум скалярных умножений и расстановка скобок |
| Состояние | cost[i][j] — минимальная стоимость произведения |
| Переход | перебор последнего умножения k: cost[i][k] + cost[k+1][j] + dims[i]·dims[k+1]·dims[j+1] |
| Сложность | по времени, по памяти |
Главная идея: у любой расстановки скобок есть последнее умножение. Оно делит цепочку на две независимые половины, и каждую из них выгодно посчитать оптимально. Это классическая динамика по отрезкам; общий шаблон и родственные задачи (Burst Balloons, разрезание палки, слияние камней) разобраны в статье про ДП по отрезкам. Здесь — только цепочка матриц, но подробно: откуда берётся экспонента, почему не работает жадность, как заполняется таблица и где задача встречается в реальном коде.
Постановка и почему она вообще интересна
Умножение матрицы p × q на матрицу q × r стандартным алгоритмом требует скалярных умножений и даёт матрицу p × r. Умножение ассоциативно: , результат одинаковый. А вот стоимость — нет.
Возьмём три матрицы: размером 1000×10, — 10×1000, — 1000×5.
- : сначала , получаем огромную 1000×1000, потом ещё . Итого .
- : , получаем 10×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 матриц — это число Каталана :
| Матриц | 2 | 3 | 4 | 5 | 6 | 8 | 11 |
|---|---|---|---|---|---|---|---|
| Вариантов | 1 | 2 | 5 | 14 | 42 | 429 | 16 796 |
Растёт это примерно как . Для 20 матриц вариантов уже больше миллиарда. Откуда Каталан и где ещё всплывают эти числа — в статье про числа Каталана.
Жадность не работает
На собеседовании первым часто предлагают жадный алгоритм. Две самые популярные идеи — и обе ломаются.
«Сначала самое дешёвое умножение соседей». Для dims = [40, 20, 30, 10, 30] (четыре матрицы: 40×20, 20×30, 30×10, 10×30) самая дешёвая пара — за . Жадный алгоритм в итоге набирает 36 000. Оптимум — 26 000: .
«Сначала избавиться от самой большой внутренней размерности». Для dims = [1, 2, 3, 4] самая большая внутренняя размерность — 3, жадность умножает за и получает итог 32. Оптимум — за .
Проблема в том, что решение в одном месте цепочки меняет размеры, с которыми работают все последующие умножения. Локально выгодный шаг может испортить глобальную картину — классический признак того, что нужна динамика, а не жадный алгоритм.
Оптимальная подструктура
Пусть в оптимальной расстановке для последнее умножение стоит между и :
Левая скобка даёт матрицу dims[i-1] × dims[k], правая — dims[k] × dims[j], и последнее умножение стоит . Эта стоимость не зависит от того, как расставлены скобки внутри половин. Значит, каждую половину выгодно посчитать оптимально: если бы внутри левой части был способ дешевле, его можно было бы подставить и улучшить общий ответ. Это и есть оптимальная подструктура.
Получаем рекуррентность (индексы матриц с единицы):
Различных пар (i, j) всего , а наивная рекурсия пересчитывает их экспоненциально много раз. Запоминаем — и задача решена. Как перейти от рекурсии к кэшу, разобрано в статье про мемоизацию; ниже сразу итеративная версия.
Итеративное решение
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» есть, а самой расстановки нет — интервьюер почти наверняка попросит её вывести.
Разбор таблицы на примере
Возьмём тот же пример: — 40×20, — 20×30, — 30×10, — 10×30.
Длина 1. Одна матрица ничего не стоит: диагональ нулевая.
Длина 2. Вариант один, просто считаем:
- : ;
- : ;
- : .
Длина 3. Уже есть выбор.
- : разрез после — ; разрез после — . Берём 14 000.
- : после — ; после — . Берём 12 000.
Длина 4. Три варианта последнего умножения:
- после : ;
- после : ;
- после : .
Итоговая таблица cost (строка — начало, столбец — конец):
| 0 | 24 000 | 14 000 | 26 000 | |
| 0 | 6000 | 12 000 | ||
| 0 | 9000 | |||
| 0 |
Заполняется она диагоналями: сначала главная, потом соседняя, и так до правого верхнего угла. Восстановление идёт сверху вниз: split[0][3] = 2 (разрез после ), затем split[0][2] = 0 (после ) — получаем .
Сложность
Три вложенных цикла: длина, начало, точка разреза. Точное число итераций внутреннего цикла — , то есть с маленькой константой. Для n = 500 это около 20 миллионов операций: в C++ мгновенно, в чистом Python — несколько секунд.
Память — две таблицы , . Сэкономить её, как в одномерных задачах, не получится: ячейке нужны все отрезки внутри неё, а не только соседняя строка.
Для любопытных: существует алгоритм Ху и Шинга (Hu, Shing, 1980-е), который решает задачу за через триангуляцию многоугольника. Он сложный, и на собеседованиях его не спрашивают; достаточно знать, что он есть.
Та же задача на 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 матриц, сторона — подцепочке , а треугольник — последнему умножению. Именно на этом соответствии построен алгоритм Ху–Шинга.
Отличие только в индексах: в триангуляции у отрезков общая граница 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). Последняя — тоже перебор последнего оператора, только вместо минимума — подсчёт.
Хороший ответ строится так:
- Пример на трёх матрицах, показывающий, что порядок важен.
- Число вариантов — Каталан, перебор не годится; жадность ломается на контрпримере.
- Наблюдение про последнее умножение и рекуррентность.
- Мемоизация или таблица по длинам, и .
- Восстановление скобок через
split.
Если после этого интервьюер спросит «а где ещё такое бывает», вспомните multi_dot в NumPy и порядок JOIN в базах данных. Чтобы закрепить шаблон, разберите задачи из статьи про ДП по отрезкам и наибольшую палиндромную подпоследовательность.