Изменения
Опечатка
{{Задача|definition = Дана последовательность из <tex>n<//Не окончательный вариант --[[Участник:GosuGDR|GosuGDR]] 07:02tex> матриц, 10 декабря 2011 (MSK)требуется найти самый эффективный способ их перемножения.}}
Например, предположим, что А <tex>\dim{A}= (10 &\times; 30)</tex>, <tex>\dim{B } = (30 &\times; 5)</tex>, <tex>\dim{C } = (5 &\times; 60)</tex>. Тогда:
:Для <tex> (''AB''A \times B)''\times C'' = </tex> будет <tex>(10×30×5\times30\times5) + (10×5×60\times5\times60) = 1500 + 3000 = 4500 </tex> операций:''Для <tex> A''\times(''BC''B \times C) = </tex> будет <tex>(30×5×60\times5\times60) + (10×30×60\times30\times60) = 9000 + 18000 = 27000 операций. Как мы видим, первый способ гораздо эффективней. Теперь стало понятно, что нам надо найти оптимальную расстановку скобок в нашем выражении из <math>n</mathtex> матриц. Как бы это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнения этого алгоритма будет расти экспоненциально от <math>n</math> количества матриц, так как навскидку в каждую позицию мы можем поставить открывающуюся и закрывающуюся скобку, то асимптотика будет равна <math>O(2^n)</math>. Решение данной задачи, как мы увидим — это разбить нашу задачу на подзадачи. Так же мы увидим, что с помощю решения однократного решения подзадачи и повторного использования ответа, мы сможем заметно сократить асимптотикуопераций.
Как мы видим, первый способ гораздо эффективней.
== Решение задачи ==
=== Перебор всех вариантов ===
=== Псевдокод ===
'''int''' dp[][] <font color="green">// dp[i][j] — ответ на отрезке [i, j)</font> '''int''' v[] <font color= Литература "green">// Массив v[] — хранит все размеры матриц по порядку // Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократно // l — включая в отрезок, r — исключая из отрезка. Изначально l =0, r =n, где n {{---}} длина последовательности</font> '''int''' matrixChainMultiplication('''int''' l, '''int''' r) '''if''' dp[l][r] == -1 <font color="green">// Если значение динамики не посчитано</font> '''if''' l == r - 1 dp[l][r] = 0 <font color="green"> // Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю</font> '''else''' dp[l][r] = <tex>\infty</tex> '''for''' i = l + 1 '''to''' r - 1 dp[l][r] = min(dp[l][r], v[l] * v[i] * v[r] + matrixChainMultiplication(l, i) + matrixChainMultiplication(i, r)) '''return''' dp[l][r] == См. также == *[[Задача о наибольшей общей подпоследовательности ]]*[[Кратчайший путь в ациклическом графе ]]*[[Задача о расстановке знаков в выражении]]*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами | Aлгоритм Кока-Янгера-Касами ]]*[[Правильные скобочные последовательности | Правильные скобочные последовательности ]]== Источники информации == *[http://en.wikipedia.org/wiki/Matrix_chain_multiplication Wikipedia {{---}} Matrix chain multiplication]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория:Динамическое_программирование]]