动态规划——矩阵连乘问题
一:问题描述
有 n 个矩阵相乘,构造一个相乘次序,使得乘法的次数最低。用程序写出求
解每个子问题的结果。
二:算法设计与分析
通过分析矩阵相乘,我们直到,其具有最优子结构,即一个最优解包含其子
问题的最优解,而且有很多子问题是要重复计算的,所以我们可以用动态规划
的算法自底向上的进行计算,保存子问题的答案,在后面的计算过程中就可以
直接利用已经得到的答案,通过层层往上就可以得到原问题的结果。
三:源程序
/*********************************************************
programmer: linpder
time: 05.10.22
topic: 动态规划--矩阵相乘。
动态规划的问题还有很多,备忘录方法,最长公共子序列,
凸多边形的最优三角部分等。
*********************************************************/
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
#dene MAX 32767 //定义一个最大值
int a[11]; //存储在连乘时断开的位置.
void nd(int pos[11][11],int s,int e,int &i)
//用递归算法求出断开的位置.
{
int b;
b=pos[s][e];
if(b<s)return ; //如果 b 的值小于 s 的,退出
if(b>e)return ; //如果 b 的值大于 s 的,退出
if(e==s+1)return ; //如果 e 只比 s 大一,退出
a[i]=b;
i++;
nd(pos,s,b,i);
nd(pos,b+1,e,i);