Задача о порядке перемножения матриц — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Задача о порядке перемножения матриц''' — классическая задача динамического программир…»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 70 промежуточных версий 15 участников)
Строка 1: Строка 1:
'''Задача о порядке перемножения матриц''' — классическая задача динамического программирования, в которой дана последовательность матриц<math> A_1, A_2, ..., A_n </math> и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов <math> A_{i - 1}</math> совпадает с количеством строк <math> A_i </math> матрицы).
+
{{Задача
 +
|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> (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}
 +
0, & i=j \\
 +
\min\limits_{i \leqslant k < j}{(f(i,k) + f(k+1,j) + p_{i-1}p_kp_j)} & i < j
 +
\end{array}
 +
\right.
 +
</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

Задача:
Дана последовательность из [math]n[/math] матриц, требуется найти самый эффективный способ их перемножения.


У нас есть множество способов перемножить матрицы, потому что операция перемножения ассоциативна. Другими словами, нет разницы в каком порядке расставляются скобки между множителями, результат будет один и тот же.

Расстановок скобок достаточно много и их количество очень быстро растет. Точное количество всевозможных вариантов равно [math]n[/math]–ому числу Каталана. Однако, порядок в котором расставляются скобки между матрицами повлияет на количество арифметических операций, которые потребуются на вычисление ответа, или, другими словами, на эффективность.

Например, предположим, что [math]\dim{A}= 10 \times 30[/math], [math]\dim{B} = 30 \times 5[/math], [math]\dim{C} = 5 \times 60[/math]. Тогда:

Для [math] (A \times B)\times C[/math] будет [math](10\times30\times5) + (10\times5\times60) = 1500 + 3000 = 4500[/math] операций
Для [math] A \times(B \times C)[/math] будет [math](30\times5\times60) + (10\times30\times60) = 9000 + 18000 = 27000[/math] операций.

Как мы видим, первый способ гораздо эффективней.

Решение задачи

Перебор всех вариантов

В данной задаче нужно узнать минимальное количество операций (или минимальную стоимость), необходимых для перемножения матриц. Если перемножить только две матрицы, то можно осуществить это едиственным способом, следовательно минимальная стоимость — это стоимость перемножения этих двух матриц. В общем, можно найти минимальную стоимость используя следующий рекурсивный алгоритм:

  • взять последовательность матриц и разделить её на две части,
  • найти минимальную стоимость перемножения на каждой подпоследовательности,
  • сложить эти две стоимости и прибавить к этому стоимость перемножения двух получившихся матриц,
  • сделать это для каждой возможной позиции в последовательности, в которой она может быть разделена и взять минимум среди всех результатов.

Или другими словами, давайте обозначим через [math]f(i, j)[/math] минимальное количество скалярных умножений для вычисления матрицы [math]M_{i..j}[/math], то получаем следующее рекуррентное соотношение: [math] f(i,j) = \left \{ \begin{array}{ll} 0, & i=j \\ \min\limits_{i \leqslant k \lt j}{(f(i,k) + f(k+1,j) + p_{i-1}p_kp_j)} & i \lt j \end{array} \right. [/math]

Объясняется оно просто: для того, чтобы найти произведение матриц [math]M_{i..j}[/math] при [math]i=j[/math] не нужно ничего делать — это и есть сама матрица [math]M_i[/math]. При нетривиальном случае мы перебираем все точки разбиения матрицы [math]M_{i..j}[/math] на матрицы [math]M_{i..k}[/math] и [math]M_{k+1..j}[/math], ищем количество операций, необходимое чтобы их получить и затем перемножаем для получения матрицы [math]M_{i..j}[/math].(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц [math]M_{i..k}M_{k+1..j}[/math]). Считаем, что размеры матриц заданы в массиве [math]p[/math] и размер матрицы [math]M_i[/math] равен [math]p_{i-1} \times p_i[/math].


Чтобы привести пример, давайте вернемся к нашим матрицам. Если у нас есть четыре матрицы [math]ABCD[/math], то мы посчитаем для [math](A)(BCD)[/math], [math](AB)(CD)[/math], и [math](ABC)(D)[/math], делая рекурсивные вызовы на отрезках [math]ABC[/math], [math]AB[/math],[math]CD[/math], и [math]BCD[/math], чтобы найти минимальную стоимость. Потом среди них выбираем лучший вариант. Так же, этот алгоритм дает не только минимальную стоимость, но и показывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом матрицы, каким дается нам минимальная стоимость.

Однако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех скобочных последовательностей. Делается значительное количество ненужной работы. Например, в выше описанном алгоритме, осуществляется рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета [math]ABC[/math] и [math]AB[/math]. Но нахождение наилучшей стоимости для подсчета [math]ABC[/math] так же требует нахождения лучшей стоимости для [math]AB[/math]. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется [math]n[/math]–ому числу Каталана, да плюс вычисление для каждой правильной скобочной последовательности затрат на перемножение (то есть [math]O(n \cdot C_n)[/math]). Так как [math]N[/math]­-ое число Каталана равняется [math] \frac{1}{n+1}{2 n \choose n} [/math] или асимптотически [math] \frac{4^n}{n^{3/2}\sqrt{\pi}} [/math], а это быстро возрастающая функция, нам бы хотелось решение, которое работает быстрее.

Псевдокод

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] = [math]\infty[/math]
            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]

См. также

Источники информации