Matrix multiplication (C language)
Reference link: https://blog.csdn.net/qq_32919451/article/details/80643118
Problem description
Given n matrices {A1,A2,..., An}, where Ai and Ai+1 are multiplicative, i=1, 2,..., n-1. How to determine the calculation order of matrix continued product so that the number of times required to calculate matrix continued product according to this order is the least. For example, given that the dimensions of three consecutive multiplication matrices {A1,A2, A3} are 10 * 100100 * 5 and 5 * 50 respectively, using (A1A2)A3, the number of multiplication is 101005 + 10550 = 7500 times, while using A1 (A2A3), the number of multiplication is 100 * 5 * 50 + 10 * 100 * 50 = 75000 times. Obviously, the best order is (A1A2)A3, and the number of multiplication is 7500 times.
Analysis of optimal solution structure
The most difficult part of this problem is to find the optimal substructure. Any bracketed method for the product A1A2... An will divide the sequence into two parts somewhere, that is, where the last multiplication is calculated. We record this position as k, that is, first calculate A1... Ak and Ak+1... An, and then multiply the results of these two parts.
The optimal substructure is as follows: assuming that an optimal bracketing of A1A2... An separates the product between Ak and Ak+1, the bracketing method of prefix sub chain A1... Ak must be an optimal bracketing of A1... Ak, and the suffix sub chain is the same.
We don't know the exact position of k at first. We need to traverse all the positions to ensure that we can find the appropriate k to divide the product.
Establish recursive relationship
Build auxiliary tables to solve overlapping sub problems
From the recursion in the second step, it can be found that there will be many overlapping subproblems in the process of solution. An NX n-dimensional auxiliary table m [n] [n], s[n] [n] can be used to represent the optimal product cost and its partition position k respectively.
Auxiliary tables s[n] [n] can be constructed in two ways:
- One is to fill in the form from bottom to top. This method requires to fill in the solution of the subproblem step by step in an incremental way, that is, first calculate the solution of all matrix chains with length 2, and then calculate the matrix chain with length 3 until length n;
- The other is the memo method of filling in the table from top to bottom. This method initializes each element of the table to a special value (in this problem, the optimal product cost can be set to a maximum value) to represent the solution of the sub problems to be calculated and filled in one by one in the recursive process.
For a group of matrices: A1(30x35),A2(35x15),A3(15x5),A4(5x10),A5(10x20),A6(20x25), the number N is 6
Then the p array holds the number of rows and columns: p={30,35,15,5,10,20,25} has N+1, that is, 7 elements
p[0],p[1] represents the number of rows and columns of the first matrix, p[1],p[2] represents the number of rows and columns of the second matrix... p[5],p[6] represents the number of rows and columns of the sixth matrix
Calculate the optimal value
Construct optimal solution
code implementation
#include <stdio.h>
#include <stdlib.h>
//MAXSIZE is the number of array numbers
#define MAXSIZE 6
#include <limits.h>
int n = MAXSIZE-1;//Number of matrices
int a[MAXSIZE] = {2,3,5,8,6,5};//Global settings content
int t[MAXSIZE][MAXSIZE]; //memorandum
int m[MAXSIZE][MAXSIZE]; //Optimal solution of m[i][j] storage subproblem
int s[MAXSIZE][MAXSIZE]; //s[i][j] optimal partition point of storage subproblem
//Method 1: memo method optimization
int F(int left,int right)
{
int i=0,lefttimes,righttimes,wholetimes;
int min=10000;
int k;
if(left==right) return 0;
if(t[left][right]>0)
{
return t[left][right];
}
for(i=left;i<right;i++)
{
lefttimes = F(left,i);
righttimes = F(i+1,right);
wholetimes = lefttimes+ righttimes+a[left]*a[i+1]*a[right+1];
if(wholetimes < min)
{
min = wholetimes;
}
}
t[left][right] = min;
return min;
}
//Method 2: bottom up
void matrix(int n,int m[][n],int s[][n],int p[])
{
int i,r,k,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
m[i][j]=-1;
}
}
for(i=1;i<=n;i++)
m[i][i]=0; //The minimum subproblem contains only one matrix, and the diagonals are all 0
for(r=2;r<=n;r++)//r represents the length of the matrix (2,3... Gradually longer)
for(i=1;i<=n-r+1;i++)//Row loop
{
int j=i+r-1;//Starting from the ith matrix Ai, the length is r, then the matrix segment is (Ai~Aj)
//Find the smallest of (Ai~Aj). In fact, k should start from i, but first record the first value. k starts from i+1, which is also OK.
//For example, for (A2~A4), i=2,j=4, m[2][4]=m[3][4]+p[1]*p[2]*p[4], that is, A2(A3A4)
m[i][j] = m[i+1][j]+a[i-1]*a[i]*a[j];
s[i][j]=i;//Record the index of the break point
for(int k=i+1;k<j;k++)//Cycle to find the minimum number of decimal multiplication in (Ai~Aj)
{
//Divide the matrix segment (Ai~Aj) into left and right parts (left m[i][k], right m[k+1][j]),
//Plus the number of final multiplication of the left and right parts (p[i-1] *p[k]*p[j])
int t = m[i][k]+m[k+1][j]+a[i-1]*a[k]*a[j];
if(t<m[i][j])
{
m[i][j] = t;
s[i][j] = k;
//Save the smallest, that is, the best result
}
}
}
for(i=1;i<MAXSIZE;i++)
{
for(j=1;j<MAXSIZE;j++)
{
printf("%5d",m[i][j]);
}
printf("\n");
}
printf("Minimum times of matrix multiplication:%d\n",m[1][n]);
for(i=0;i<MAXSIZE;i++)
{
for(j=0;j<MAXSIZE;j++)
{
printf("%5d",s[i][j]);
}
printf("\n");
}
printf("Form of matrix multiplication:");
printmatrix(1,n);
}
//Recursive printout
void printmatrix(int leftindex,int rightindex)
{
if(leftindex==rightindex)
printf("A%d",leftindex);
else{
printf("(");
printmatrix(leftindex,leftindex+s[leftindex][rightindex]);
printmatrix(leftindex+s[leftindex][rightindex]+1,rightindex);
printf(")");
}
}
int main()
{
int i,j,x,p;
for(i=0;i<MAXSIZE;i++)
{
for(j=0;j<MAXSIZE;j++)
{
t[i][j]=0;//Memo reset
}
}
int times = F(0,MAXSIZE-2);
printf("Minimum times of matrix multiplication:%d\n",times);
matrix(n,m,s,a);
return 0;
}
screenshot
