Изменения
Нет описания правки
'''Задача о порядке перемножения матриц''' — классическая задача, которая может быть решена с помощью динамического программирования. В этой задаче нам дана последовательность матриц, в которой мы хотим найти самый эффективный способ перемножения их. На самом деле задача заключается не в нахождении результата перемножения, а просто нужно найти порядокв нахождении нужного порядока, в котором нам надо их перемножитьмы будем перемножать.
У нас есть много способов, потому что перемножение ассоциативнооперация перемножения ассоциативна. Другими словами, нет разницы как мы расставим скобки между множителями, результат будет один и тот же. Например, если у нас есть четыре матрицы ''A'', ''B'', ''C'' и ''D'', то у нас есть следующие варианты:
:(''ABC'')''D'' = (''AB'')(''CD'') = ''A''(''BCD'') = ''A''(''BC'')''D'' = ....
Однако, порядок в котором мы расставим скобки в нашем выражении повлияет на количество простых арифметических операций, которые мы потратим на вычисление ответа, или, другими словами, на ''эффективность''.
Например, предположим, что А = (10 × 30), B = (30 × 5), C = (5 × 60). Тогда:
Очевидно, что первый способ гораздо эффективней. Теперь мы поняли, что нам надо найти оптимальную расстановку скобок в нашем выражении из ''n'' матриц.
Как это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнение этого алгоритма будет эксапаненциально рости от ''n'' количества матриц. Решение данной проблемы, как мы увидим — это разбить нашу задачу на подзадачи. С Так же мы увидим, что с помощю решения подзадач по одному разу однократного решения подзадачи и повторного использования решенияответа, мы сможем заметно сократить асимптотику. Эта задача входит в классические задачи
== Решение динамическим программированием ==
Сначала, давайте считать то, что мы реально хотим знать минимальную стоимость или минимальное количесвто операций(или минимальную стоимость), необходимых для перемножения матриц. Если мы перемножаем только две матрицы, то существует едиственный способ сделать мы можем осуществить этотолько едиственным способом, следовательно минимальная стоимость — это стоимость этого перемножения. В общем, мы моежм можем найти минимальную стоимость испозльуя используя следующий рекурсивный алгоритм:
* Взять последовательность матриц и разделить её на две части.
* Сделать это для каждой возможной позиции в последовательности, в которой она может быть разделена и взять минимум среди всех результатов.
Внезапно, если мы применим этот алгоритм, то мы обнаружим, что это так же медленно, как и наивный способ перебирания всех скобочных последовательностей! Что пошло не так? Ответом на этот вопрос является тофакт, что мы делаем много ненужной работы. Например, в выше описанном алгоритме, мы сделали рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета ''ABC'' и ''AB''. Но нахождение лучшей наилучшей стоимости для подсчета ''ABC'' так же требует нахождения лучшей стоимости для ''AB''. Так как рекурсия растет вглбь все больше и больше, то и число ненужных повторений увеличивается.
Одно из простых решений: ''меморизация''. Каждый раз, когда мы считаем минимальную стоимость на отрезке, мы сохраняем ответ. Когда у нас просят посчитать это ещё раз, то мы сразу же выдадим ответ и не будем пересчитывать. Хоть у нас <math> n^2/2 </math>
One simple solution is called memoization: each time we compute the minimum cost needed to multiply out a specific subsequence, we save it. If we are ever asked to compute it again, we simply give the saved answer, and do not recompute it. Since there are about n2/2 different subsequences, where n is the number of matrices, the space required to do this is reasonable. It can be shown that this simple trick brings the runtime down to O(n3) from O(2n), which is more than efficient enough for real applications. This is top-down dynamic programming.
Pseudocode (without memoization):
Псевдокод (без меморизации):
