Matrix Chain Multiplication

Q: Какова временная сложность умножения цепочки матриц?

Таблица содержит около n²/2 фрагментов, и для каждого проверяется до n разбиений, поэтому динамическое программирование выполняется за время O(n³) и использует O(n²) памяти. Обычная рекурсия без мемоизации выполняет 3^(n-1) вызовов для n матриц.

Q: Почему важен порядок умножения матриц?

Умножение матриц ассоциативно, поэтому (AB)C и A(BC) дают одну и ту же матрицу, но промежуточные матрицы различаются по размеру. В первом примере (AB)C строит матрицу размером 4 × 3 и требует 264 операций, а A(BC) строит матрицу размером 10 × 12 и требует 840 операций.

Q: Как найти оптимальную расстановку скобок?

Сохраняй выигрышное разбиение в choice[left][right] рядом с best[left][right] . Для вывода одну матрицу печатай по её имени; для более длинного участка печатай открывающую скобку, часть до choice[left][right] , часть после неё и закрывающую скобку. Это требует O(n²) памяти.

СложноДинамическое программирование

+10

Цепочка матриц задаётся массивом dims: матрица i имеет dims[i] строк и dims[i+1] столбцов, поэтому каждая матрица подходит к следующей. Умножение матрицы размера p × q на матрицу размера q × r требует p × q × r скалярных умножений и даёт матрицу размера p × r. Любой способ расставить скобки даёт одно и то же итоговое произведение, но затраты при этом различаются. Верните минимальное число скалярных умножений, необходимое для перемножения всей цепочки.

Функция

matrixChainOrder(dims: integer-array) → integer

dimsinteger-array: размеры вдоль цепочки: матрица i имеет размеры dims[i] × dims[i+1]
Возвращаетinteger: минимальное количество скалярных умножений для перемножения всей цепочки

Ограничения

2 ≤ dims.length ≤ 100, поэтому цепочка содержит от 1 до 99 матриц.
1 ≤ dims[i] ≤ 100
Ответ не превышает 98 × 10⁶, что значительно меньше максимального значения 32-разрядного знакового целого числа.

Примеры

Ввод: dims = [4, 10, 3, 12]
Вывод: 264
Пояснение: При умножении первых двух матриц получается 4 × 10 × 3 = 120, и остается матрица 4 × 3, умножение которой на матрицу 3 × 12 добавляет 144: итого 264. При другом порядке вычисления стоят 360 + 480 = 840.

Дополнительный вопрос

Можешь также посчитать, сколько различных способов расстановки скобок дают минимальную стоимость?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Порядок меняет стоимость: 264 против 840 в первом примере. Посмотри на последнее умножение. Оно объединяет произведения левой и правой частей цепочки, и каждая часть представляет собой ту же задачу для более короткой цепочки. Таблица для отрезков цепочки решает каждую такую задачу один раз за время O(n³).

Попробуйте все разбиения с помощью обычной рекурсии

Верно, но не успевает на самых больших тестах

Идея

Пронумеруем границы цепочки от 0 до m-1, где m = dims.length: граница k имеет размер dims[k]. Матрицы между границами left и right при перемножении в любом порядке дают матрицу размера dims[left] × dims[right]. Поэтому, если на последнем шаге этот отрезок разделяется в точке split, этот шаг стоит dims[left] × dims[split] × dims[right], независимо от того, что происходило внутри двух блоков. Каждый блок нужно построить с наименьшей возможной стоимостью, поэтому cheapest(left, right) — это наименьшая сумма стоимостей обоих блоков и этого последнего шага для всех возможных значений split. Перебор каждого варианта последнего шага гарантирует правильность решения.

Одни и те же отрезки решаются снова и снова: для n матриц требуется 3^(n-1) вызовов — около 1.2 × 10^9 для 20 матриц, хотя существует всего около m²/2 различных отрезков.

Алгоритм

Напишите cheapest(left, right) для матриц между границами left и right.
Если right - left < 2, имеется одна матрица: верните 0.
Для каждого split, строго расположенного между ними, сложите cheapest(left, split), cheapest(split, right) и dims[left] × dims[split] × dims[right].
Верните наименьшую сумму.
Ответ — cheapest(0, m-1).

def matrixChainOrder(dims):
    def cheapest(left, right):
        # The fewest multiplications for the matrices between boundaries left and right
        if right - left < 2:
            return 0  # a single matrix costs nothing
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        return best

    return cheapest(0, len(dims) - 1)

Рекурсия с мемоизацией

Идея

Вызов зависит только от left и right. Сохраняйте его результат в memo[left][right]; начальное значение каждой ячейки — -1, значение, которое не может быть реальной стоимостью, а при последующих вызовах считывайте значение из ячейки вместо рекурсивного вызова. Каждая из примерно m²/2 пар решается один раз с менее чем m разбиениями: O(n³), или 161,700 проверок разбиений для 99 матриц. Глубина рекурсии никогда не превышает длину цепочки, поэтому 100 границ поместятся в стеке вызовов любого размера.

Алгоритм

Выдели memo с m строками и m столбцами, заполнив каждую ячейку значением -1.
В cheapest(left, right) для отрезка из одной матрицы возвращается 0, а для ячейки, отличной от -1, возвращается сохранённая стоимость.
В противном случае вычисли стоимость каждого split точно так же, как это делает обычная рекурсия, и выбери минимум.
Запиши этот минимум в memo[left][right] перед возвратом.
Ответ — cheapest(0, m-1).

def matrixChainOrder(dims):
    m = len(dims)
    # memo[left][right]: the answer for boundaries left and right, -1 while unknown
    memo = [[-1] * m for _ in range(m)]

    def cheapest(left, right):
        if right - left < 2:
            return 0  # a single matrix costs nothing
        if memo[left][right] != -1:
            return memo[left][right]
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        memo[left][right] = best
        return best

    return cheapest(0, m - 1)

Заполните таблицу, растянув её по ширине

Идея

Каждая ячейка зависит только от более узких отрезков, поэтому циклы могут заполнять best[left][right] от узких отрезков к широким. Ширина 1 — это одна матрица, и её значение остаётся равным 0; когда вы доходите до более широкого отрезка, обе части каждого разбиения уже вычислены. При dims = [6, 2, 7, 3, 5]:

Ширина 2: best[0][2] = 84, best[1][3] = 42, best[2][4] = 105.
Ширина 3: best[0][3] равно 78 (разбиение 1: 0 + 42 + 36), best[1][4] равно 72 (разбиение 3: 42 + 0 + 30).
Ширина 4: разбиения 1, 2 и 3 дают 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 и 78 + 0 + 90 = 168, поэтому best[0][4] = 132.

Верхнее разбиение на границе 1 означает, что матрица 6 × 2 присоединяется последней, как во втором примере. Время выполнения и объём памяти такие же, как у версии с мемоизацией, при этом рекурсия не используется.

Алгоритм

Пусть m = dims.length, и выдели таблицу m × m best, заполненную нулями.
Перебирай width от 2 до m-1. Внутри перебирай left по возрастанию от 0, пока right = left + width остаётся в границах.
Для этого отрезка вычисли best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right] для каждого split от left+1 до right-1 и сохрани минимум в best[left][right].
Ответ находится в best[0][m-1].

def matrixChainOrder(dims):
    m = len(dims)
    # best[left][right]: the fewest multiplications for the matrices
    # between boundary left and boundary right (0 for a single matrix)
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            low = None
            for split in range(left + 1, right):
                # the last product joins a dims[left] x dims[split] block
                # with a dims[split] x dims[right] block
                cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
                if low is None or cost < low:
                    low = cost
            best[left][right] = low
    return best[0][m - 1]

Ловушки и крайние случаи

Сначала перемножать самую дешёвую пару. Для [10, 10, 1, 9] последняя пара самая дешёвая (90), но следующий шаг стоит 900, итого 990. Если сначала взять первую пару, стоимость будет 190.
Читать ответ не из той ячейки. В dims на один элемент больше, чем матриц, поэтому ответ — best[0][m-1], а не best[0][m].
Перебирать left по возрастанию во внешнем цикле. Тогда строка left читает best[split][right] из более поздней строки, в которой пока ещё 0. Поместите ширину во внешний цикл или перебирайте left в обратном порядке.
Не учитывать случай с одной матрицей. Для [3, 7] должно возвращаться 0, а в R цикл 2:(m-1) превращается в 2:1 и выполняется в обратном направлении, поэтому добавьте проверку.

Частые вопросы3

Какова временная сложность умножения цепочки матриц?

Таблица содержит около n²/2 фрагментов, и для каждого проверяется до n разбиений, поэтому динамическое программирование выполняется за время O(n³) и использует O(n²) памяти. Обычная рекурсия без мемоизации выполняет 3^(n-1) вызовов для n матриц.

Почему важен порядок умножения матриц?

Умножение матриц ассоциативно, поэтому (AB)C и A(BC) дают одну и ту же матрицу, но промежуточные матрицы различаются по размеру. В первом примере (AB)C строит матрицу размером 4 × 3 и требует 264 операций, а A(BC) строит матрицу размером 10 × 12 и требует 840 операций.

Как найти оптимальную расстановку скобок?

Сохраняй выигрышное разбиение в choice[left][right] рядом с best[left][right]. Для вывода одну матрицу печатай по её имени; для более длинного участка печатай открывающую скобку, часть до choice[left][right], часть после неё и закрывающую скобку. Это требует O(n²) памяти.

def matrixChainOrder(dims):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

dims = [4, 10, 3, 12]

Ожидаемый вывод

Matrix Chain Multiplication

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуйте все разбиения с помощью обычной рекурсии

Рекурсия с мемоизацией

Заполните таблицу, растянув её по ширине

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи