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