搞定矩阵连乘问题的巧妙算法设计方法
白天什么也没学,晚上才终于拿着笔,对着代码,写写画画,终于看明白是怎么计算的了。
以这6个矩阵连乘作为例子
A1 | A2 | A3 | A4 | A5 | A6 |
30*35 | 35*15 | 15*5 | 5*10 | 10*20 | 20*25 |
1 首先,要明白两个矩阵相乘所需要做的乘法次数:
2 由于连乘的矩阵必须满足,前一个矩阵的列数=后一个矩阵的行数,所以可以使用一个数组来存储连乘矩阵的行列数:
p[7]={30,35,15,5,10,20,25};
3 分析最优解的结构:
A[i:j]表示矩阵i到矩阵j的连乘,那么A[i:j]=A[i:k]+A[k+1:j]+p[i-1]*p[k]*p[j](这两个矩阵相乘所需的乘法次数);
如果A[i:j]的所需要的乘法次数是最少的,那么A[i:k]和A[k+1:j]所需要的乘法次数也应该是最少的,否则A[i:j]就不是最优的,所以满足最优子结构性质;
4 建立递归关系:
m[i][j]表示矩阵i连乘到矩阵j的最少乘次数,那么原问题的最优值是m[1,n];
当i=j时,为单个矩阵,m[i][i]=0;
当i<j时,利用最优子结构性质来计算;
获得以下递归定义:
m[i][j]=0; i=j
m[i][j]=mini<=k<j{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]}; i<j
如果需要得出最优解的加括号结果,需要另一个二维数组s[i][j],用于记录使m[i][j]获得最优解的断点,k值;
5 分析代码
1 int m[8][8]={0},s[8][8]={0}; 2 3 void MaxtrixChain(int *p,int n){ 4 for(int i=1;i<=n;i++) m[i][i]=0; 5 for(int r=2;r<=n;r++) 6 for(int i=1;i<=n-r+1;i++){ 7 int j=i+r-1; 8 m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; 9 s[i][j]=i; 10 11 for(int k=i+1;k<j;k++){ 12 int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; 13 if(t<m[i][j]){ 14 m[i][j]=t; 15 s[i][j]=k; 16 } 17 } 18 } 19 }
书上写了“依据其递归式自底向上的方式进行计算”,没拿出笔画之前,我真的没看懂这句话到底是怎么自底向上的,于是我要开始写写画画了;
我们先暂时只看下面这部分代码:
void MaxtrixChain(int *p,int n){ for(int i=1;i<=n;i++) m[i][i]=0; for(int r=2;r<=n;r++){ for(int i=1;i<=n-r+1;i++){ int j=i+r-1; m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; }
} }
具体用数据分析一下
把右图补充完整,将得到以下结果:这是我理解的自底向上地计算;
接下来看另一部分代码:
for(int r=2;r<=n;r++){ for(int i=1;i<=n-r+1;i++){ int j=i+r-1; 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; } } } }
所以我们需要把这两部分代码结合起来使用:
那么对于m[1][4]我们是枚举了所有加括号的可能情况,并存储了其中最小的一个,获得了最优值;
那么对于m[2][5]、m[3][6]也能得到最优值;并且没有做任何重复计算;
当r=5时,m[1][5]、m[2][6]也能得到最优值;
当r=6时,m]1][6]也能得到最优值;如此就得到了原问题的最优解;
每一次得到更小值的时候,s[i][j]=k,记录(更新)这个断点情况;最后可以用来帮助构造最优解的加括号形式;
6 以下给出完整源代码:
1 #include<iostream> 2 using namespace std; 3 4 //矩阵连乘:完全加括号问题 5 //A1(p1*p2),A2(p2*p3),两个矩阵相乘,总乘法次数为p1*p2*p3,其中p2表示结果的每个元素所需要的乘法次数 6 //m[i][j]表示,第i个矩阵到第j个矩阵的连乘,所需要的乘法次数 7 //对于多个矩阵连乘,可以得出以下递推式 8 //m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j] 9 //问题是如何找到这个k,使乘法次数最少 10 int m[7][7]={0}; //m[i][j]用于存储,第i个矩阵连乘到第j个矩阵的乘法次数,那么m[1][n]为最终结果 11 int s[7][7]={0}; //s[i][j]用于存储,矩阵i和矩阵j之间所取的断点,k值,用于构造结果的加括号情况 12 13 void MatrixChain(int n,int p[]){ 14 for(int i=1;i<=n;i++) m[i][i]=0; //单个矩阵乘法次数为0 15 16 //采用自底向上的方式实现递推式 17 for(int r=2;r<=n;r++){ //表示r个矩阵的连乘 18 for(int i=1;i<=n-r+1;i++){ //从第i个矩阵开始,作为连乘的起点,有r个矩阵连乘,所以要<=n-r+1 19 int j=i+r-1; //j-i=r-1,表示j是r个矩阵连乘中的终点 20 m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; 21 //相当于m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j],显然m[i][i]=0 22 //即表示Ai……Aj=Ai(Ai+1……Aj),从最后一个开始加括号 23 s[i][j]=i; 24 25 for(int k=i+1;k<j;k++){ 26 int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; //在i~j中寻找k 27 if(t<m[i][j]){ 28 m[i][j]=t; //记录t历史上的最小值,最终结果即为连乘中的最优值 29 s[i][j]=k; //记录断点k值 30 } 31 } 32 33 } 34 } 35 } 36 37 //利用s[i][j]进行构造连乘的加括号情况 38 void TraceBack(int i,int j){ 39 if(i==j) return; 40 TraceBack(i,s[i][j]); //以s[i][j]记录的k为分界点,找左边,i~k 41 TraceBack(s[i][j]+1,j); //找右边,k+1~j 42 cout<<"Matrix A"<<i<<","<<s[i][j]; 43 cout<<" and A"<<s[i][j]+1<<","<<j<<endl; 44 } 45 46 int main(){ 47 int arr[7]={30,35,15,5,10,20,25}; 48 int n=6; 49 MatrixChain(n,arr); 50 TraceBack(1,n); 51 cout<<m[1][n]<<endl; 52 system("pause"); 53 return 0; 54 }
哇本渣终于弄清楚矩阵连乘了!!
推荐阅读
-
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 函数输出对应的动作概率。 实验结果
-
搞定矩阵连乘问题:动态规划的巧妙应用
-
搞定矩阵连乘的算法技巧
-
搞定0010算法!探究【动态规划】在矩阵连乘问题中的应用
-
C++求解矩阵连乘问题的方法
-
搞定矩阵连乘问题的动态规划策略
-
搞定矩阵连乘问题的巧妙算法设计方法
-
搞定矩阵连乘问题的动态规划策略
-
搞定矩阵连乘的DP方法