dynamic-programming
Умножение матричной цепочки

Рекурсивное решение

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

Скажем, мы имеем две матрицы A ₁ и A ₂ размерности m * n и p * q . Из правил умножения матриц мы знаем, что,

1. Мы можем умножить A ₁ и A ₂ тогда и только тогда, когда n = p . Это означает, что количество столбцов A ₁ должно быть равно числу строк A ₂ .
2. Если выполняется первое условие, и мы умножим A ₁ и A ₂ , получим новую матрицу, назовем ее A ₃ размерности m * q .
3. Чтобы умножить A ₁ и A ₂ , нам нужно сделать некоторые умножители масштабирования. Общее число умножителей масштабирования, мы должны выполнить ( m * n * q ) или ( m * p * q ).
4. A ₁ * A ₂ не равно A ₂ * A ₁ .

Если у нас есть три матрицы A ₁ , A ₂ и A _3, имеющие размерность m * n , n * p и p * q соответственно, то A ₄ = A ₁ * A ₂ * A ₃ будет иметь размерность m * q . Теперь мы можем выполнить это матричное умножение двумя способами:

• Сначала умножим A ₁ и A ₂ , затем с результатом умножим A ₃ . То есть: ( A ₁ * A ₂ ) * A ₃ .
• Сначала умножим A ₂ и A ₃ , затем с результатом умножим A ₁ . То есть: A ₁ * ( A ₂ * A ₃ ).

Вы можете заметить, что порядок умножения остается неизменным, т. Е. Мы не умножаем ( A ₁ * A ₃ ) * A _2, потому что это может быть неверным. Мы только изменяем круглые скобки, чтобы умножить набор, прежде чем умножать его на оставшиеся. Как мы размещаем эти скобки, важно. Зачем? Скажем, размерность 3 матриц A ₁ , A ₂ и A ₃ составляет 10 * 100 , 100 * 5 , 5 * 50 . Затем,

1. Для ( A ₁ * A ₂ ) * A ₃ общее число умножителей масштабирования: ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 раз.
2. Для A ₁ * ( A ₂ * A ₃ ) общее число умножителей масштабирования: ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 раз.

Для второго типа число умножителей масштабирования в 10 раз больше числа 1-го типа! Поэтому, если вы можете придумать правильную ориентацию скобок, необходимую для минимизации полного умножения масштабирования, это уменьшит время и память, необходимые для матричного умножения. Именно в этом случае полезно умножение матричной цепочки. Здесь мы не будем беспокоиться о фактическом умножении матриц, мы узнаем только правильный порядок скобок, чтобы число умножения масштабирования было минимизировано. У нас будут матрицы A ₁ , A ₂ , A ₃ ........ A _n, и мы выясним минимальное количество умножителей масштабирования, необходимое для их умножения. Будем считать, что данные измерения действительны, т. Е. Удовлетворяет нашему первому требованию для матричного умножения.

Для решения этой проблемы мы будем использовать метод «разделяй и властвуй». Динамическое программирование необходимо из-за общих подзадач. Например: при n = 5 мы имеем 5 матриц A ₁ , A ₂ , A ₃ , A ₄ и A ₅ . Мы хотим узнать минимальное количество умножений, необходимое для выполнения этого матричного умножения A ₁ * A ₂ * A ₃ * A ₄ * A ₅ . Из множества способов, давайте сосредоточимся на одном: ( A ₁ * A ₂ ) * ( A ₃ * A ₄ * A ₅ ).

Для этого мы найдем A _left = A ₁ * A ₂ . _{Правило} = A ₃ * A ₄ * A ₅ . Затем мы узнаем _ответ A = A _left * A _right . Общее количество умножителей масштабирования, необходимых для определения _ответа A : = Общее количество умножителей масштабирования, необходимых для определения A _left + Общее количество умножителей масштабирования, необходимых для определения A _right + Общее число умножений масштабирования, необходимое для определения A _left * _{Правильно} .

Последний член. Общее количество умножителей масштабирования, необходимых для определения A _left * A _right, может быть записано как: Число строк в A _left * число столбцов в A _left * число столбцов в _{правой части} . (Согласно 2-му правилу умножения матрицы)

Но мы могли бы также скопировать круглые скобки. Например:

• A ₁ * ( A ₂ * A ₃ * A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ ) * ( A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ * A ₄ ) * A ₅ и т. Д.

Для каждого возможного случая мы определим количество умножителей масштабирования, необходимое для нахождения A _left и A _right , а затем для A _left * A _right . Если у вас есть общее представление об рекурсии, вы уже поняли, как выполнить эту задачу. Наш алгоритм будет:

- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.

Почему это проблема динамического программирования? Чтобы определить ( A ₁ * A ₂ * A ₃ ), если вы уже рассчитали ( A ₁ * A ₂ ), это будет полезно в этом случае.

Чтобы определить состояние этой рекурсии, мы видим, что для решения каждого случая нам нужно знать диапазон матриц, с которыми мы работаем. Поэтому нам нужно начать и кончить . Поскольку мы используем divide и conquer, наш базовый регистр будет иметь менее 2 матриц ( begin > = end ), где нам не нужно вообще размножаться. У нас будет 2 массива: строка и столбец . строка [i] и столбец [i] будут хранить количество строк и столбцов для матрицы A _i . Мы будем иметь массив dp [n] [n] для хранения уже вычисленных значений и инициализировать его с помощью -1 , где -1 представляет значение, которое еще не было вычислено. dp [i] [j] представляет собой число умножителей масштабирования, необходимое для умножения A _i , A _{i + 1} , ....., A _j включительно. Псевдокод будет выглядеть так:

Procedure matrixChain(begin, end):
if begin >= end
    Return 0
else if dp[begin][end] is not equal to -1
    Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
    operation_for_left := matrixChain(begin, mid)
    operation_for_right := matrixChain(mid+1, right)
    operation_for_left_and_right := row[begin] * column[mid] * column[end]
    total := operation_for_left + operation_for_right + operation_for_left_and_right
    answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]

Сложность:

Значение начала и конца может варьироваться от 1 до n . Существует n ² разных состояния. Для каждого состояния цикл внутри будет выполняться n раз. Общая временная сложность: O(n³) и сложность памяти: O(n²) .