90
правок
Изменения
Нет описания правки
'''Задача о порядке перемножения матриц''' — классическая задача, которая может быть решена с помощью динамического программирования. В этой задаче нам последовательность матриц, в которой мы хотим найти самый эффективный способ перемножения их. На самом деле задача заключается не в нахождении результата перемножения, а просто нужно найти порядок, в котором нам надо их перемножить.
У нас есть много способов, потому что перемножение ассоциативно. Другими словами, нет разницы как мы расставим скобки между множителями, результат будет один и тот же. Например, если у нас есть четыре матрицы ''A'', ''B'', ''C'' и ''D'', то у нас есть следующие варианты:
:(''ABC'')''D'' = (''AB'')(''CD'') = ''A''(''BCD'') = ''A''(''BC'')''D'' = ....
Однако, порядок в котором мы расставим скобки в нашем выражении повлияет на количество арифметических операций, которые мы потратим на вычисление ответа, или, другими словами, на ''эффективность''.
Например, предположим, что А = (10 × 30), B = (30 × 5), C = (5 × 60). Тогда:
:(''AB'')''C'' = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 операций
:''A''(''BC'') = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 операций.
Очевидно, что первый способ гораздо эффективней. Теперь мы поняли, что нам надо найти оптимальную расстановку скобок в нашем выражении из ''n'' матриц.
Как это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнение этого алгоритма будет эксапаненциально рости от ''n'' количества матриц. Решение данной проблемы, как мы увидим — это разбить нашу задачу на подзадачи. С помощю решения подзадач по одному разу и повторного использования решения, мы сможем заметно сократить асимптотику. Эта задача входит в классические задачи
==Динамическое решение==
===Сведение задачи к подзадачам ===
* Томас Х. Кормен и др. Алгоритмы: построение и анализ
* Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms
[[Категория: Дискретная математика и алгоритмы]]
[[Категория:Динамическое_программирование]]
