当前位置:网站首页>动态规划_备忘录法_矩阵链乘问题

动态规划_备忘录法_矩阵链乘问题

2021-07-10 12:42:08 花城1122

问题描述

给定\(n\)个矩阵\(\{A_1,A_2,A_3,...,A_n\}\),其中\(A_i\)\(P_{i-1}\times P_i\)矩阵,\(i = 1,...,n\),并且\(A_i\)\(A_{i-1}\)是可乘的。由于矩阵乘法满足结合律,所以计算矩阵的链乘可有许多不同的计算次序,两个矩阵\(A_{i\times j}\)\(A_{j\times k}\)相乘的工作量为\(i\times j\times k\)次数乘。
给定向量\(P=<P_0,P_1,...,P_n>\)\(n\)个矩阵的行数和列数,确定一种乘法次序,使得基本运算“数乘”的总次数最少。

完全加括号

完全加括号的矩阵链乘积可递归地定义为:

  • 单个矩阵是完全加括号的
  • 矩阵链乘积\(A\)是完全加括号的,则\(A\)可表示为两个完全加括号的矩阵链乘积\(B\)\(C\)的乘积,并加括号,即\(A=(BC)\)

最优子结构

  • 矩阵链乘\(A_iA_{i+1}...A_j\)简记为\(A_{i...j},i\leq j\),于是矩阵链乘\(A_1A_2...A_n\)可记为\(A_{1...n}\),完全加括号形式为\(A_{1...n}=A_{1...k}A_{k+1...n},1\leq k < n\)
  • 矩阵连乘\(A_{1...n}\)的最优计算次序的计算量等于\(A_{1...k}\)\(A_{k+1...n}\)两者的最优计算次序的计算量之和,再加上\(A_{1...k}\)\(A_{k+1...n}\)相乘的计算量。矩阵链乘问题的最优解具有最优子结构特性。

最优解的递推关系

  • \(i\)\(j\)确定子问题的边界,输入\(P=<P_0,P_1,...P_n>\)

\[A_{i...j}=A_{i...k}A_{k+1...j},k=i,i+1,...,j-1 \]

  • 确定优化函数和递推方程:二维数组\(m\)用来保存矩阵链乘时所需的最小计算量

\[m[i][j]=\begin{cases} \min\limits_{i\leq k < j} \{m[i][k]+m[k+1][j]+P_{i-1}P_kP_j\} &\text{if } i<j \\ 0 &\text{if } i=j \end{cases} \]

  • 设立标记函数:为了确定加括号的次序,设计表\(s[i,j]\)记录求得最优时,最后一次运算的位置,即\(m[i][j]\)达到最小时\(k\)的划分。

算法描述(伪代码)

  • 迭代实现 备忘录法
MatrixChain(P,n)
	令所有m[i,j]的初值为0;
	for r <- 2 to n   do
		for i <- 1 to n-r+1  do
			j <- i+r-1;
			m[i,j] <- m[i+1,j]+P_i-1P_iP_j;
			s[i,j] = i;
			for k <- i+1 to j-1  do
				t <- m[i,k]+m[k+1,j]+P_i-1P_kP_j;
				if t < m[i,j]
					then m[i,j] <- t;
						 s[i,j] <- k;

结束语

醉后不知天在水,满船清梦压星河

作者:花城

版权声明
本文为[花城1122]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/huacheng1122/p/14993588.html