动态规划算法分析与设计实验报告(矩阵连乘)

实验报告4课程数据结构与算法实验名称动态规划(一) 第页班级10计本学号105032010111 姓名陈兴灶实验日期：2012年3月20日报告退发(订正、重做)一、实验目的掌握递归及分治策略的原理和应用。

二、实验环境1、微型计算机一台2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容必做题：1、编程实现矩阵连乘算法，求出最优值及一个最优解。

附加题：1、开车从a到b会经过n个加油站，给定这n个加油站的距离和油价，及汽车耗油量，汽车油箱的容量为v，编程计算从a到b至少需要花费多少油费。

四、实验步骤和结果第一题：矩阵连乘算法package shiyan4;import java.util.Scanner;public class matrixChain {public static int [][]a;public static int [][]b;public static void matrixchain(int []p,int [][]m,int [][]s){int n=p.length-1;for(int i=1;i<n;i++)m[i][i]=0;for(int r=2;r<=n;r++)for(int i=1;i<=n-r+1;i++){int j=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(int k=i+1;k<j;k++){int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}public static void traceback(int [][]s,int i,int j){if(i==j)return ;traceback(s,i,s[i][j]);traceback(s,s[i][j]+1,j);System.out.println("Multiply A"+i+","+s[i][j]+" and A"+(s[i][j]+1)+","+j);}public static void main(String []args){Scanner sc=new Scanner(System.in);System.out.println("输入矩阵个数");int n=sc.nextInt();int []p=new int[n+1];a=new int [n+1][n+1];b=new int [n+1][n+1];System.out.println("输入各矩阵的行数和列数");for(int i=0;i<=n;i++)p[i]=sc.nextInt();matrixchain(p,a,b);System.out.println("最少次数为");System.out.println(a[1][a.length-1]+" ");System.out.println("最优解为");traceback(b,1,n);}}结果：第二题：计算从a到b至少需要花费多少油费package shiyan4;import java.util.Scanner;public class MinPertrolFee {public static float []fee;public static float []distance;public static float v;public static float vh;public static float vs;float money;MinPertrolFee(){Scanner sc=new Scanner(System.in);System.out.println("输入加油站个数");int n=sc.nextInt();fee=new float[n];System.out.println("输入每个加油站油的单价");distance=new float[n];for(int i=1;i<fee.length;i++)fee[i]=sc.nextFloat();System.out.println("输入两两相邻加油站间的距离");for(int i=1;i<distance.length;i++)distance[i]=sc.nextFloat();System.out.println("输入油箱容量");v=sc.nextFloat();System.out.println("输入每公里的耗油量");vh=sc.nextFloat();vs=0;money=0;}public static void minpertrolfee(MinPertrolFee e) {float s=e.v/e.vh,s2;int j,l,k;for(int i=1;i<e.fee.length;i++){float vj=e.distance[i]/e.vh-e.vs;if(vj>0){e.money+=addpertrol(vj,i);e.vs+=vj;}float s1=0;for( j=i;j<e.fee.length&&s>=s1;j++)s1+=e.distance[j];for( l=i,k=i;l<(e.fee.length-1)&&l<=j;l++) {if(e.fee[k]>=e.fee[l+1])break;else continue;}if(l==j&&j!=e.distance.length)s2=e.v/e.vh;else s2=e.distance[l]-e.distance[i];float vj1=s2/e.vh-e.vs;if(vj1>0){e.money+=addpertrol(vj1,i);e.vs+=vj1;}e.vs-=e.distance[i]/e.vh;}System.out.println("所须要最少的钱为"+e.money); }public static float addpertrol(float vj,int i) {return vj*fee[i];}public static void main(String []args){MinPertrolFee e=new MinPertrolFee();minpertrolfee(e);}}结果：五、实验总结1.第二题算法是错的。

一、实验背景动态规划是一种重要的算法设计方法，广泛应用于解决优化问题。

本次实验旨在通过实际操作，加深对动态规划算法的理解，掌握其基本思想，并学会运用动态规划解决实际问题。

二、实验内容本次实验主要包括以下几个内容：1. 动态规划算法概述首先，我们对动态规划算法进行了概述，学习了动态规划的基本概念、特点、应用领域等。

动态规划是一种将复杂问题分解为若干个相互重叠的子问题，并存储已解决子问题的解，以避免重复计算的方法。

2. 矩阵连乘问题矩阵连乘问题是动态规划算法的经典问题之一。

通过实验，我们学会了如何将矩阵连乘问题分解为若干个相互重叠的子问题，并利用动态规划方法求解。

实验过程中，我们分析了问题的最优子结构、子问题的重叠性，以及状态转移方程，从而得到了求解矩阵连乘问题的动态规划算法。

3. 0-1背包问题0-1背包问题是另一个典型的动态规划问题。

在实验中，我们学习了如何将0-1背包问题分解为若干个相互重叠的子问题，并利用动态规划方法求解。

实验过程中，我们分析了问题的最优子结构、子问题的重叠性，以及状态转移方程，从而得到了求解0-1背包问题的动态规划算法。

4. 股票买卖问题股票买卖问题是动态规划在实际应用中的一个例子。

在实验中，我们学习了如何将股票买卖问题分解为若干个相互重叠的子问题，并利用动态规划方法求解。

实验过程中，我们分析了问题的最优子结构、子问题的重叠性，以及状态转移方程，从而得到了求解股票买卖问题的动态规划算法。

三、实验心得1. 动态规划算法的思维方式通过本次实验，我深刻体会到了动态规划算法的思维方式。

动态规划算法的核心是将复杂问题分解为若干个相互重叠的子问题，并存储已解决子问题的解。

这种思维方式有助于我们更好地理解和解决实际问题。

2. 状态转移方程的重要性在动态规划算法中，状态转移方程起着至关重要的作用。

它描述了子问题之间的关系，是求解问题的关键。

通过本次实验，我学会了如何分析问题的最优子结构，以及如何建立合适的状态转移方程。

word设计性实验报告课程名称：《算法分析与设计》实验题目：矩阵连乘问题组长：成员一：成员二：成员三：系别：数学与计算机科学系专业班级：指导教师：实验日期：一、实验目的和要求实验目的熟悉动态规划算法设计思想和设计步骤，掌握基本的程序设计方法，培养学生用计算机解决实际问题的能力。

实验要求1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。

2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。

3、实验项目可以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行实验，要求在学期末形成完整的项目程序设计报告。

二、实验内容提要矩阵连乘问题给定n个矩阵{A1,A2,…,A n}，其中，Ai与Ai+1是可乘的，i=1,2，…，n-1。

考查这n 个矩阵的连乘积A1,A2,…,A n。

由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。

这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。

完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。

三、实验步骤下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。

（1）分析最优解的结构（最优子结构性质）设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解结构特征。

对于矩阵乘积的最优计算次序问题也不例外。

首先，为方便起见，降矩阵乘积Ai Ai+1…Aj简记为A[i:j]。

考查计算A[1：n]的最优计算次序。

设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1<=k<n,则其相应的完全加括号方式为（（A1…Ak）（Ak+1…An））即依此次序，先计算A[1：k]和A[k+1：n]，然后将计算结果相乘得到A[1：n]。

算法设计与分析——矩阵连乘问题（动态规划）⼀、问题描述引出问题之前我们先来复习⼀下矩阵乘积的标准算法。

int ra,ca;//矩阵A的⾏数和列数int rb,cb;//矩阵B的⾏数和列数void matrixMultiply(){for(int i=0;i<ra;i++){for(int j=0;j<cb;j++){int sun=0;for(int k=0;k<=ca;k++){sum+=a[i][k]*b[k][j];}c[i][j]=sum;}}}给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。

如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是10*100，100*5和5*50，采⽤（A1A2）A3，乘法次数为10*100*5+10*5*50=7500次，⽽采⽤A1（A2A3），乘法次数为100*5*50+10*100*50=75000次乘法，显然，最好的次序是（A1A2)A3，乘法次数为7500次。

加括号的⽅式对计算量有很⼤的影响，于是⾃然地提出矩阵连乘的最优计算次序问题，即对于给定的相继n个矩阵，如何确定矩阵连乘的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

⼆、问题分析矩阵连乘也是Catalan数的⼀个常⽤的例⼦，关于时间复杂度的推算需要参考离散数学关于Catalan的内容。

下⾯考虑使⽤动态规划法解矩阵连乘积的最优计算次序问题。

1、分析最优解的结构问题的最优⼦结构性质是该问题可以⽤动态规划求解的显著特征！！！2、建⽴递归关系3、计算最优值public static void matrixChain(int n) {for (int i = 1; i <= n; i++) {m[i][i] = 0;}for (int r = 2; r <= n; r++) {//i与j的差值for (int i = 1; i <= n - r + 1; i++) {int j = i + r - 1;m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];s[i][j] = i;for (int k = i + 1; k < j; k++) {int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];if (t < m[i][j]) {m[i][j] = t;s[i][j] = k;}}}}}4、构造最优解public static void traceback(int i, int j) {if (i == j) {System.out.printf("A%d", i); // 输出是第⼏个数据return;}System.out.printf("(");traceback(i, s[i][j]);// 递归下⼀个数据System.out.printf(" x ");traceback(s[i][j] + 1, j);System.out.printf(")");}三、总结。

南京信息工程大学滨江学院实验（实习）报告1.实验目的动态规划通常用来求解最优化问题。

通过本次实验掌握动态规划算法。

通过矩阵连乘问题和0-1背包问题实现动态规划算法。

学会刻画问题的最优结构特征，并利用最优化问题具有的重叠子问题性质，对每个子问题求解一次，将解存入表中，当再次需要这个子问题时直接查表，每次查表的代价为常量时间。

2.实验内容及分析设计过程1.矩阵链乘法问题矩阵链乘法问题可描述如下：给定个矩阵的链,矩阵的规模为，求完全括号方案，使得计算乘积所需的标量乘法次数最少。

令m[i,j]表示计算矩阵所需标量乘法次数的最小值，那么，原问题的最优解计是m[1,n］。

最小代价括号化方案的递归求解公式为采用自底向上表格法代替上述递归算法来计算最优代价。

为了实现自底向上方法，我们必须确定计算m[i,j]时需要访问哪些其他表项。

上述公式显示，j-i+l 个矩阵链相乘的最优计算代价m[i,j] 只依赖于那些少于j-i+l 个矩阵链相乘的最优计算代价。

因此，算法应该按长度递增的顺序求解矩阵链括号化问题，并按对应的顺序填写表m。

对如下输入A1 A2 A3 A4 A5 A630⨯35 35⨯15 15⨯5 5⨯10 10⨯20 20⨯25程序运行结果为2.背包问题给定n 个重量为价值为的物品和一个承重为W 的背包。

求这些物品中最有价值的一个子集，并且要能装到背包中。

设V[i,j]是能够放进承重量为j 的背包的前i 个物品中最有价值子集的总价值。

则递推关系为初始条件V[0,j]=0(j>=0),V[i,0]=0(i>=0) 我们的目标是求V[n ，W]。

递归式给出了V[i,j]的计算顺序，V[i,j]只依赖与前一行的那些项。

故可以逐行计算V[i,j].对于物品数量n=5，w[n]={2,2,6,5,4},v[n]={6,3,5,4,6},背包总重量c=10 程序运行结果为3. 实验小结通过本次实验加深了我对动态规划算法的理解。

福州大学数学与计算机科学学院《计算机算法设计与分析》上机实验报告（2）i<=k<j,则：m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj。

由于在计算是并不知道断开点k的位置，所以k还未定。

不过k的位置只有j-i个可能。

因此，k是这j-i个位置使计算量达到最小的那个位置。

综上，有递推关系如下：若将对应m[i][j]的断开位置k记为s[i][j]，在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解。

s[i][j]中的数表明，计算矩阵链A[i:j]的最佳方式应在矩阵Ak和Ak+1之间断开，即最优的加括号方式应为(A[i:k])(A[k+1:j)。

从s[1][n]记录的信息可知计算A[1:n]的最优加括号方式为(A[1:s[1][n]])(A[s[1][n]+1:n])，进一步递推，A[1:s[1][n]]的最优加括号方式为(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]] )。

同理可以确定A[s[1][n]+1:n]的最优加括号方式在s[s[1][n]+1][n]处断开...照此递推下去，最终可以确定A[1:n]的最优完全加括号方式，及构造出问题的一个最优解。

3、动态规划迭代算法设计：用动态规划迭代方式解决此问题，可依据其递归式自底向上的方式进行计算。

在计算过程中，保存已解决的子问题的答案。

每个子问题只计算一次，而在后面需要时只需简单检查一下，从而避免了大量的重复计算，最终得到多项式时间的算法。

4、算法代码：1.//3d1-2 矩阵连乘动态规划迭代实现2.//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*253.//p[0-6]={30,35,15,5,10,20,25}4.#include "stdafx.h"5.#include <iostream>ing namespace std;7.8.const int L = 7;9.10.int MatrixChain(int n,int **m,int **s,int *p);11.void Traceback(int i,int j,int **s);//构造最优解12.13.int main()14.{15.int p[L]={30,35,15,5,10,20,25};16.17.int **s = new int *[L];18.int **m = new int *[L];19.for(int i=0;i<L;i++)20. {21. s[i] = new int[L];22. m[i] = new int[L];23. }24.25. cout<<"矩阵的最少计算次数为："<<MatrixChain(6,m,s,p)<<endl;26. cout<<"矩阵最优计算次序为："<<endl;27. Traceback(1,6,s);28.return 0;29.}30.31.int MatrixChain(int n,int **m,int **s,int *p)32.{33.for(int i=1; i<=n; i++)34. {35. m[i][i] = 0;36. }37.for(int r=2; r<=n; r++) //r为当前计算的链长（子问题规模）38. {39.for(int i=1; i<=n-r+1; i++)//n-r+1为最后一个r链的前边界40. {41.int j = i+r-1;//计算前边界为r，链长为r的链的后边界42.43. m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];//将链ij划分为A(i) * ( A[i+1:j] )44.45. s[i][j] = i;46.47.for(int k=i+1; k<j; k++)48. {49.//将链ij划分为( A[i:k] )* (A[k+1:j])50.int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];51.if(t<m[i][j])52. {53. m[i][j] = t;54. s[i][j] = k;55. }56. }57. }58. }59.return m[1][L-1];60.}61.62.void Traceback(int i,int j,int **s)63.{64.if(i==j) return;65. Traceback(i,s[i][j],s);66. Traceback(s[i][j]+1,j,s);67. cout<<"Multiply A"<<i<<","<<s[i][j];68. cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;69.}上述迭代算法的运行过程如下图所示：当R=2时，先迭代计算出： m[1:2]=m[1:1]+m[2:2}+p[0]*p[1]*p[2]；m[2:3]=m[2:2]+m[3:3]+p[1]*p[2]*p[3];。

一、实验目的通过本次实验，加深对动态规划算法的理解和应用，掌握解决矩阵连乘问题的方法，提高算法分析和设计能力。

二、实验原理矩阵连乘问题是指给定n个矩阵，每个矩阵都与它的前一个矩阵可乘，求计算这些矩阵连乘积的最优计算次序，以使计算过程中所需的数乘次数最少。

由于矩阵乘法满足结合律，因此可以通过加括号的方式确定不同的计算次序。

三、实验步骤1. 问题描述：给定n个矩阵A1, A2, ..., An，其中Ai与Ai-1是可乘的。

求计算矩阵连乘积A1A2...An的最优计算次序，使得计算过程中所需的数乘次数最少。

2. 输入数据：矩阵个数n，每个矩阵的规模。

3. 输出结果：计算矩阵连乘积的最优计算次序和最少数乘次数。

4. 算法设计：- 定义一个二维数组m[i][j]，其中m[i][j]表示计算矩阵AiAi-1...Aj的最少数乘次数。

- 初始化m[i][i] = 0，因为单个矩阵无需计算。

- 对于每个子问题A[i:j]，计算m[i][j]的最小值：- 遍历k从i到j-1，将问题分解为A[i:k]和Ak+1:j，计算m[i][k]和m[k+1][j]的和，并加上k个矩阵的维度乘积。

- 取上述和的最小值作为m[i][j]的值。

5. 递归关系：- 当i = j时，m[i][j] = 0。

- 当i < j时，m[i][j] = min(m[i][k] + m[k+1][j] + p[i-1]p[k]p[j])，其中k从i到j-1，p[i-1]表示矩阵Ai-1的行数，p[j]表示矩阵Aj的列数。

6. 自底向上计算：- 从m[1][1]开始，按照递归关系计算m[1][2]，m[1][3]，...，m[1][n]。

- 然后计算m[2][3]，m[2][4]，...，m[2][n]，以此类推，直到计算m[1][n]。

7. 输出最优计算次序：- 从m[1][n]开始，根据递归关系和子问题的最优解，逐步确定每个子问题的最优计算次序，直到得到整个问题的最优计算次序。

一、实验背景与目的矩阵连乘问题是一个经典的算法问题，它涉及给定一系列矩阵，确定这些矩阵的最佳乘积顺序，以最小化乘法操作的次数。

本实验旨在通过动态规划算法解决矩阵连乘问题，加深对动态规划方法的理解，并提高算法分析与设计的能力。

二、实验内容与步骤1. 问题描述与理解：- 给定n个矩阵A1, A2, ..., An，其中任意两个相邻矩阵都是可乘的。

- 目标是确定计算这些矩阵连乘积的最佳顺序，以最小化所需的乘法次数。

2. 算法分析：- 使用动态规划方法，通过将问题分解为子问题并存储子问题的解来求解。

- 设定m[i, j]表示矩阵Ai到Aj的最佳乘积顺序的乘法次数。

3. 动态规划过程：- 初始化m[i, i] = 0，因为单个矩阵不需要乘法。

- 对于长度为k的矩阵序列，通过遍历所有可能的分割点，计算m[i, j]的最小值。

- 具体步骤包括：- 对于每个可能的k（1 ≤ k ≤ n-1），- 对于每个起始矩阵i（1 ≤ i ≤ n-k），- 计算m[i, i+k-1]和m[i+k, j]，- 更新m[i, j]为m[i, i+k-1] + m[i+k, j] + p[i-1] p[i] p[i+k]。

4. 代码实现：- 使用C或Java等编程语言实现动态规划算法。

- 编写辅助函数来计算矩阵的乘法次数。

三、实验结果与分析1. 实验结果：- 通过实验，成功实现了矩阵连乘问题的动态规划算法。

- 得到了计算给定矩阵序列连乘积所需的最小乘法次数。

2. 结果分析：- 动态规划方法有效地解决了矩阵连乘问题，避免了穷举法的指数级时间复杂度。

- 通过分析子问题的解，我们可以找到整个问题的最优解。

四、实验总结与反思1. 实验收获：- 加深了对动态规划方法的理解，特别是如何通过子问题的解来构建整个问题的解。

- 学会了如何将实际问题转化为动态规划问题，并使用代码实现算法。

2. 反思与展望：- 实验过程中遇到了一些挑战，如理解子问题的定义和计算最优子结构的策略。

矩阵链乘法（动态规划）
⼀题意描述：
给定由n个要相乘的矩阵构成的序列（链）<A1,A2,A3,····A n>。

由于矩阵满⾜结合律（加括号⽅式表⽰结合⽅式），不同的计算⽅式导致的求出最终计算结果的代价相异，有的花的时间很少，有的⽅式所花时间很多，那么下⾯的任务就是求出算出结果所需要的最少时间及⼀个最优解。

⼆思路分析：
设p(n)表⽰⼀串n个矩阵可能的加全部括号⽅案数。

当n=1时，只有⼀个矩阵，此时p(1)=1。

当n>=2时，⼀个加全部括号的矩阵乘积等于两个加全部括号的⼦矩阵乘积的乘积，⽽且这两个⼦乘积之间的分裂可能发⽣在第k个和第k+1个矩阵之间，其中k=1，2，····，n-1;因此可以求得递归式：
1.找局部最优解：把问题：转化成两个最优⼦问题：及
2.构造递归解：
⾸先定义m[i,j]为解决⼦问题A[i....j]的最⼩计算次数，那么解决整个问题A[1,n]所花的最⼩时间为m[1,n]。

那么递归⽅程可以写成如下形式：
为了跟踪如何构造⼀个最优解我们可以定义s[i,j]为这样的⼀个k值，在该处分裂乘积后可得⼀个最优解。

3.构造函数进⾏求解
输出最优路径的函数⾃⼰编写，经过调⽤数组s[i][j]即可。