动态规划程序设计
实验目的:掌握并实现动态规划算法。
实验内容:对维数为序列(5,10,3,12,5,50,6)的各矩阵。找出其矩阵链乘的一个最优加全括号。
实验要求:利用动态规划思想写出算法的伪代码和 C 程序代码
(一)算法思想
穷举所有的计算次序,且对每一计算次序确定其乘法次数。由此可找出 n 个矩阵进行连乘积 A1A2…An 的
最小乘法次数。
将矩阵链乘积简记为 A[i:j] ,这里 i≤j
考察计算 A[i:j]的最优计算次序。设这个计算次序在矩阵 Ak 和 Ak+1 之间将矩阵链断开,i≤k<j,则其相应
完全加括号方式为
计算量:A[i:k]的计算量加上 A[k+1:j]的计算量,再加上 A[i:k]和 A[k+1:j]相乘的计算量
设计算 A[i:j],1≤i≤j≤n,所需要的最少数乘次数 m[i,j],则原问题的最优值为 m[1,n]
当 i=j 时,A[i:j]=Ai,因此,m[i,i]=0,i=1,2,…,n
当 i<j 时,
可以递归地定义 m[i,j]为:
k 位置只有 j-i 种可能
(二)程序代码
//动态规划
import java.io.*;
public class Testsuanfa {
public final int len = this.GetN()+1;
public int[] A = new int[len];
public double[][] M = new double[len][len];
public double[][] S = new double[len][len];
//取得用户需要规划的矩阵连乘的个数。
public int GetN(){
int dvalue = 0;
String value;
System.out.println("请输入连乘矩阵个数: ");
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
try {
value = bfr.readLine();
dvalue =Integer.parseInt(value);
//捕捉输入异常
} catch (IOException e) {
System.out.println("输入出错了,请重新输入:");
System.exit(0);
}catch (NumberFormatException e2) {
System.out.println("请输入正确的数字!!");
System.exit(0);
}