搞定矩阵连乘的算法技巧
给定n个矩阵,其中Ai与Ai+1是可乘的(i=1,2,…… n-1)。考察这n个矩阵的连乘积A1A2A2……An。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为:
1、单个矩阵是完全加括号的;
2、矩阵连乘积A是完全加括号的,则A可表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号,即A=(BC)。
例如,矩阵连乘积可以有以下5种完全加括号方式:
,,,,
矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数,若A是一个p*q矩阵,B是一个q*r矩阵,则其乘积C=AB是一个p*r的矩阵,共需要p*q*r次数乘。
穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。
/*穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序*/
void matrixMultiply(int** a, int** b, int** c, int ra, int ca, int rb, int cb)
/*
ra、ca表示矩阵A的行数和列数,rb、cb表示矩阵B的行数和列数
*/
{
if (ca != cb)
//矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数
cout<<"矩阵不可乘"<<endl;
//矩阵A的每一行分别与矩阵B的每一列相乘
for (int i = 0; i < ra; i++)
{
for (int j = 0; j < cb; j++)
{
int sum = a[i][0] * b[0][j];
//将A的每一行与B的每一列对应位置相乘并相加
for (int k = 1; k < ca; k++)
sum += a[i][k] * b[k][j];
//C=A*B,记录乘积结果
c[i][j] = sum;
}
}
}
算法复杂度分析:
对于n个矩阵的连乘积,设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:
动态规划算法:
将矩阵连乘积 简记为A[i:j] ,这里i≤j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开,i≤k<j,则其相应完全加括号方式
计算量:A[i:k]的计算量加上A[k+1:j]的计算量,再加上 A[i:k]和A[k+1:j]相乘的计算量。
步骤:
1、分析最优解的结构
特征:计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
2、建立递归关系
设计算A[i:j],1≤i≤j≤n,所需要的最少数乘次数m[i,j],则原问题的最优值为m[1,n]
当i=j时,A[i:j]=Ai,因此,m[i,i]=0,i=1,2,…,n
当i<j时,
3、计算最优值
用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法。
void MatrixChain(int* p, int n, int** m, int** s)
{
for (int i = 1; i <= n; i++)
m[i][i] = 0;//自己与自己的相乘次数是0
for (int r = 2; r <= n; r++)
/* r表示当前相乘的矩阵个数 */
{
for (int i = 1; i <= n - r + 1; i++)
/* i表示当前相乘的起始矩阵,j表示当前相乘的终止矩阵*/
{
int j = i + r - 1;
m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
s[i][j] = i;//在i之后断开
for (int k = i + 1; k < j; k++)
{
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];//找下一个断开位置
if (t < m[i][j])
{
m[i][j] = t;//记录最优值
s[i][j] = k;//在k之后断开
}
}
}
}
}
4、构造最优解
void Traceback(int i, int j, int** s)
{
if (i == j)
return;
Traceback(i, s[i][j], s);
Traceback(s[i][j] + 1, j, s);
cout << "Multiply A" << i << "," << s[i][j];
cout << "and A " << (s[i][j] + 1) << "," << j << endl;
}
s[i][j]中的数表明,计算矩阵链A[i:j]的最佳方式是在矩阵A(k)和A(k+1)之间断开,即最优加括号方式为。
上一篇: 定制IDEA中类与方法的注释样式模板
下一篇: 搞定矩阵连乘!用动态规划轻松应对
推荐阅读
-
二叉树, 329. 矩阵中的最长递增路径, 备忘递归表填充, [73] [算法分析与设计] 516.
-
大公司使用的 12 种切分算法,一口搞定库与表的分割
-
NeurIPS 2022 | 最强斗地主AI!网易互娱AI Lab提出基于完美信息蒸馏的方法-完美信息蒸馏(PTIE) 在斗地主游戏中,非完美信息的引入主要是由于三位玩家均不能看到别人的手牌,对于任意一位玩家而言,仅可知道其余两位玩家当前手牌的并集,而难于精准判断每位玩家当前手牌。完美信息蒸馏的思路是针对这种非完美问题,构建一个第三方角色,该角色可以看到三位玩家的手牌,该角色在不告知每位玩家完美信息的情况下通过信息蒸馏的方式引导玩家打出当前情况下合理的出牌。 以强化学习常用的 Actor-Critic 算法为例,PTIE 在 Actor-Critic 算法的应用中可以利用 Critic 的 Value 输出作为蒸馏手段来提升 Actor 的表现。具体而言即在训练中 Critic 的输入为完美信息(包含所有玩家的手牌信息),Actor 的输入为非完美信息(仅包含自己手牌信息),此种情况下 Critic 给予的 Value 值包含了完美信息,可以更好地帮助 Actor 学习到更好的策略。 从更新公式上来看,正常的 Actor-Critic 算法 Actor 更新的方式如下: 在 PTIE 模式下,对于每个非完美信息状态 h,我们可以在 Critic 中构建对应的完美信息状态 D(h),并用 Critic 的输出来更新 Actor 的策略梯度,从而达到完美信息蒸馏的效果。 PTIE 框架的整体结构如下图所示: 无论是训练还是执行过程中智能体都不会直接使用完美信息,在训练中通过蒸馏将完美信息用于提升策略,从而帮助智能体达到一个更高的强度。 PTIE 的另一种蒸馏方式是将完美信息奖励引入到奖励值函数的训练中,PerfectDou 提出了基于阵营设计的完美信息奖励 node reward,以引导智能体学习到斗地主游戏中的合作策略,其定义如下: 如上所示,完美信息部分 代表 t 时刻地主手牌最少几步可以出完,在斗地主游戏中可以近似理解为是距游戏获胜的距离, 代表 t 时刻地主阵营和农民阵营距游戏获胜的距离之差, 为调节系数。通过此种奖励设计,在训练时既可以一定程度地引入各玩家的手牌信息(出完的步数需要知道具体手牌才能计算),同时也鼓励农民以阵营的角度做出决策,提升农民的合作性。 特征构建: PerfectDou 针对牌类游戏的特点主要构建了两部分特征:牌局状态特征和动作特征。其中牌局状态特征主要包括当前玩家手牌牌型特征、当前玩家打出的卡牌牌型特征、玩家角色、玩家手牌数目等常用特征,动作特征主要用于刻画当前状态下玩家的所有可能出牌,包括了每种出牌动作的牌型特征、动作的卡牌数目、是否为最大动作等特征。 牌型特征为 12 * 15 的矩阵,如下图所示: 该矩阵前 4 行代表对应每种卡牌的张数,5-12 行代表该种卡牌的种类和对应位置。 网络结构和动作空间设计 针对斗地主游戏出牌组合数较多的问题,PerfectDou 基于 RLCard 的工作上对动作空间进行了简化,对占比最大的两个出牌牌型:飞机带翅膀和四带二进行了动作压缩,将整体动作空间由 27472 种缩减到 621 种。 PerfectDou 策略网络结构如下图所示: 策略网络结构同样分为两部分:状态特征部分和动作特征部分。 在状态特征部分,LSTM 网络用于提取玩家的历史行为特征,当前牌局状态特征和提取后的行为特征会再通过多层的 MLP 网络输出当前的状态信息 embedding。 在动作特征部分,每个可行动作同样会经过多层 MLP 网络进行编码,编码后的动作特征会与其对应的状态信息 embedding 经过一层 MLP 网络计算两者间的相似度,并经由 softmax 函数输出对应的动作概率。 实验结果
-
针对任意矩阵的 Strassen 算法的 java 实现
-
基于查理复用算法(Charlie multiplexing algorithm)的 LED 矩阵控制设计
-
推荐的数据结构和算法书籍、视频、项目、网站和预习技巧(2021 年持续更新) ...
-
使用代码和 Netflix 数据的基于用户的电影推荐协作过滤算法(稀疏矩阵
-
玩转云端 | SkyCloud 的边缘安全加速平台 AccessOne 有管理多个产品的实用技巧。一站式平台管理全部搞定!
-
机器学习算法的推导 - 为什么矩阵推导中有 "转置"?
-
直角坐标系潮汐流牛顿计算法雅各布矩阵的推导