Я пытаюсь понять, что такое цепное матричное умножение и чем оно отличается от обычного умножения. Я проверил несколько исходников, но все они кажутся очень академически объясненными, чтобы я мог понять.
Я предполагаю, что это форма алгоритма динамического программирования для оптимизации операции, но я не пошел дальше.
Спасибо
Цепное умножение — это просто серия умножений. А * Б * С * Д . Изначально в нем нет ничего о программировании и динамическом программировании. Но есть красивое правило (ассоциативный закон) A * (B * C) = (A * B) * C, но вычислительные затраты на эти выражения разные. Таким образом, возникает задача оптимального распределения скобок. это было вступление. теперь читайте вики.
Умножение цепочки матриц — это задача, которую можно решить с помощью подхода динамического программирования. Для этого требуются правильные матрицы в скобках, чтобы умножать заданные матрицы с минимальным количеством умножений. Пример
M1 = 12 x 20
M2 = 20 x 15
M3 = 15 x 30
Есть два способа решить эту проблему, в зависимости от того, с чего вы начинаете умножать свои матрицы.
1). ((M1 x M2) x M3)
2). (M1 x (M2 x M3))
Для первого требуется всего 3600 + 5400 = 9000 умножений.
Для второго решения требуется 9000 + 7200 = 16200 умножений.
Здесь мы выберем первое, а не второе, потому что оно требует меньшего количества умножений.
Ваша программа должна сообщать пользователю, как заключать матрицы в скобки, чтобы свести к минимуму умножения (Проблема оптимизации).
