搞定矩阵连乘的DP方法
最优二叉查找树的一道思考习题
同最优二叉查找树一样,矩阵连乘问题也是一个卡特兰数问题(其动态规划的构造过程都很像)
分析解答:
a,铺垫的数学知识首先要搞清楚矩阵相乘是怎么乘的:
1)对于连续的n个矩阵相乘 A1 * A2 *A3.........An,其乘法顺序可以是任意的,可以在上面加括号,改变做乘法的顺序,例如 A*B*C三个矩阵相乘可以A*(B*C)
也可以直接按从左到右的顺序。连续的两个矩阵的位数必须满足m*p,p*n才能相乘,且相乘后的结果是个m*n的矩阵。(线性代数的知识)
2)对于2个m*p,p*n的矩阵相乘,共做乘法次数为 m*n*p 次。这是预备知识,知道矩阵连续的乘法的运算次数跟运算顺序有关后,就很容易举出例子了,略。
b,卡特兰数个,证明很麻烦,有时间看了组合数学再来看
c,重点是要解决这个问题。
设M[i , j]表示从第 i 个矩阵到第 j 个矩阵连乘的最少乘法次数,(i 从 0 编号),我们最终的目标是求 M[0 , n-1]。
Ai *.......Ak * Ak+1.....Aj
假设要得到这个式子的值(即从矩阵 i 连乘到矩阵 j),所作的最后一个矩阵乘法是在矩阵 k 后(注意准确的描述位置)断开的(即左右都已乘运算好),那么容易得到
其递推式:
M[i , j] = min{ M[i , k] + M[k+1 , j] + p[i - 1] * p[ k ] * p[ j ] } i <= k <= j-1
其中 di 是矩阵 Ai 的第一维,dk+1是断开处矩阵 Ak 的第二维(即Ak+1的第一维,是一样的),dj+1是最后一个矩阵 Aj 的第二维。
得到这个式子也是一个逆向思维的过程。
可以用矩阵连乘的动态规划构造过程与最优二叉查找树比较下,发现其构造非常相似(在前面一篇dp之什么叫做professional中提到过,不再详述)
实现:
初始条件:M[i , i] = 0
填表顺序:鉴于其递推式与最优二叉查找树相似,填表顺序也是按对角线的,自己画画就知道了。
代码也跟最优二叉查找树的控制逻辑相似:
package Section8;
/*第八章 动态规划 课后习题:矩阵连乘*/
public class MatEven {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] Dim = {30,35,35,15,15,5,5,10,10,20,20,25};
int result = MatEven(Dim);
System.out.println("\n动态规划求的的最优策略相乘顺序导致的最少乘法数为:" + result);
}
public static int MatEven(int[] Dim){
//接受n个矩阵的维度数组Dim大小为2n
int n = Dim.length / 2; //有n个矩阵,编号0...n-1,编号为k的矩阵的维数是Dim[2k] * Dim[2k+1]
int[][] Result = new int[n][n]; //最小代价矩阵
//初始化
for(int i = 0;i < n;i++)
Result[i][i] = 0;
//沿对角线填矩阵
for(int d = 1;d <= n-1;d++) //共n-1条对角线需要填
{
for(int i = 0;i <= n-d-1;i++) //第d条对角线的第一个点横坐标为d
{
//int j = i - d;
int j = i + d; //在第d条对角线上的点,横纵坐标的关系是j = i + d
//这样就确定了一个位置(i,j)的坐标,然后来填(i,j)
int Min = 1000000000;
for(int k = i;k <= j-1;k++) //从第k个矩阵后面断开
{
//动态规划状态转移方程
int temp = Result[i][k] + Result[k+1][j] + (Dim[2*i] * Dim[2*k + 1] * Dim[2*j+1]);
if( temp < Min)
Min = temp;
}
Result[i][j] = Min;
}
}
return Result[0][n-1];
}
}
上面用一个数组接受一个连乘的矩阵的维数,
例如连乘的矩阵维数是:30*3535*1515*55*1010*2020*25
用动态规划求解得到的最佳乘法次数是:
动态规划求的的最优策略相乘顺序导致的最少乘法数为:15125
直接返回矩阵的话就可以得到整个M[i , j]的值
如果按照从左到右的顺序做乘法,是远远不止这个次数的。
-------------------------------------------------------------------------
当然,再做一些处理,就还可以得到具体的次序,类似于最优二叉查找树,就是要记录动态规划产生的过程,略
----------------------------------------------------------------------------------------------
总结:
矩阵连乘问题是个卡特兰数问题
其动态规划的构造过程非常类似于最优二叉查找树
矩阵连乘的最有子结构是什么?
本文转自农夫山泉别墅博客园博客,原文链接:http://www.cnblogs.com/yaowen/p/4466268.html,如需转载请自行联系原作者
下一篇: 搞定矩阵连乘问题的动态规划策略
推荐阅读
-
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 函数输出对应的动作概率。 实验结果
-
实现矩阵键盘扫描的两种方法(带程序)
-
读取 Numpy 矩阵中某一列的方法以及数组与矩阵相互转换的示例
-
[姿势估计] 实践记录:使用 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 添加到要返回的关键点坐标中。
-
[机器学习中的矩阵推导] (2) 矩阵矢量推导(定义方法)
-
[机器学习中的矩阵推导] (2) 矩阵矢量推导(定义方法)
-
全国 370 个城市的空间权重矩阵和计算方法、城市点坐标、城市路网、城市兴趣点
-
最简单的QQ透明头像设置方法(小白教程)几分钟搞定
-
Python 2D 矩阵 行和列转置的多种实现方法
-
稀疏矩阵的 toarray 和 todense 方法。