Динамическое программирование порядок перемножения матриц

Задача о порядке перемножения матриц

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

Расстановок скобок достаточно много и их количество очень быстро растет. Точное количество всевозможных вариантов равно [math]n[/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_[/math] , то получаем следующее рекуррентное соотношение: [math] f(i,j) = \left \< \begin 0, & i=j \\ \min\limits_<(f(i,k) + f(k+1,j) + p_p_kp_j)> & i \lt j \end \right. [/math]

Объясняется оно просто: для того, чтобы найти произведение матриц [math]M_[/math] при [math]i=j[/math] не нужно ничего делать — это и есть сама матрица [math]M_i[/math] . При нетривиальном случае мы перебираем все точки разбиения матрицы [math]M_[/math] на матрицы [math]M_[/math] и [math]M_[/math] , ищем количество операций, необходимое чтобы их получить и затем перемножаем для получения матрицы [math]M_[/math] .(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц [math]M_M_[/math] ). Считаем, что размеры матриц заданы в массиве [math]p[/math] и размер матрицы [math]M_i[/math] равен [math]p_ \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 [/math] или асимптотически [math] \frac\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]

См. также

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

Источник

Динамическое программирование.

Рассмотрим произведение матриц M 1 M 2 M 3 . M n 1 M n . Каждая матрица M i имеет размер r i 1 r i . M 1 ( r 0 ; r 1 ) M 2 ( r 1 ; r 2 ) M 3 ( r 2 ; r 3 ) . M n 1 ( r n 2 ; r n 1 ) M n ( r n Вычисление произведения двух матриц – размер первой n p и размер второй p m требует n p m умножений их элементов: C ( n ; m ) = A ( n ; p ) × B ( p ; m ) c ij = k =1.. p ( a ik * b kj ) для i 1.. n , j 1.. m

Задача о порядке перемножения матриц

Общее количество элементарных операций умножения, требуемое при вычислении произведения цепочки матриц, зависит от порядка , в котором производятся попарные умножения матриц. Требуется найти такой порядок перемножения матриц, который минимизирует общее количество элементарных операций умножения.

Пример: M 1 M 2 M 3 M 4 ,

где размер ( M 1 ) = 10 20, размер ( M 2 ) = 20 50, размер ( M 3 ) = 50 1, размер ( M 3 ) = 1 100 .

M 4
				M 1	M 1 M 2 M 3 M 4 ,
																		M 2
																							M 3			20 000								100 000					5 000
1)	M 1 ( M 2 ( M 3 M 4 )) (10 20 100 (20 50 100 (50 1 100) ) ) 125
000		200							1 000				1 000
2)	( M 1 ( M 2 M 3 )) M 4 ( (10 20 1 (20 50 1) ) 10 1 100 ) 2 200

Рекуррентное соотношение

Пусть m ij – оптимальное количество умножений, требуемое для вычисления произведения цепочки матриц M ( i , j ) = M i M i +1 . M j 1 M j , где 1 i j n . Очевидно, что M ( i , i ) = M i и m ii = 0 , а m 1 n – соответствует решению задачи для исходной цепочки M (1, n ) . При 1 i j n справедливо :

m ij = Min < m ik + m k +1, j + r i 1 r k r j
M ( i ,	i k j >.
	j ) = M ( i , k ) M ( k+ 1, j ),		i k j
r i 1 r j				r i 1 r k	r k r j

1) Заметим , что в правой части равенства разности индексов k – i и j – k –1 у слагаемых m ik и m k +1, j меньше, чем разность индексов j – i в m ij . Таким образом, рекуррентное соотношение следует решать, начиная с m ii = 0 и последовательно увеличивая разность индексов j – i до тех пор, пока не получим m 1 n . 2) Удобно представлять результаты вычислений в виде таблицы . В этой таблице строка с номером l состоит из ячеек T ( i , j ), индексы которых связаны соотношением j – i = l . Т.е. j = i + l и T ( i , j ) = T ( i , i + l ).

В ячейках таблицы T ( i , j ) хранятся вычисленные
значения m ij и те значениея q ij = k в диапазоне
i k j , при которых был получен
Min < m ik + m k +1, j + r i 1 r k r j >.
l = 0	Т (1, 1)	Т (2, 2)	Т (3, 3)	Т (4, 4)	…	Т ( n 1, n 1) Т ( n , n )
l = 1	Т (1, 2)	Т (2, 3)	Т (3, 4)	…	Т ( n 2, n 1)	Т ( n 1, n )
l = 2	Т (1, 3)	Т (2, 4)	…	Т ( n 3, n 1)	Т ( n 2, n )
…	…	…	…	…
l = n –3	Т (1, n 2)	Т (2, n 1)	Т (3, n )
l = n –2	Т (1, n 1)	Т (2, n )
l = n –1	Т (1, n )

Алгоритм вычисляет оптимальное значение m 1 и заполняет n

Характеристики алгоритма

Алгоритм требует: •порядка n 2 /2 элементов памяти для хранения таблицы •около n 3 /3 выполнений тела внутреннего цикла. Пример см. далее

24.02.2014	Динамическое	19
программирование

Пример вычисления M 1 M 2 M 3 M 4 (см. слайд

13 ) Для заполнения строки таблицы при l = 1 вычислим последовательно = m 1,1 + m 2,2 + r 0 r 1 r 2 = 10 20 50 = 10 000, = m 2,2 + m 3,3 + r 1 r 2 r 3 = 20 50 1 = 1000, = m 3,3 + m 4,4 + r 2 r 3 r 4 = 50 1 100 = 5000. Здесь фактически минимум находить не требуется, так как тело цикла по k выполняется лишь один раз (при k = i ). Заполненная строка таблицы есть

l = 1	m 1,2 = 10 000		m 2,3 = 1000	m 3,4 = 5000
	q 1,2	= 1	q 2,3 = 2	q 3,4 = 3

m ij = Min < m ik + m k +1, j + r i 1 r k r j i k j >.
Строка таблицы при L = 2 m 1,3 = Min < m 1 k + m k +1,3 + r 0 r k r 3 k = 1, 2>= = Min < m 1,1 + m 2,3 + r 0 r 1 r 3 , m 1,2 + m 3,3 + r 0 r 2 r 3 >= = Min <0 + 1000 200, 10 000 0 500>= = Min < 1200 , 10 500>= 1200 (при k = 1 ), m 2,4 = Min < m 2 k + m k +1,4 + r 1 r k r 4 k = 2, 3>= = Min < m 2,2 + m 3,4 + r 1 r 2 r 4 , m 2,3 + m 4,4 + r 0 r 2 r 3 >= = Min <0 + 5000 100 000, 1000 0 2000>= = Min = 3000 (при k = 3 )

l = 1	m 1,2 = 10 000	m 2,3 = 1000	m 3,4 = 5000
	q 1,2 = 1	q 2,3 = 2	q 3,4 = 3
l = 2				m 1,3 = 1200	m 2,4 = 3000
	q 1,3 = 1	q 2,4 = 3
m ij = Min < m ik + m k +1, j + r i 1			r k r j i k j >.

Источник