Динамическое программирование умножения цепочек матриц

Question

Предположим, что умножение матрицы G1 размерности p × q на другую матрицу G2 размерности q × r требует скалярных умножений pqr.Вычисление произведения из n матриц G1G2G3… .. Gn можно сделать, заключив скобки различными способами.Определите GiGi + 1 как явно вычисленную пару для данной парантеризации, если они умножаются напрямую.Например, в цепочке умножения матриц G1G2G3G4G5G6 с использованием скобок (G1 (G2G3)) (G4 (G5G6)), G2G3 и G5G6 являются только явно вычисленными парами.

Рассмотрим цепочку умножения матриц F1F2F3F4F5, где матрицы F1,F2, F3, F4 и F5 имеют размеры 2 × 25,25 × 3,3 × 16,16 × 1 и 1 × 1000 соответственно.В скобках F1F2F3F4F5, которые минимизируют общее количество скалярных умножений, явно вычисленные пары имеют / являются

только F1F2 и F3F4

только F2F3

только F3F4

только F2F3 и F4F5

============================================================================ *======

Мой подход - я хочу решитьэто менее одной минуты, но я знаю только один способ - использовать динамический подход «снизу вверх», составив таблицу, и еще одно, что я могу сделать вывод, это то, что мы должны умножиться на F5 наконец, потому что в его измерении 1000. Итак, пожалуйста, какразвить быструю интуицию для такого рода вопросов!

============================================================================

Правильный ответэто F3F4

Answer 1

Самая важная вещь, которую нужно отметить, это размер 1 × 1000 .Вам лучше следить за этим, если вы хотите минимизировать умножения.Хорошо, теперь мы знаем, что мы в основном умножаем небольшое число на 1000 .

Тщательно исследуем, если мы пойдем с F4F5 , мы будем умножать 16x1x1000 .Но вычисляя F3F4 first , матрица результатов имеет размерность 3x1 .Поэтому, используя F3F4 , мы можем получить небольшие числа, такие как 3,1 .Таким образом, никоим образом я не пойду с F4F5 .

По аналогичной логике я бы не пошел с F2F3 и потерял бы меньшее 3 и стал больше 25 и 16 для последующего использования с 1000 .

OK , для F1F2, вы можете быстро обнаружить, что (F1F2) (F3F4) не лучше, чем (F1 (F2 (F3F4))) .Таким образом, ответ F3F4