Что такое умножение матрицы цепей?

Question

Я пытаюсь понять, что такое умножение матрицы цепочек и чем оно отличается от обычного умножения. Я проверил несколько источников, но мне все они объяснили очень академически.

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

Спасибо

Answer 1

Цепное умножение - это просто серия умножений. A * B * C * D. Первоначально это не имеет ничего общего с программированием и динамическим программированием. Но есть хорошее правило (ассоциативный закон) A * (B * C) = (A * B) * C, но вычислительная стоимость этих выражений различна. Поэтому возникает задача оптимального распределения скобок. это было вступление. теперь читай вики.

Answer 2

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

M1 = 12 x 20
M2 = 20 x 15
M3 = 15 x 30

Есть два способа решения этой проблемы, в зависимости от того, где вы начинаете умножать свои матрицы.

1). ((M1 x M2) x M3)
2). (M1 x (M2 x M3))

Первый требует только 3 600 + 5400 = 9 000 умножений.
Второе решение требует 9 000 + 7 200 = 16 200 умножений.
Здесь мы выберем первый, а не второй, потому что нужно меньше умножений.
Ваша программа должна быть в состоянии сообщить пользователю, как заключить в скобки матрицы, чтобы минимизировать умножения ( Задача оптимизации )