Задача о порядке перемножения матриц — различия между версиями
Tsarevfs (обсуждение | вклад) (→Ссылки) |
м (rollbackEdits.php mass rollback) |
||
(не показано 67 промежуточных версий 15 участников) | |||
Строка 1: | Строка 1: | ||
− | + | {{Задача | |
− | + | |definition = Дана последовательность из <tex>n</tex> матриц, требуется найти самый эффективный способ их перемножения. | |
− | + | }} | |
− | + | ||
− | == | + | У нас есть множество способов перемножить матрицы, потому что операция перемножения ассоциативна. Другими словами, нет разницы в каком порядке расставляются скобки между множителями, результат будет один и тот же. |
− | === | + | |
− | + | [[Правильные скобочные последовательности | Расстановок скобок]] достаточно много и их количество очень быстро растет. Точное количество всевозможных вариантов равно <tex>n</tex>–ому [[Числа Каталана | числу Каталана]]. | |
− | + | Однако, порядок в котором расставляются скобки между матрицами повлияет на количество арифметических операций, которые потребуются на вычисление ответа, или, другими словами, на ''эффективность''. | |
− | + | ||
− | + | Например, предположим, что <tex>\dim{A}= 10 \times 30</tex>, <tex>\dim{B} = 30 \times 5</tex>, <tex>\dim{C} = 5 \times 60</tex>. Тогда: | |
− | <tex> | + | |
+ | : Для <tex> (A \times B)\times C</tex> будет <tex>(10\times30\times5) + (10\times5\times60) = 1500 + 3000 = 4500</tex> операций | ||
+ | : Для <tex> A \times(B \times C)</tex> будет <tex>(30\times5\times60) + (10\times30\times60) = 9000 + 18000 = 27000</tex> операций. | ||
+ | |||
+ | Как мы видим, первый способ гораздо эффективней. | ||
+ | |||
+ | == Решение задачи == | ||
+ | |||
+ | === Перебор всех вариантов === | ||
+ | |||
+ | В данной задаче нужно узнать минимальное количество операций (или минимальную стоимость), необходимых для перемножения матриц. Если перемножить только две матрицы, то можно осуществить это едиственным способом, следовательно минимальная стоимость — это стоимость перемножения этих двух матриц. В общем, можно найти минимальную стоимость используя следующий [[Динамическое программирование | рекурсивный алгоритм]]: | ||
+ | |||
+ | * взять последовательность матриц и разделить её на две части, | ||
+ | * найти минимальную стоимость перемножения на каждой подпоследовательности, | ||
+ | * сложить эти две стоимости и прибавить к этому стоимость перемножения двух получившихся матриц, | ||
+ | * сделать это для каждой возможной позиции в последовательности, в которой она может быть разделена и взять минимум среди всех результатов. | ||
+ | |||
+ | Или другими словами, давайте обозначим через <tex>f(i, j)</tex> минимальное количество скалярных умножений для вычисления матрицы <tex>M_{i..j}</tex>, то получаем следующее рекуррентное соотношение: | ||
+ | <tex> f(i,j) = \left \{ | ||
\begin{array}{ll} | \begin{array}{ll} | ||
0, & i=j \\ | 0, & i=j \\ | ||
− | min( | + | \min\limits_{i \leqslant k < j}{(f(i,k) + f(k+1,j) + p_{i-1}p_kp_j)} & i < j |
\end{array} | \end{array} | ||
\right. | \right. | ||
</tex> | </tex> | ||
− | Объясняется оно просто: для того, чтобы найти произведение матриц <tex> | + | Объясняется оно просто: для того, чтобы найти произведение матриц <tex>M_{i..j}</tex> при <tex>i=j</tex> не нужно ничего делать — это и есть сама матрица <tex>M_i</tex>. При нетривиальном случае мы перебираем все точки разбиения матрицы <tex>M_{i..j}</tex> на матрицы <tex>M_{i..k}</tex> и <tex>M_{k+1..j}</tex>, ищем количество операций, необходимое чтобы их получить и затем перемножаем для получения матрицы <tex>M_{i..j}</tex>.(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц <tex>M_{i..k}M_{k+1..j}</tex>). Считаем, что размеры матриц заданы в массиве <tex>p</tex> и размер матрицы <tex>M_i</tex> равен <tex>p_{i-1} \times p_i</tex>. |
− | + | ||
− | + | ||
+ | Чтобы привести пример, давайте вернемся к нашим матрицам. Если у нас есть четыре матрицы <tex>ABCD</tex>, то мы посчитаем для <tex>(A)(BCD)</tex>, <tex>(AB)(CD)</tex>, и <tex>(ABC)(D)</tex>, делая рекурсивные вызовы на отрезках <tex>ABC</tex>, <tex>AB</tex>,<tex>CD</tex>, и <tex>BCD</tex>, чтобы найти минимальную стоимость. Потом среди них выбираем лучший вариант. Так же, этот алгоритм дает не только минимальную стоимость, но и показывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом матрицы, каким дается нам минимальная стоимость. | ||
+ | |||
+ | Однако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех [[Правильные скобочные последовательности | скобочных последовательностей]]. Делается значительное количество ненужной работы. Например, в выше описанном алгоритме, осуществляется рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета <tex>ABC</tex> и <tex>AB</tex>. Но нахождение наилучшей стоимости для подсчета <tex>ABC</tex> так же требует нахождения лучшей стоимости для <tex>AB</tex>. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется <tex>n</tex>–ому [[Числа Каталана | числу Каталана]], да плюс вычисление для каждой [[Правильные скобочные последовательности | правильной скобочной последовательности]] ''затрат'' на перемножение (то есть <tex>O(n \cdot C_n)</tex>). Так как <tex>N</tex>-ое [[Числа Каталана | число Каталана]] равняется <tex dpi="163"> \frac{1}{n+1}{2 n \choose n} </tex> или асимптотически <tex dpi="163"> \frac{4^n}{n^{3/2}\sqrt{\pi}} </tex>, а это быстро возрастающая функция, нам бы хотелось решение, которое работает быстрее. | ||
+ | |||
+ | === Псевдокод === | ||
+ | |||
+ | |||
+ | '''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] | ||
− | + | [[Категория: Дискретная математика и алгоритмы]] | |
− | + | [[Категория:Динамическое_программирование]] |
Текущая версия на 19:17, 4 сентября 2022
Задача: |
Дана последовательность из | матриц, требуется найти самый эффективный способ их перемножения.
У нас есть множество способов перемножить матрицы, потому что операция перемножения ассоциативна. Другими словами, нет разницы в каком порядке расставляются скобки между множителями, результат будет один и тот же.
Расстановок скобок достаточно много и их количество очень быстро растет. Точное количество всевозможных вариантов равно –ому числу Каталана. Однако, порядок в котором расставляются скобки между матрицами повлияет на количество арифметических операций, которые потребуются на вычисление ответа, или, другими словами, на эффективность.
Например, предположим, что
, , . Тогда:- Для будет операций
- Для будет операций.
Как мы видим, первый способ гораздо эффективней.
Решение задачи
Перебор всех вариантов
В данной задаче нужно узнать минимальное количество операций (или минимальную стоимость), необходимых для перемножения матриц. Если перемножить только две матрицы, то можно осуществить это едиственным способом, следовательно минимальная стоимость — это стоимость перемножения этих двух матриц. В общем, можно найти минимальную стоимость используя следующий рекурсивный алгоритм:
- взять последовательность матриц и разделить её на две части,
- найти минимальную стоимость перемножения на каждой подпоследовательности,
- сложить эти две стоимости и прибавить к этому стоимость перемножения двух получившихся матриц,
- сделать это для каждой возможной позиции в последовательности, в которой она может быть разделена и взять минимум среди всех результатов.
Или другими словами, давайте обозначим через
минимальное количество скалярных умножений для вычисления матрицы , то получаем следующее рекуррентное соотношение:Объясняется оно просто: для того, чтобы найти произведение матриц
при не нужно ничего делать — это и есть сама матрица . При нетривиальном случае мы перебираем все точки разбиения матрицы на матрицы и , ищем количество операций, необходимое чтобы их получить и затем перемножаем для получения матрицы .(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц ). Считаем, что размеры матриц заданы в массиве и размер матрицы равен .
Чтобы привести пример, давайте вернемся к нашим матрицам. Если у нас есть четыре матрицы , то мы посчитаем для , , и , делая рекурсивные вызовы на отрезках , , , и , чтобы найти минимальную стоимость. Потом среди них выбираем лучший вариант. Так же, этот алгоритм дает не только минимальную стоимость, но и показывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом матрицы, каким дается нам минимальная стоимость.
Однако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех скобочных последовательностей. Делается значительное количество ненужной работы. Например, в выше описанном алгоритме, осуществляется рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета и . Но нахождение наилучшей стоимости для подсчета так же требует нахождения лучшей стоимости для . Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется –ому числу Каталана, да плюс вычисление для каждой правильной скобочной последовательности затрат на перемножение (то есть ). Так как -ое число Каталана равняется или асимптотически , а это быстро возрастающая функция, нам бы хотелось решение, которое работает быстрее.
Псевдокод
int dp[][] // dp[i][j] — ответ на отрезке [i, j)
int v[] // Массив v[] — хранит все размеры матриц по порядку
// Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократно
// l — включая в отрезок, r — исключая из отрезка. Изначально l = 0, r = n, где n — длина последовательности
int matrixChainMultiplication(int l, int r)
if dp[l][r] == -1 // Если значение динамики не посчитано
if l == r - 1
dp[l][r] = 0 // Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю
else
dp[l][r] =
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]