首页 > 代码库 > 算法13---动态规划矩阵链乘法
算法13---动态规划矩阵链乘法
算法13---动态规划矩阵链乘法
矩阵链乘法是动态规划里面使用到的一个例子
1 两个矩阵的计算
那么对于一个矩阵的乘法，首先如果是两个矩阵的乘法，那么如何实现呢？
注意到我们使用二维数组表示矩阵，但是二维数组不能作为函数的返回值。具体实现如下
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <math.h> 4 5 #define a_rows 3 6 #define a_columns 4 7 #define b_rows 4 8 #define b_columns 3 9 10 void matrix_multiply(int a[a_rows][a_columns],int b[b_rows][b_columns],int c[a_rows][b_columns])11 {12 if (a_columns!=b_rows)13 {14 printf("error!can‘t figure the answer!\n");15 }16 for (int i = 0; i < a_rows; i++)17 {18 for (int j = 0; j < b_columns; j++)19 {20 c[i][j]=0;21 for (int k = 0; k< a_columns; k++)22 {23 c[i][j]=c[i][j]+a[i][k]*b[k][j];24 }25 }26 }27 }28 29 int main()30 {31 32 printf("it is a easy matrix \n");33 34 int a[a_rows][a_columns]={{1,1,1,1},{2,2,2,2},{3,3,3,3}};35 int b[b_rows][b_columns]={{1,1,1},{2,2,2},{3,3,3},{4,4,4}};36 int c[a_rows][b_columns]={0};37 matrix_multiply(a,b,c);38 for (int i = 0; i < 3; i++)39 {40 for (int j = 0; j < 3; j++)41 {42 printf("%d \n",c[i][j]);43 if (j==2)44 {45 printf("\n");46 }47 }48 }49 return 0;50 }
2 矩阵链问题
问题描述
给定n个矩阵构成的一个链<A1,A2,A3,.......An>，其中i=1,2,...n，矩阵A的维数为pi-1pi，对乘积 A1A2...An 以一种最小化标量乘法次数的方式进行加全部括号。
换句话说，就是在矩阵链乘问题中，实际上并没有把矩阵相乘，目的是确定一个具有最小代价的矩阵相乘顺序。找出这样一个结合顺序使得相乘的代价最低。
一般的过程如下
（1）最优括号话方案的结构特征
假设AiAi+1....Aj的一个最优加全括号把乘积在Ak和Ak+1之间分开，则Ai..k和Ak+1..j也都是最优加全括号的。
（2）一个递归求解方案
设m[i,j]为计算机矩阵Ai...j所需的标量乘法运算次数的最小值，对此计算A1..n的最小代价就是m[1,n]。现在需要来递归定义m[i,j]，分两种情况进行讨论如下：
当i==j时：m[i,j] = 0，（此时只包含一个矩阵）
当i<j 时：从步骤1中需要寻找一个k（i≤k＜j）值，使得m[i,j] ＝min{m[i,k]+m[k+1,j]+pi-1pkpj} （i≤k＜j）。
（3）计算最优代价
我们不采用递归实现，而是自下向上的借助辅助空间保存中间量实现；
（4）构造一个最优解
具体的实现过程如下面所示
还没有调好，主要是二维数组不能作为返回值
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define N 6 5 #define MAXVALUE 999999 6 7 void recursive_matrix_chain(int *p,int i,int j,int m[N+1][N+1],int s[N+1][N+1]); 8 int memoized_matrix_chain(int *p,int m[N+1][N+1],int s[N+1][N+1]); 9 int lookup_chain(int *p,int i,int j,int m[N+1][N+1],int s[N+1][N+1]); 10 11 //我们首先采用递归来实现 12 void recursive_matrix_chain(int *p,int i,int j,int m[N+1][N+1],int s[N+1][N+1]) 13 { 14 if (i==j) 15 { 16 m[i][j]=0; 17 } 18 else 19 { 20 int k; 21 m[i][j]=MAXVALUE; 22 for (int k = i; k < j; k++) 23 { 24 int temp=recursive_matrix_chain(p,i,k,m,s)+recursive_matrix_chain(p,k+1,j,m,s)+p[i-1]*p[k]*p[j]; 25 if (temp<m[i][j]) 26 { 27 m[i][j]=temp; 28 s[i][j]=k; 29 } 30 } 31 32 } 33 } 34 35 //因为递归的计算量太大，所以我们可以采用备忘录的方法，自顶向下实现 36 37 int memoized_matrix_chain(int *p,int m[N+1][N+1],int s[N+1][N+1]) 38 { 39 40 for (int i = 1; i <=N; ++i) 41 { 42 for (int j = 0; j <=N; ++j) 43 { 44 m[i][j]=MAXVALUE; 45 } 46 } 47 return lookup_chain(p,1,N,m,s); 48 } 49 50 int lookup_chain(int *p,int i,int j,int m[N+1][N+1],int s[N+1][N+1]) 51 { 52 if (m[i][j]<MAXVALUE) 53 { 54 return m[i][j]; 55 } 56 if (i==j) 57 { 58 m[i][j]=0; 59 } 60 else 61 { 62 for (int k = i; i < j; ++k) 63 { 64 int temp=lookup_chain(p,i,k,m,s)+lookup_chain(p,k+1,j,m,s)+p[i-1]*p[k]*p[j]; 65 if (temp<m[i][j]) 66 { 67 s[i][j]=k; 68 } 69 } 70 } 71 return m[i][j]; 72 } 73 74 75 void print_optimal_parens(int s[N+1][N+1],int i,int j) 76 { 77 if (i==j) 78 { 79 printf("A%d\n",i); 80 } 81 else 82 { 83 printf("("); 84 print_optimal_parens(s,i,s[i][j]); 85 print_optimal_parens(s,s[i][j]+1,j); 86 printf(")"); 87 } 88 } 89 90 int main() 91 { 92 int p[N+1] = {30,35,15,5,10,20,25}; 93 int m[N+1][N+1]={0}; 94 int s[N+1][N+1]={0}; 95 int i,j; 96 memoized_matrix_chain(p,N+1,m,s); 97 printf("m value is: " ); 98 99 for(i=1;i<=N;++i)100 {101 for(j=1;j<=N;++j)102 printf("%d ",m[i][j]);103 printf("\n");104 printf("s value is: \n");105 106 for(i=1;i<=N;++i)107 {108 for(j=1;j<=N;++j)109 printf("%d ",s[i][j]);110 printf("\n");111 }112 printf("the result is:\n");113 print_optimal_parents(s,1,N);114 return 0;115 }
现在再给出一个c++的版本，一个实现，我是看的别人的，自己可以修改
1 #include <iostream> 2 using namespace std; 3 4 #define N 6 5 #define MAXVALUE 1000000 6 7 void matrix_chain_order(int *p,int len,int m[N+1][N+1],int s[N+1][N+1]); 8 void print_optimal_parents(int s[N+1][N+1],int i,int j); 9 10 int main()11 {12 int p[N+1] = {30,35,15,5,10,20,25};13 int m[N+1][N+1]={0};14 int s[N+1][N+1]={0};15 int i,j;16 matrix_chain_order(p,N+1,m,s);17 cout<<"m value is: "<<endl;18 for(i=1;i<=N;++i)19 {20 for(j=1;j<=N;++j)21 cout<<m[i][j]<<" ";22 cout<<endl;23 }24 cout<<"s value is: "<<endl;25 for(i=1;i<=N;++i)26 {27 for(j=1;j<=N;++j)28 cout<<s[i][j]<<" ";29 cout<<endl;30 }31 cout<<"The result is:"<<endl;32 print_optimal_parents(s,1,N);33 return 0;34 }35 36 void matrix_chain_order(int *p,int len,int m[N+1][N+1],int s[N+1][N+1])37 {38 int i,j,k,t;39 for(i=0;i<=N;++i)40 m[i][i] = 0;41 for(t=2;t<=N;t++) //当前链乘矩阵的长度42 {43 for(i=1;i<=N-t+1;i++) //从第一矩阵开始算起，计算长度为t的最少代价44 {45 j=i+t-1;//长度为t时候的最后一个元素46 m[i][j] = MAXVALUE; //初始化为最大代价47 for(k=i;k<=j-1;k++) //寻找最优的k值，使得分成两部分k在i与j-1之间48 {49 int temp = m[i][k]+m[k+1][j] + p[i-1]*p[k]*p[j];50 if(temp < m[i][j])51 {52 m[i][j] = temp; //记录下当前的最小代价53 s[i][j] = k; //记录当前的括号位置，即矩阵的编号54 }55 }56 }57 }58 }59 60 //s中存放着括号当前的位置61 void print_optimal_parents(int s[N+1][N+1],int i,int j)62 {63 if( i == j)64 cout<<"A"<<i;65 else66 {67 cout<<"(";68 print_optimal_parents(s,i,s[i][j]);69 print_optimal_parents(s,s[i][j]+1,j);70 cout<<")";71 }72 73 }
算法13---动态规划矩阵链乘法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。