矩阵连乘

矩阵AB可乘的条件是矩阵A的列数等于矩阵B的行数

计算时,加括号方式,对计算量的影响很大

穷举搜索法:来搜索可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘最少的计算次序

                              1 分析最优解的结构                                    

关键特征:计算A[1:n]的最优次序所包含的计算矩阵子链A[1:k]和 A[k+1:n]的次序也是最优的。

                              2 建立递归关系                                          

当i=j时:m[i][j] = 0;

当i<j时,m[i][j] = m[i][k]+ m[k+1][j]+pi-1pkpj

                              3 计算最优值                                            

时间复杂度O(n^3)   空间复杂度O(n^2)

                              4 构造最优解                                            

。。。

代码:

#include<iostream>
using namespace std;
const int MAX = 100;
 //p用来记录矩阵的行列,main函数中有说明
 //m[i][j]用来记录第i个矩阵至第j个矩阵的最优解
 //s[][]用来记录从哪里断开的才可得到该最优解
int p[MAX+1],m[MAX][MAX],s[MAX][MAX];
int n;//矩阵个数
 
void matrixChain(){
     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 = r+i-1;//列的控制
             //找m[i][j]的最小值,先初始化一下,令k=i
             m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
             s[i][j]=i;
             //k从i+1到j-1循环找m[i][j]的最小值
             for(int k = i+1;k<j;k++)
             {
                 int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                 if(temp<m[i][j])
                 {
                     m[i][j]=temp;
                     //s[][]用来记录在子序列i-j段中,在k位置处
                     //断开能得到最优解
                     s[i][j]=k;
                 }
             }
         }
 }
 
 //根据s[][]记录的各个子段的最优解,将其输出
 void traceback(int i,int j){
     if(i==j)return ;
 
     traceback(i,s[i][j]);
     traceback(s[i][j]+1,j);
     cout<<"Multiply A"<<i<<","<<s[i][j]<<"and A"<<s[i][j]+1<<","<<j<<endl;
 }
 
 int main(){
     cin>>n;
     for(int i=0;i<=n;i++)cin>>p[i];
     //测试数据可以设为六个矩阵分别为
     //A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25]
     //则p[0-6]={30,35,15,5,10,20,25}
     //输入:6 30 35 15 5 10 20 25
     matrixChain();
 
     traceback(1,n);
     //最终解值为m[1][n];
     cout<<m[1][n]<<endl;
     return 0;
 }

测试结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏kalifaの日々

MATLAB学习笔记

who whos format long format short format bank format rat pi i exp() log() log10(...

2713
来自专栏人人都是极客

三天速成 TensorFlow课件分享

这是一套香港科技大学发布的极简 TensorFlow 入门教程,三天全套幻灯片教程已被分享到 Google Drive。机器之心将简要介绍该教程并借此梳理 Te...

4769
来自专栏华章科技

三天速成!香港科技大学TensorFlow课件分享

该教程第一天先介绍了深度学习和机器学习的潜力与基本概念,而后便开始探讨深度学习框架 TensorFlow。首先我们将学到如何安装 TensorFlow,其实我们...

1172
来自专栏数据结构与算法

圆的反演变换

挺神奇的东西,网上没有多少资料,我也不是太懂,代码什么的都没写过,那就抄一下百度百科吧

1382
来自专栏有趣的Python

9- 深度学习之神经网络核心原理与算法-全连接网络GPU实现

4472
来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(十一)——分类方法之决策树

一、分类方法简介 1. 分类的概念         数据挖掘中分类的目的是学会一个分类函数或分类模型(也常常被称作分类器),该模型能把数据库中的数据项映射到给定...

32610
来自专栏和蔼的张星的图像处理专栏

图像旋转即c++实现

主要还是考虑面试的时候会不会用到,刚才好好看了下旋转的这个思路,其实和图像缩放的思路差不多的,主要的问题是要找到坐标的映射方式。 因为还是包含了一部分的公式,...

2864
来自专栏文武兼修ing——机器学习与IC设计

使用numpy构建多层感知机目标其他组件网络训练与测试

import numpy as np 目标 使用numpy实现多层感知机的正向和反向传播 层次构建 全连接层 正向传播 正向传播的公式为:$Y = f(W \t...

36711
来自专栏机器之心

三天速成!香港科技大学TensorFlow课件分享

机器之心整理 参与:蒋思源 这是一套香港科技大学发布的极简 TensorFlow 入门教程,三天全套幻灯片教程已被分享到 Google Drive。机器之心将简...

55312
来自专栏机器学习算法与Python学习

Torch7模型训练

Torch7搭建卷积神经网络详细教程已经详细的介绍啦Module模块,这里再次基础上再给出一些上Container、 Transfer Functions La...

38713

扫码关注云+社区

领取腾讯云代金券