一．问题描述：

给出一个矩阵链（A1A2A3.......An），确定相乘顺序，使得乘法执行次数最小（因为矩阵链相乘，计算量主要集中在标量乘法的个数上，所以乘法执行次数最小，也就是程序总体执行时间最小）。

 

二．解题思路：

当n=1时，乘法顺序已定；当n>1时，问题（A1A2A3.......An）的最优乘法次序可等价为确定一个k值（1<=k<=n-1），（A1.......Ak）和（Ak+1.......An）的最优乘法次序，再加上两者相乘代价。这是一种递归思想，解题时采用动态规划思想，自底向上，保留子问题解，用以解决问题解。

 

三．动态规划步骤：

步骤一：确定最优解结构（用子问题的解定义问题的解）。

假设Ai.....j是AiAi+1....Aj最优解，若i<=k<=j-1，Ai.....j=Ai.....k*Ak+1.....j ，则Ai.....k是AiAi+1....Ak最优解，Ak+1.....j是Ak+1....Aj最优解。（证明可使用反证法）

步骤二：递归定义最优解的值（本质上就是将步骤一数据化，便于实现；用子问题最优解的值定义问题最优解的值）。

假设m[i][j]是计算Ai.....j的标量乘法次数，m[i][k]是计算Ai.....k的标量乘法次数，m[k+1][j]是计算Ak+1.....j的表量乘法次数，见书上公式15.7

在计算m[i][j]时，m[i][k]和m[k+1][j]都是已知的（类数学归纳法）。

步骤三：自底向上计算最优解的值。（设计部分）

即是自底向上填写m[i][j]，并填写辅助数组s[i][j]，s[i][j]记录的是计算m[i][j]时所采用的k值。（说明整个动态规划思想是一种递归思想，类似与数学归纳法，步骤一和步骤二相当于数学归纳法的第二步，而计算m[i][i]相当于数学归纳法的第一步。）

步骤四：构造最优解。（设计部分）

利用辅助数组s[i][j]构造问题最优解。

 

四．代码实现：

 

#include "stdio.h"

//功能函数声明

void print_arr(int *p,int row,int col);

int matrix_chain_order(int *A,int M[6][6],int S[6][6]);

void init_arr(int *p,int row,int col);

void print_optimal_parents(int S[6][6],int i,int j);

//主函数

int main(void)

{

int A[7] = {30,35,15,5,10,20,25};

int M[6][6],S[6][6];

init_arr((int *)M,6,6);

init_arr((int *)S,6,6);

matrix_chain_order(A,M,S);

printf("M array is:\n");

print_arr((int *)M,6,6);

printf("S array is:\n");

print_arr((int *)S,6,6);

printf("optimal order parent:\n");

print_optimal_parents(S,0,5);

printf("\n");

return 0;

}

///////////////////////////////////////////////////

1.功能：打印指定的二维数组

2.参数：二维数组名，行数，列数

3.返回值：无

4.性能：时间O(row*col)，空间O(1)

////////////////////////////////////////////////////

void print_arr(int *p,int row,int col)

{

int i,j;

for(i = 0; i < row; i++)

{

for(j = 0; j < col; j++)

{

printf("d ",*(p+i*col+j));

}

printf("\n");

}

}

////////////////////////////////////////////////////

1.功能：把二维数组初始化为0

2.参数：二维数组名，行数，列数

3.返回值：无

4.性能：时间O(row*col)，空间O(1)

////////////////////////////////////////////////////

void init_arr(int *p,int row,int col)

{

int i,j;

for(i = 0; i < row; i++)

{

for(j = 0; j < col; j++)

{

*(p+i*col+j) = -1;

}

}

}

////////////////////////////////////////////////////

1.功能：初始化M数组和S数组

2.参数：记录矩阵维数的一维名，M数组，S数组

3.返回值：无错返回0

4.性能：时间O(n3)，空间O(1)

////////////////////////////////////////////////////

int matrix_chain_order(int *A,int M[][6],int S[][6])

{

int i,j,l,k,maxk;

//初始化长度为1的矩阵乘积代价

for(i = 0; i < 6; i++)

{

M[i][i] = 0;

}

for(l = 2; l <= 6; l++) //l表示相乘矩阵数目

{

for(i = 0; i <= 5-l+1; i++) //i表示待乘矩阵链中相乘第一个矩阵，同时表示M和S数组的第一维

{

j = i+l-1; //j表示待乘矩阵链中相乘最后一个矩阵，同时表示M和S数组的第二维

M[i][j] = 10000000; //10000000表示一个极大数，必须保证大于M数组中任何一个数

for(k = i; k < j; k++) //用k遍历第i到第j个矩阵

{

maxk = M[i][k] + M[k+1][j] + A[i] * A[k+1] * A[j+1]; //计算在k处划分时，矩阵相乘的计算代价

if(maxk < M[i][j]) //选取最小代价值，记录到M[i][j]中，并记录S[i][j]

{

M[i][j] = maxk;

S[i][j] = k;

}

}

}

}

return 0;

}

////////////////////////////////////////////////////

1.功能：打印最优加括号

2.参数：记录打印次序的二维方阵名S,S的行最小值和行最大值

3.返回值：无

4.性能：时间O(n)，空间O(1)（不包括递时，系统使用的栈空间）

////////////////////////////////////////////////////

void print_optimal_parents(int S[6][6],int i,int j)

{

if(i == j)

{

printf("A%d",i);

}

else

{

printf("(");

matrix_print_parent(S,i,S[i][j]);

matrix_print_parent(S,S[i][j]+1,j);

printf(")");

}

}