首页 > 代码库 > 算法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...A以一种最小化标量乘法次数的方式进行加全部括号。
  换句话说,就是在矩阵链乘问题中,实际上并没有把矩阵相乘,目的是确定一个具有最小代价的矩阵相乘顺序。找出这样一个结合顺序使得相乘的代价最低。
 
一般的过程如下
(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---动态规划矩阵链乘法