Изменения
Нет описания правки
'''Задача о порядке перемножения матриц''' (англ. ''chain matrix multiplication'') — классическая задача, которая может быть решена с помощью динамического программирования. В этой задаче нам дается последовательность матриц, в которой мы хотим найти самый эффективный способ их перемножения.
У нас есть множество способов перемножить матрицы, потому что операция перемножения ассоциативна. Другими словами, нет разницы в каком порядке мы расставим скобки между множителями, результат будет один и тот же. Например, если у нас есть четыре матрицы ''A'', ''B'', ''C'' и ''D'', то существуют следующие варианты::(''ABC'')''D'' = (''AB'')(''CD'') = ''A''(''BCD'') = ''A''(''BC'')''D'' = ....
Однако, порядок в котором мы расставим скобки между матрицами повлияет на количество арифметических операций, которые потребуются на вычисление ответа, или, другими словами, на ''эффективность''.
