#include
#include
#include
usingstd::cout;
usingstd::endl;
int main()
{
int p[]={30,35,15,5,10,20,25}; //p[0],p[1]确定A1行列数，p[1],p[2]确定A2行列数，依次类推
int n=sizeof(p)/sizeof(int)-1; //自动计算矩阵个数，增加程序灵活性
inti,j,k,r;
long **m=new long*[n+1]; int **s=new int*[n+1];
for(i=0;i<=n;i++) m[i]=new long[n+1]; //m 行列数n*n，下标都从1开始
for(i=0;i<=n;i++) s[i]=new int[n+1]; //s 行列数n*n，下标都从1开始
for(i=0;i<=n;i++) m[i][i]=s[i][i]=0; // 矩阵初始化
// 给以下程序加上注解
for (r = 2; r <= n; r++) /* 数组相乘个数*/
for (i = 1; i <= n - r+1; i++) /* n行里每行要求得的值的个数*/
{
j=i+r-1; /* 相乘数组中最后数组的列指针*/
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; /* 得到两个数组相乘的运算量*/
s[i][j] = i;
for (k = i+1; k < j; k++) /* 加括号方法得到的组数*/
{
long 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; /* 括号分割的位置*/
}
}
}
//输出矩阵m与s的上三角阵，结果应与图（b）、（c）一致,你的代码写在下面！
//此处为你的输出矩阵m与s的上三角阵的代码！
cout<<"图(b)显示结果如下："< for(i=0;i<=n;i++) { if (i==0) { cout<<"\t"; } else { cout< } } cout< for (i=1;i<=n;i++) { cout< for (int j=1;j<=n;j++) { if (m[i][j]>=0) { cout< } else { cout<<"\t"; } } cout< } cout<<"图(c)显示结果如下："< { if (i==0) { cout<<"\t"; } else { cout< } } cout< for (i=1;i<=n;i++) { cout< for (int j=1;j<=n;j++) { if (s[i][j]>=0) { cout< } else { cout<<"\t"; } } cout< } return 0; } 动态规划算法原理及其应用研究 系别：x x x 姓名：x x x 指导教员： x x x 2012年5月20日 摘要：动态规划是解决最优化问题的基本方法，本文介绍了动态规划的基本思想和基本步骤，并通过几个实例的分析，研究了利用动态规划设计算法的具体途径。关键词：动态规划多阶段决策 1.引言 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数 矩阵连乘最佳加括号方式－动态规划算法 一、问题描述 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。 为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵 {A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,A n}（其中矩阵A i的维数为p i-1×p i，i＝1,2,…,n），如何确定计算矩阵连乘积A1A2…A n的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。 二、算法思路 动态规划——矩阵连乘的问题 《问题的引出》 看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次 按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次 所以问题是：如何确定运算顺序，可以使计算量达到最小化。 枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，次数为卡特兰数,卡特兰数指数增长，必然不行。 《建立递归关系》 子问题状态的建模（很关键）：令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。 显然如果i=j，则m[i][j]这段中就一个矩阵，需要计算的次数为0； 如果i>j，则m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]Xp[k]Xp[j]},其中k,在i与j 之间游荡，所以i<=k 所以计算顺序如上右图：相应的计算顺序对应代码为13-15行 m[1][n]即为最终求解，最终的输出想为（（A1（A2 A3））（（A4 A5）A6））的形式，不过没有成功，待思考... 1#include 矩阵连乘问题（动态规划） 一、实验目的与要求 1、明确矩阵连乘的概念。 2、利用动态规划解决矩阵连乘问题。 二、实验题： 问题描述： 给定n个矩阵｛A1,A2,...,An｝，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 三、实验代码 #include 矩阵连乘问题《算法分析与设计》 设计性实验报告 课程名称：《算法分析与设计》矩阵连乘问题实验题目：长：组员一：成 二：成员成员三：数学与计算机科学系别：系专业班级：指导教师：实验日期： 一、实验目的和要求 实验目的 熟悉动态规划算法设计思想和设计步骤，掌握基 本的程序设计方法，培养学生用计算机解决实际问题的能力。 实验要求 1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。 2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。 3、实验项目可 以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行 实验，要求在学期末形成完整的项目程序设计报告。 二、实验内容提要 矩阵连乘问题给定n个矩阵{A,A,…,A}， 其中，Ai与Ai+1是可乘的，n21A,A,…,A。由于矩阵乘法满足结n-1。考查这n个矩阵的连乘积i=1,2，…，n12合律，故计算矩阵的连乘积可以有 许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反 复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可 递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。 三、实验步骤下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。（1）分析最优解的结构（最优子结构性质）设计求解具体问题的动态规划算法的第一步是刻画该问 题的最优解结构特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为方便起见，降- 1 - 矩阵乘积Ai Ai+1…Aj简记为A[i:j]。 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 问题描述：给定n个矩阵：A1,A2,...,A n，其中A i与A i+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 问题解析：由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC) 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：(A1(A2(A3A4)))，(A1((A2A3)A4))，((A1A2)(A3A4))，((A1(A2A3))A4)，(((A1A2)A3)A4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。 看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数 ((A1*A2)*A3):10X100X5+10X5X50=7500次，按此顺序计算需要的次数(A1*(A2*A3)):10*5*50+10*100*50=75000次 所以问题是：如何确定运算顺序，可以使计算量达到最小化。 算法思路： 例：设要计算矩阵连乘乘积A1A2A3A4A5A6，其中各矩阵的维数分别是： A1：30*35; A2：35*15; A3：15*5; A4：5*10; A5：10*20; A6：20*25 递推关系： 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。 当i=j时，A[i:j]=A i，因此，m[i][i]=0，i=1,2,…,n 当i 六、附录 A #include { if((c[j][r]+cost[r]) 一、问题描述给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr次数乘。为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,An}（其中矩阵Ai的维数为pi-1×pi，i ＝1,2,…,n），如何确定计算矩阵连乘积A1A2…An的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。 二、算法思路动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。本实验的算法思路是： 1、计算最优值算法MatrixChain()：建立两张表（即程序中的**m和**s，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另 目录： 矩阵连乘问题： 1. 描述矩阵连乘问题 2. 分析矩阵连乘问题以及对递归式的推导（1）直接递归思路 （2）备忘录思路 （3）动态规划思路 3. 伪代码的方式描述算法： （1）直接递归算法 （2）备忘录算法 （3）动态规划算法 4. 把算法转换成程序实现的过程及结果（1）直接递归算法程序 （2）备忘录算法程序 （3）动态规划算法程序 1.描述矩阵连乘问题： 给定n 个矩阵{n A A A ?,2,1}，其中i A 和1+i A 是可乘的，i=1,2,…,n-1。考察这n 个矩阵的连乘积n A A A ?,2,1。由于矩阵乘法具有结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说连乘积已完全加括号，则可依次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘B 和C 的乘积并加括号，即A=（BC ）。 矩阵A 和B 可乘的条件是矩阵A 的列数等于矩阵B 的行数。若A 是一个p ×q 的矩阵，B 是一个q ×r 的矩阵，那么C=A ×B 就是一个p ×r 矩阵。它的计算是三重循环的，计算量是pqr 。如果加括号后矩阵的量是不同的，所以我们的问题就是要讨论如何给连乘的矩阵加括号才能使矩阵的计算量最少。 穷举搜索法：对于n 个矩阵的连乘积，设有不同的计算次序P(n)。由于可以先在第k 个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,...,n-1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。由此可得P(n)的递归式如下： 1 n=1 P （n ）= ∑-=-1 1 )()(n k k n P k P n>1 解此递归方程可得，P(n)=C(n-1),而C(n)是一个指数增长的函数。因此穷举搜索法不是一个有效的算法。以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。 2. 分析矩阵连乘问题以及对递归式的推导 将矩阵连乘积j i i A A A ?+,1,简记为A[i:j]。考察计算A[1:n]的最优计算次序。这个问题的一个关键特征是：计算A[1:n]的最优次序包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。这是因为：定义矩阵A i 的维数为p i-1×p i ,则A[i:k]的计算次数为p i-1×p k ，A[k+1,j]的计算次数为p k ×p j ，而这两个总的矩阵最后相乘时的计算量是固定的，为p i-1×p k ×p j 。所以，矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 （1）、直接递归的思路：记计算A[i:j]，1≤i ≤j ≤n ，所需最少数乘次数为m[i][j],则原问题的最优质为m[1][n]。由分析得知：m[i][j]可以递归的定义为： 0 i=j m[i][j]= }]][1[]][[{min 1j k i j k i p p p j k m k i m -≤≤+++ i 《算法设计与分析》课程报告 课题名称：动态规划——编辑距离问题 课题负责人名（学号）： 同组成员名单（角色）：无 指导教师：左劼 评阅成绩： 评阅意见： 提交报告时间：2010年 6 月 23 日 动态规划——编辑距离问题 计算机科学与技术专业 学生指导老师左劼 [摘要]动态规划的基本思想与分治法类似，也是将待求解的问题分解成若干份的子问题，先分别解决好子问题，然后从子问题中得到最终解。但动态规划中的子问题往往不是相互独立的，而是彼此之间有影响，因为有些子问题可能要重复计算多次，所以利用动态规划使这些子问题只计算一次。将字符串A变换为字符串所用的最少字符操作数称为字符串A到B的编辑距离。 关键词：动态规划矩阵字符串操作数编辑距离 一、问题描述 1、基本概念：设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。字符串操作包括： (1) 删除一个字符； (2) 插入一个字符； (3) 将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A 到B的编辑距离，记为d(A,B)。 2、算法设计：设计一个有效算法，对于给定的任意两个字符串A 和B，计算其编辑距离d(A,B)。 3、数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行为字符串A，第二行为字符串B。 4、结果输出：将编辑距离d(A,B)输出到文件ouput.txt的第一行。 输入文件示例输出文件示例 input.txt output.txt fxpimu 5 xwrs 二、分析 对于本问题，大体思路为：把求解编辑距离分为字符串A从0个字符逐渐增加到全部字符分别想要变为字符串B该如何变化以及变化的最短距离。 具体来说，首先选用数组a1存储字符串A(设长度为n)，a2存储字符串B(设长度为m)，d矩阵来进行具体的运算；这里有两个特殊情况比较简单可以单独考虑，即A的长度为0而B不为0还有A不为0B为0，这两种情况最后的编辑距离分别为m和n；讨论一般情况，d矩阵为d[n][m]，假定我们从d[0][0]开始一直进行以下操作到了d[i][j]的位置，其中删除操作肯定是A比B长，同理，插入字符操作一定是A比B短，更改字符操作说明一样长，我们所要做的是对d[i][j-1] 华北电力大学科技学院 实验报告 实验名称矩阵连乘问题 课程名称计算机算法设计与分析 专业班级：软件12K1 学生姓名：吴旭 学号：121909020124 成绩： 指导老师：刘老师实验日期：2014.11.14 一、实验内容 矩阵连乘问题，给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A1,A2,…,A n。 二、主要思想 由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为： (1)单个矩阵是完全加括号的； (2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号 的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行 1、分析最优解的结构 设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在A k和A k+1之间将矩阵链断开，1n,则其相应的完全加括号方式为((A1…A k)(A k+1…A n))。依此次序，先计算A[1:k]和A[k+1:n],然后将计 算结果相乘得到A[1:n]。 2、建立递归关系 设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A[i:j]，1i n，所需的最少数乘次数为m[i][j]，原问题的最优值为m[1][n]。 当i=j时，A[i:j]=A i为单一矩阵，无需计算，因此m[i][i]=0，i=1,2,…n。 当i 动态规划法解矩阵连乘问题 实验内容 给定n个矩阵{A1,A2,….An}，其中Ai与Ai+1是可乘的，i=1,2,3。。。，n-1。我们要计算这n个矩阵的连乘积。由于矩阵乘法满足结合性，故计算矩阵连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则我们可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 解题思路 将矩阵连乘积A(i)A(i+1)…A(j)简记为A[i:j]，这里 i <= j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵A(k)和A(k+1)之间将矩阵链断开，i <= k < j, 则其相应完全加括号方式为(A(i)A(i+1)…A(k)) * (A(k+1)A(k+2)…A(j))。 特征：计算A[i: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] = m[i,k] + m[k+1,j] + p(i-1)p(k)p(j)这里A(i)的维数为 p(i-1)*(i)(注：p(i-1)为矩阵A(i)的行数，p(i)为矩阵A[i]的列数) 实验 实验代码 #include 动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 三、实验步骤 （1）需求分析 通过动态规划法解决数塔问题。从顶部出发，在每一节点可以选择向下或者向右走，一直走到底层，以找出一条数值最大的路径。 （2）概要设计 本次实验程序主要用到二维数组，以及通过动态规划法进行比较每个数的大小。主要运用两个for循环语句实现动态规划。 （3）详细设计 第一步，输入给定的二维数组并打印出相应的数组： int array[5][5]={{9}, /* */{12,15}, /* */{10,6,8}, /* */{2,18,9,5}, /* */{19,7,10,4,6}}; int i,j; for(i=0;i<5;i++) { for(j=0;j<5;j++) cout< 动态规划算法解矩阵连乘问题 一、实验目的 通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。 二、实验环境 VC6.0 C++，vs2005 三、实验内容 1 用动态规划算法解矩阵连乘问题 （1）问题的描述 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的（当然实际上可以不加）； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B 是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,A n}（其中矩阵Ai的维数为p i-1×p i，i＝1,2,…,n），如何确定计算矩阵连乘积A1A2…A n的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。正如课堂中所分析，穷举法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。 （2）算法设计思想 动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 实验标题 1、矩阵连乘 2、最长公共子序列 3、最大子段和 4、凸多边形最优三角剖分 5、流水作业调度 6、0-1背包问题 7、最优二叉搜索树 实验目的掌握动态规划法的基本思想和算法设计的基本步骤。 实验内容与源码1、矩阵连乘 #include 动态规划讲解大全 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型 多阶段决策过程的最优化问题。 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大. 无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。 解决方法：动态规划算法原理与的应用
矩阵连乘最佳加括号方式-动态规划算法
矩阵连乘(数据结构)
矩阵连乘问题(动态规划)
矩阵连乘问题算法分析与设计
南京邮电大学算法设计实验报告——动态规划法
动态规划矩阵连乘算法
动态规划算法分析实验报告
矩阵连乘问题
矩阵连乘问题
算法设计动态规划(编辑距离)
矩阵连乘实验报告
动态规划法解矩阵连乘问题
动态规划算法的应用
动态规划算法解矩阵连乘问题
动态规划算法实验报告
动态规划讲解大全含例题及答案
相关主题
文本预览