C++求解矩阵连乘问题的方法
矩阵连乘问题C++
- 1.认真审阅题目,明确题目的已知条件和求解的目标;
- 2.问题建模
- 3.算法设计;
- 4.编码实现;
1.认真审阅题目,明确题目的已知条件和求解的目标;
给定n个矩阵{A1,A2,A3……,An},其中Ai与Ai+1(i = 1,2 ,3,4……n-1)是可乘的,加括号的方法表示矩阵连乘的次序,不同加括号的方法所对应的计算次序是不同的。
2.问题建模
【例4-2】三个矩阵 A1 A2 A3 连乘,用加括号的方法表示其计算次序。
3个矩阵相乘,其加括号的方法一共有两种,具体如下:
【例4-3】4个矩阵连乘,用加括号的方法表示其计算次序。
4个矩阵连乘,其加括号的方法共有5种,具体如下:
不同加括号的方法所对应的计算量也是不同的,甚至差别很大。由于在矩阵相乘的过程中,仅涉及加法和乘法两种基本运算,乘法耗时远远大于加法耗时,故采用矩阵连乘所需乘法的次数来对不同计算次序的计算量进行衡量。
【例4-4】三个矩阵 A1 ,A2 ,A3 的行列分别为10×100、100×5、5×50,求例4-2中的两种加括号方法所需要乘法的次数。
两种加括号方法所需要乘法的次数分别为
那么,矩阵连乘问题就是对于给定n个连乘的矩阵,找出一种加括号的方法,使得矩阵连乘的计算量最小。
容易想到的解决方法是穷举法,即对n个矩阵连乘的每一种加括号方法进行乘法次数的统计,从中找出最小的计算量所对应的加括号方法。这种方法的复杂性取决于加括号的方法的种数。对于n个矩阵连乘,其加括号的方法有多少种呢?
考查矩阵连乘,不管哪种加括号的方法,最终都归结为两部分结果矩阵相乘,这两部分从n个连乘矩阵中的哪个矩阵处分开呢?设可能从A k 和A k+1 处将n个矩阵分成两部分,其中k=1,2,…,n-1。令P(n)代表n个矩阵连乘不同的计算次序,即不同加括号的方式,则n个矩阵连乘加括号的方式可通过两步操作来实现:①分别完成对两部分加括号;②对所得的结果加括号。由此
解此递推方程可得P(n)实际上是Catalan数,即P(n)=C(n-1),其中 。故穷举法的复杂性非常高,是n的指数级函数,显然,该方法不可行。
3.算法设计;
采用自低向上的方法求解最优质的具体的求解步骤设计如下:
步骤1:确定合适的数据结构,采用二维数组m来存放各个子问题的最优值,二维数组来存放来存放各个子问题的最优策略,(如果s[i][j]=k,则最优加括号的 方法为(Ai……Ak)(Ak+1……,Aj),一维数组P
步骤2:初始化。令m[i][j] = 0 , s[i][j] = 0,其中 i = 1, 2, ……
步骤3:循环阶段
步骤3-1:按照递归关系式计算两个矩阵AiAi+1,相乘时的最优值,并将其存入m[i][i+1],同时将最优决策计入s[i][i+1],i = 1, 2, ……
步骤3-2:按照递归关系式计算3个矩阵AiAi+1Ai+2相乘时的最优值并将其存入m[i][i+2],同时最优决策计入s[1][i+2],i = 1, 2, ……, n – 2
以此类推
步骤3-(n-1):按照递归关系式计算n个矩阵A1,A2,……An相乘时的最优质的并将其存入m[1][n],同时将最优决策计入s[1][n]
至此,m[1][n]即为原问题的最优值
步骤4:根据二维数组s记录的最优决策信息来构造最优解
步骤4-1:递归构造A1,……,As[1][n]的最优解,直到包含一个矩阵结束
步骤4-2:递归构造As[1][n]+1……An的最优解,直到包含一个矩阵结束
步骤4-3:将步骤4-1和步骤4-2递归的结果加括号
4.编码实现;
```cpp
#include <iostream>
using namespace std;
void MatrixChain(int *p, int n, int * * m, int * * s)//用于求最优值
{
//初始化
for(int i = 1; i <= n; i ++){
m[i][i] = 0;
s[i][i] = 0;
}
for(int r = 2; r <= n; r++){//不同规模的子问题
for(int i = 1; i <= n - r + 1; i++){//每一个规模为r的矩阵连乘序列的首矩阵Ai
int j = i + r - 1;//每个规模为r的矩阵连乘序列的尾矩阵为Aj
m[i][j] = m[i+1][j] + p[i-1] * p[i]*p[j];//决策为k=i的乘法次数
s[i][j] = 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;
}
}
}
}
}
void Traceback(int i, int j, int ** s){
//s[i][j]记录了断开的位置,即计算A[i:j]的加括号方式为(A[i:s[i][j]]) * A [s[i][j] + 1: j])
if(i == j) return;
Traceback(i, s[i][j], s);//递归打印A[i:s[i][j]的加括号方式
Traceback(s[i][j] + 1, j, s);//递归打印A[s[i][j]+1:j ]的加括号的方式
cout << "A" << "[" << i << ":" << s[i][j] << "]" << "乘以" << "A""[" << (s[i][j] + 1) << ":" << j << "]"<< endl;
}
int main(){
return 0;
}
## 5.算法分析;
显然,语句int t = m[i][k] + m[k+1][j] + p [i-1= * p[k]*p[j]为算法MatriChain的基本语句,最坏的情况下该语句的执行次数为O(n的三次方)故散发的最坏时间复杂度为O(n的三次方)
9.总结。
上一篇: 搞定矩阵连乘问题的动态规划策略
推荐阅读
-
整数编程问题的建模技术和求解方法汇总-3 求解方法
-
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 函数输出对应的动作概率。 实验结果
-
用 C 语言实现的排列组合问题通用算法、求解方法
-
[姿势估计] 实践记录:使用 Dlib 和 mediapipe 进行人脸姿势估计 - 本文重点介绍方法 2):方法 1:基于深度学习的方法:。 基于深度学习的方法:基于深度学习的方法利用深度学习模型,如卷积神经网络(CNN)或递归神经网络(RNN),直接从人脸图像中学习姿势估计。这些方法能够学习更复杂的特征表征,并在大规模数据集上取得优异的性能。方法二:基于二维校准信息估计三维姿态信息(计算机视觉 PnP 问题)。 特征点定位:人脸姿态估计的第一步是通过特征点定位来检测和定位人脸的关键点,如眼睛、鼻子和嘴巴。这些关键点提供了人脸的局部结构信息,可用于后续的姿势估计。 旋转表示:常见的旋转表示方法包括欧拉角和旋转矩阵。欧拉角通过三个旋转角度(通常是俯仰、偏航和滚动)描述头部的旋转姿态。旋转矩阵是一个 3x3 矩阵,表示头部从一个坐标系到另一个坐标系的变换。 三维模型重建:根据特征点的定位结果,三维人脸模型可用于姿势估计。通过将人脸的二维图像映射到三维模型上,可以估算出人脸的旋转和平移信息。这就需要建立人脸的三维模型,然后通过优化方法将模型与特征点对齐,从而获得姿势估计结果。 特征点定位 特征点定位是用于检测人脸关键部位的五官基础部分,还有其他更多的特征点表示方法,大家可以参考我上一篇文章中介绍的特征点检测方案实践:人脸校正二次定位操作来解决人脸校正的问题,客户在检测关键点的代码上略有修改,坐标转换部分客户见上图 def get_face_info(image). img_copy = image.copy image.flags.writeable = False image = cv2.cvtColor(image, cv2.COLOR_BGR2RGB) results = face_detection.process(image) # 在图像上绘制人脸检测注释。 image.flags.writeable = True image = cv2.cvtColor(image, cv2.COLOR_RGB2BGR) box_info, facial = None, None if results.detections: for detection in results. for detection in results.detections: mp_drawing.Drawing.detection = 无 mp_drawing.draw_detection(image, detection) 面部 = detection.location_data.relative_keypoints 返回面部 在上述代码中,返回的数据是五官(6 个关键点的坐标),这是用 mediapipe 库实现的,下面我们可以尝试用另一个库:dlib 来实现。 使用 dlib 使用 Dlib 库在 Python 中实现人脸关键点检测的步骤如下: 确保已安装 Dlib 库,可使用以下命令: pip install dlib 导入必要的库: 加载 Dlib 的人脸检测器和关键点检测器模型: 读取图像并将其灰度化: 使用人脸检测器检测图像中的人脸: 对检测到的人脸进行遍历,并使用关键点检测器检测人脸关键点: 显示绘制了关键点的图像: 以下代码将参数 landmarks_part 添加到要返回的关键点坐标中。
-
求解线性规划问题(可行解 | 可行域 | 最佳解 | 级的概念 | 极大线性无关组 | 向量级 | 矩阵级 | 基础 | 基础变量 | 非基础变量 | 基础解 | 可行基础 )
-
求解逆矩阵的三种常用方法
-
求解三对角矩阵的追赶法(C/C++/python/matlab/Fortran 90)
-
[原创] 《矩阵连环计》史诗剧三十二集:用矩阵方法求解二元二次方程组的一般形式
-
如何用动态规划方法求解复杂网络的分段最短路线问题
-
在C++中实现无需额外空间的矩阵转置方法