90
правок
Изменения
Нет описания правки
'''Задача о порядке перемножения матриц''' — классическая задача , которая может быть решена с помощью динамического программирования, в которой дана последовательность матриц <tex> A_1, A_2, ..., A_n </tex> и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов <tex> A_{i - 1}</tex> совпадает с количеством строк <tex> A_i </tex> матрицы).
== Подробное описание задачи ==
Произведение матриц — ассоциативная операция. Когда матрицы велики по одному измерению и малы по другому, количество скалярных операций может серьёзно зависеть от порядка перемножений матриц. Допустим, нам даны 3 матрицы <tex> A_1, A_2, A_3 </tex> размерами соответственно <tex> 10 \times 100, 100 \times 5</tex> и <tex>5 \times 50</tex>. Существует 2 способа их перемножения (расстановки скобок): <tex>((A_1A_2)A_3)</tex> и <tex>(A_1(A_2A_3))</tex>. В первом случае нам потребуется <tex>10\cdot100\cdot5 + 10\cdot5\cdot50 = 7500</tex> скалярных умножений, а во втором случае <tex>100\cdot5\cdot50 + 10\cdot100\cdot50 = 75000</tex> умножений — разница налицо. Поэтому может оказаться выгоднее потратить некоторое время на предобработку, решив, в каком порядке лучше всего умножать, чем умножать сразу в лоб.
