Я пытаюсь понять, что такое умножение цепной матрицы и как оно отличается от обычного умножения. Я проверил несколько sourcers, но все, кажется, очень академически объяснено для меня, чтобы понять.Что такое умножение цепей матрицы?
Я думаю, что это форма алгоритма динамического программирования для оптимизации работы, но я не пошел дальше.
Thanks
Цепь умножения - это всего лишь серия умножений. A * B * C * D. Первоначально он не имеет ничего о программировании и динамическом программировании. Но есть хорошее правило (ассоциативный закон) A * (B * C) = (A * B) * C, но вычислительная стоимость этих выражений различна. Таким образом, существует задача оптимального распределения скобок. это было интро. теперь читайте wiki.
Matrix Chain Умножение является проблемой, которая может быть решена с помощью динамического программирования подхода, он требует собственных введенных матриц для умножения матриц, данных с минимальным количеством умножений. Пример
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 умножений.
Второе решение требует 9 000 + 7 200 = 16 200 умножений.
Здесь мы выберем первую секунду, потому что ей нужно меньше количества умножений.
Вашей программа должна быть в состоянии сказать пользователю, как скобки матрицы так, что сводит к минимуму умножениям (задачи оптимизации)
она с о динамическом программировании, это простое объяснение того, как динамическое программирование работ. вы можете посмотреть CLRS для получения более подробной информации. – DarthVader
@ Андре это красивое правило называется ассоциативным законом. – Geek
@ Geek было так давно, что я забыл, почему я не упоминал об этом, либо я забыл имя, либо просто добавил какой-то юмор. – Andrey