Цепочка матриц: динамика по отрезкам и где ставить скобки

Если ты умеешь записать переход динамики по отрезкам для цепочки матриц и знаешь, в каком порядке заполнять таблицу, листай до «Теперь сам».

Как думаешь, важен ли порядок умножения

Три матрицы: A1 размером 10 × 100, A2 - 100 × 5, A3 - 5 × 50. Умножение матрицы p × q на q × r даёт p × r и стоит p·q·r умножений чисел: каждый из p·r элементов ответа - сумма q произведений.

Прежде чем читать дальше, посчитай: сколько стоит (A1 · A2) · A3 и сколько A1 · (A2 · A3)? Ответ один и тот же - умножение матриц ассоциативно. А цена?

На что это похоже

Сборка мебели из готовых блоков, где цена соединения зависит от размеров соединяемых частей. Сначала свинтить две маленькие полки и потом прикрутить к шкафу - дёшево; сначала собрать громоздкую конструкцию, а потом к ней всё остальное - дорого, хотя итоговый шкаф тот же. Мастер, планирующий сборку, решает одно: какое соединение будет ПОСЛЕДНИМ. После этого обе половины - такие же задачи, только меньше.

Механизм: отрезок, последнее умножение, порядок по длине

матрица A_i имеет размер p[i−1] × p[i]
m[i][j] - наименьшая цена произведения A_i · … · A_j

база:     m[i][i] = 0          (одна матрица - ничего не умножаем)
переход:  m[i][j] = min по k от i до j−1:
              m[i][k]          левая часть A_i … A_k, p[i−1] × p[k]
            + m[k+1][j]        правая часть,          p[k] × p[j]
            + p[i−1]·p[k]·p[j] последнее умножение двух частей

порядок:  по возрастанию длины отрезка j − i - тогда обе части
          уже посчитаны
ответ:    m[1][n];  запоминаем лучшее k - по нему строятся скобки

Состояний n²/2, у каждого до n вариантов k - Θ(n³). Перебор всех расстановок - числа Каталана: 1, 2, 5, 14, 42, …, 4862 для десяти матриц, и дальше растут примерно как 4^n.

Почему подзадачи независимы: если последнее умножение - после A_k, то левая половина считается отдельно и даёт матрицу p[i−1] × p[k] при ЛЮБОЙ своей расстановке скобок. Её лучшая расстановка не зависит от правой - оптимальная подструктура.

Правило

Цепочку матриц считают динамикой по отрезкам: m[i][j] - лучшая цена произведения A_i … A_j, переход перебирает место последнего умножения k: m[i][k] + m[k+1][j] + p[i−1]·p[k]·p[j]. Отрезки заполняют по возрастанию длины, цена - Θ(n³) против экспоненциального числа расстановок. Скобки восстанавливают по запомненному лучшему k, рекурсивно.

Разбор: три матрицы и четвёртая

p = [10, 100, 5, 50]:   A1 10×100,  A2 100×5,  A3 5×50
(A1·A2)·A3 = 10·100·5 + 10·5·50     =  5000 + 2500  =  7500
A1·(A2·A3) = 100·5·50 + 10·100·50   = 25000 + 50000 = 75000

добавим A4 размером 50×1:  p = [10, 100, 5, 50, 1]
длина 2:  m[1][2] = 5000   m[2][3] = 25000   m[3][4] = 250
длина 3:  m[1][3] = min(0 + 25000 + 50000,  5000 + 0 + 2500) = 7500
          m[2][4] = min(0 + 250 + 500,  25000 + 0 + 5000)    = 750
длина 4:  m[1][4] = min( k=1:    0 + 750  + 10·100·1 = 1750,
                         k=2: 5000 + 250  + 10·5·1   = 5300,
                         k=3: 7500 + 0    + 10·50·1  = 8000 )  = 1750
скобки: A1 · (A2 · (A3 · A4))

Без A4 лучшим было «сначала A1·A2», с ней - ровно противоположное: сначала свернуть хвост до узкого столбца 5 × 1. Локального правила здесь нет: на трёх матрицах лучшим было начать с A1 · A2, а с четвёртой матрицей это умножение в оптимальный порядок не входит вовсе - решение видно только из полной таблицы.

Разбор: десять матриц и все 4862 расстановки

Программа берёт десять матриц со случайными размерами, считает цену «слева направо», лучшую цену динамикой и проверяет её перебором всех расстановок.

import random
from functools import lru_cache

rng = random.Random(24)
p = [rng.choice((5, 10, 20, 50, 100, 200, 500)) for _ in range(11)]
n = len(p) - 1                        # A_i размером p[i-1] × p[i]


def po_poryadku():                    # слева направо: ((A1 A2) A3) ...
    return sum(p[0] * p[k - 1] * p[k] for k in range(2, n + 1))


def dinamika():                       # m[i][j] - лучшая цена A_i … A_j
    m = [[0] * (n + 1) for _ in range(n + 1)]
    razrez = [[0] * (n + 1) for _ in range(n + 1)]
    for dlina in range(2, n + 1):     # по возрастанию длины отрезка
        for i in range(1, n - dlina + 2):
            j = i + dlina - 1
            m[i][j] = float("inf")
            for k in range(i, j):     # последнее умножение - после A_k
                c = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                if c < m[i][j]:
                    m[i][j], razrez[i][j] = c, k
    def skobki(i, j):
        if i == j:
            return f"A{i}"
        k = razrez[i][j]
        return f"({skobki(i, k)} {skobki(k + 1, j)})"
    return m[1][n], skobki(1, n)


@lru_cache(None)
def vse_rasstanovki(i, j):            # перебор всех скобок: цены
    if i == j:
        return [0]
    return [a + b + p[i - 1] * p[k] * p[j]
            for k in range(i, j)
            for a in vse_rasstanovki(i, k)
            for b in vse_rasstanovki(k + 1, j)]


cena, skobki = dinamika()
vse = vse_rasstanovki(1, n)
print("размеры:", p)
print("слева направо:", po_poryadku())
print("динамика:     ", cena)
print("скобки:", skobki)
print("перебор", len(vse), "расстановок: лучшая", min(vse),
      " худшая", max(vse))

размеры: [200, 50, 500, 100, 10, 10, 10, 10, 10, 200, 200]
слева направо: 23680000
динамика:      1658000
скобки: ((A1 ((A2 (A3 A4)) (A5 (A6 (A7 A8))))) (A9 A10))
перебор 4862 расстановок: лучшая 1658000  худшая 55280000

Динамика совпала с перебором. Лучший порядок в четырнадцать раз дешевле порядка «слева направо» и в тридцать три раза дешевле худшего. Обрати внимание на скобки: внутренние группы сворачивают узкие матрицы 10 × 10 раньше, чем трогать широкие 200 × 50 и 500 × 100.

Что ломается без этого

Первая ошибка - заполнять таблицу по строкам i, а не по длине отрезка: для m[1][4] нужны m[2][4] и m[1][3], а построчный порядок посчитает m[1][4] раньше m[2][4]. Вторая - забыть третье слагаемое p[i−1]·p[k]·p[j] или взять в нём не те индексы: размер левой части - p[i−1] × p[k], правой - p[k] × p[j]. Третья - пытаться решать жадно (самое дешёвое умножение первым): на многих цепочках это далеко от оптимума. Четвёртая - не запомнить k и потом не суметь выписать скобки.

Зачем это в работе

Порядок умножения матриц выбирают библиотеки линейной алгебры и компиляторы тензорных выражений: numpy.linalg.multi_dot делает ровно эту динамику, а в нейросетях и физических расчётах цепочки сворачивают так же, иначе вычисление растягивается в десятки раз. Сама схема «динамика по отрезкам» - выбрать точку последнего действия и решить половины - описывает и оптимальный порядок слияния файлов, и разбор выражения грамматикой, и триангуляцию многоугольника, и оптимальное дерево поиска из следующего урока.

Теперь сам

p = [5, 10, 3, 12]: A1 - 5 × 10, A2 - 10 × 3, A3 - 3 × 12. Какая расстановка дешевле и сколько она стоит?