_实验2动态规划法

格式：pdf
大小：187.54 KB
文档页数：3

下载文档原格式

动态规划法,回溯法,分支限界法求解TSP问题实验报告

TSP问题算法实验报告指导教师：****名：***学号：**********提交日期：2015年11月目录总述 (2)动态规划法 (3)算法问题分析 (3)算法设计 (3)实现代码 (3)输入输出截图 (6)OJ提交截图 (6)算法优化分析 (6)回溯法 (6)算法问题分析 (6)算法设计 (7)实现代码 (7)输入输出截图 (9)OJ提交截图 (9)算法优化分析 (10)分支限界法 (10)算法问题分析 (10)算法设计 (10)实现代码 (10)输入输出截图 (15)OJ提交截图 (15)算法优化分析 (15)总结 (16)总述TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮力法，动态规划法…具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。

动态规划法算法问题分析假设n个顶点分别用0~n-1的数字编号，顶点之间的代价存放在数组mp[n][n]中，下面考虑从顶点0出发求解TSP问题的填表形式。

首先，按个数为1、2、…、n-1的顺序生成1~n-1个元素的子集存放在数组x[2^n-1]中，例如当n=4时，x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}。

设数组dp[n][2^n-1]存放迭代结果，其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP问题的算法如下。

算法设计输入：图的代价矩阵mp[n][n]输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度1.初始化第0列（动态规划的边界问题）for(i=1;i<n;i++)dp[i][0]=mp[i][0]2.依次处理每个子集数组x[2^n-1]for(i=1;i<n;i++)if（子集x[j]中不包含i）对x[j]中的每个元素k，计算d[i][j]=min{mp[i][k]+dp[k][j-1]};3.输出最短路径长度。

算法实验报告

实验一分治与递归算法的应用一、实验目的1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。

2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。

3．学会利用分治算法解决实际问题。

二 . 实验内容金块问题老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。

假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。

并对自己的程序进行复杂性分析。

三.问题分析:一般思路：假设袋中有n 个金块。

可以用函数M a x（程序1 - 3 1）通过n-1次比较找到最重的金块。

找到最重的金块后，可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。

这样，比较的总次数为2n-3。

分治法：当n很小时，比如说，n≤2，识别出最重和最轻的金块，一次比较就足够了。

当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。

第二步，分别找出在A和B中最重和最轻的金块。

设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。

第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。

在第二步中，若n＞2，则递归地应用分而治之方法程序设计据上述步骤，可以得出程序1 4 - 1的非递归代码。

该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。

当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。

首先处理n≤1的情况。

若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶,数个重量值w [ 1 : n - 1 ]参与f o r循环。

当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。

算法设计与分析课程教学大纲

算法设计与分析课程教学大纲【适用专业】计算机科学与技术【课时】理论课时：32【学分】 2【课程性质、目标和要求】《算法设计与分析》是计算机科学与技术专业的专业课。

无论是计算科学还是计算实践，算法都在其中扮演着重要角色。

本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。

课程基本要求是⑴掌握算法分析的基本概念和理论。

⑵掌握算法设计技术和分析算法以及算法复杂性。

【教学时间安排】本课程计 2 学分，理论课时32, 学时分配如下：【教学内容要点】第一章算法引论一、学习目的要求1．了解算法的计算复杂性分析方法2．理解算法分析的基本理论3．掌握算法分析的基本概念二、主要教学内容1. 算法的基本概念2. 表达算法的抽象机制3. 采用Java语言与自然语言相结合的方式描述算法的方法4. 算法的计算复杂性分析方法第二章递归与分治策略一、学习目的要求1．理解典型范例中递归与分治策略应用技巧2．掌握递归与分治策略3．掌握数学归纳法证明算法正确性方法二、主要教学内容1. 递归的概念2. 分治法的基本思想3. 二分搜索技术4. 大整数的乘法5. Strassen阵乘法6. 棋盘覆盖7. 合并排序8. 快速排序9. 线性时间选择10. 最接近点对问题11. 循环赛日程表第三章动态规划一、学习目的要求1．理解典型范例中动态规划算法的设计思想2．掌握动态规划算法的基本要求以及算法的设计要点二、主要教学内容1. 矩阵连乘问题2. 动态规划算法的基本要素3. 最长公共子序列4. 最大子段和5. 凸多边形最优三角剖分6. 多边形游戏7. 图像压缩8. 电路布线9. 流水作业调度10. 0—l背包问题11. 最优二叉搜索树12. 动态规划加速原理三、课堂讨论选题1. 最长公共子序列2. 0—l背包问题第四章贪心算法一、学习目的要求1．了解贪心算法的理论基础及基本要素2. 理解典型范例中贪心算法的设计思想3. 掌握贪心算法的设计要点二、主要教学内容1. 活动安排问题2. 贪心算法的基本要素3. 最优装载4. 哈夫曼编码5. 单源最短路径6. 最小生成树7. 多机调度问题8. 贪心算法的理论基础三、课堂讨论选题1. 最优装载2. 单源最短路径第五章回溯法一、学习目的要求1．理解回溯法的效率分析方法2．掌握回溯法的算法框架和应用技巧二、主要教学内容1. 回溯法的算法框架2. 装载问题3. 批处理作业调度4. 符号三角形问题5. n后问题6. 0—l背包问题7. 最大团问题8. 图的m着色问题9. 旅行售货员问题10. 圆排列问题11. 电路板排列问题12. 连续邮资问题13. 回溯法的效率分三、课堂讨论选题1. 0—l背包问题2. 图的m着色问题第六章分支限界法一、学习目的要求1．理解分支限界法的基本思想2．掌握典型范例中分支限界法的应用技巧二、主要教学内容1. 分支限界法的基本思想2. 单源最短路径问题3. 装载问题4. 布线问题5. 0-1背包问题6. 最大团问题7. 旅行售货员问题8. 电路板排列问题9. 批处理作业调度三、课堂讨论选题1. 0-1背包问题2. 批处理作业调度第七章概率算法一、学习目的要求1．理解概率算法的基本思想2．掌握典型范例中概率算法的应用技巧二、主要教学内容1. 随机数2. 数值概率算法3. 舍伍德算法4. 拉斯维加斯算法5. 蒙特卡罗算法第八章 NP完全性理论一、学习目的要求1．了解P类与NP类问题2．了解典型的NP完全问题二、主要教学内容1. 计算模型2. P类与NP类问题3. NP完全问题4. 一些典型的NP完全问题第九章近似算法一、学习目的要求1．掌握近似算法的基本思想2．掌握常用近似算法的应用二、主要教学内容1. 近似算法的性能2. 顶点覆盖问题的近似算法3. 旅行售货员问题近似算法4. 集合覆盖问题的近似算法5. 子集和问题的近似算法第十章算法优化策略一、学习目的要求1．掌握算法优化策略2．掌握算法优化的基本方法二、主要教学内容1. 算法优化策略的比较与选择2. 动态规划加速原理3. 问题的算法特征4. 优化数据结构5. 优化搜索策略【教学（实验）内容要点】算法设计与分析实验是算法设计与分析课的一个实践性教学环节。

实验二动态重点规划算法

实验二动态规划算法一、实验目旳与规定1、熟悉最长公共子序列问题旳算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X旳子序列是指存在一种严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}旳子序列，相应旳递增下标序列为{2，3，5，7}。

给定2个序列X和Y，当另一序列Z既是X旳子序列又是Y旳子序列时，称Z 是序列X和Y旳公共子序列。

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y旳最长公共子序列。

三．(1)实验源代码://最长公共子序问题://问题描述: 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，//是X旳子序列是指存在一种严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

//例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}旳子序列，相应旳递增下标序列为{2，3，5，7}。

//给定2个序列X和Y，当另一序列Z既是X旳子序列又是Y旳子序列时，称Z 是序列X和Y旳公共子序列。

//给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y旳最长公共子序列。

#include<bits/stdc++.h>using namespace std;#define max 1000//注意：这里使用旳char数组，可以按字符输出，若改为string类型，//执行printf("%c",A[m-1])就会报错;char A[100],B[100]; //输入旳两个串a和b//这里定义全局变量可以不赋值0，由于全局变量自动赋值0;int c[max][max]; //记录最长公共子序旳长度；int b[max][max]; //记录状态号;void LCS(int m,int n){if(m==0||n==0){return;}else if(b[m][n]==1){LCS(m-1,n-1);printf("%c",A[m-1]);}else if(b[m][n]==2){m=m-1;LCS(m,n);}else if(b[m][n]==3){n=n-1;LCS(m,n);}}void LCS_length(int m,int n){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(A[i-1]==B[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}}int main(){printf("请输入两个待测旳字符串:\n");scanf("%s",&A);scanf("%s",&B);int m=strlen(A); //m为A串长度；int n=strlen(B); //n为B串长度;LCS_length(m,n);printf("其最长公共子序旳长度为:%d\n",c[m][n]);printf("其最长公共子序为:");LCS(m,n);return 0;}(2)运营成果为:(3)算法思路:最长公共子序列旳构造有如下表达：设序列X=<x1, x2, …, x m>和Y=<y1, y2, …, y n>旳一种最长公共子序列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且z k≠x m ，则Z是X m-1和Y旳最长公共子序列；3.若x m≠y n且z k≠y n，则Z是X和Y n-1旳最长公共子序列。

《动态规划法》课件

动态规划法的发展趋势
混合整数动态规划
将整数变量引入动态规划中，解决更复杂的问题，如组合优化问题。
动态规划与机器学习结合
利用机器学习算法辅助动态规划求解，提高算法的效率和准确性。
ABCD
多目标动态规划
考虑多个相互冲突的目标，寻求最优解的权衡。
分布式动态规划
将问题分解为多个子问题，在分布式系统中并行求解，提高大规模问题的处理能力。
排班问题
总结词
动态规划法可以用于解决排班问题，使得员工的工作计划安排最优。
详细描述
排班问题是一个多约束优化问题，涉及到员工的工作时间、班次、休息时间等多个因素。通过构建状态转移方程和优先级规则，动态规划法能够求解出满足所有约束条件的最佳排班方案。
生产调度问题
总结词
动态规划法可以应用于生产调度问题，优化生产流程和资源分配。
策略
一系列决策的集合，表示从初始状态到终止状态的整个求解过程。
转移方程与最优解
转移方程
描述状态转移的数学方程，表示从一个状态转移到另一个状态的关系。
最优解
在所有可能的策略中，能够使目标函数达到最优值的策略。
03
动态规划法的求解步骤
问题的分解
总结词
将复杂问题分解为若干个子问题
详细描述
动态规划法首先将原问题分解为若干个子问题，每个子问题都是原问题的简化版本。通过解决这些子问题，可以逐步推导出原问题的解决方案。
02
动态规划法的基本概念
阶段与状态
01
阶段
将问题的求解过程划分为若干个相互联系的阶段，以便按一定的次序进行求解。
02
03
状态
状态转移
在某一时刻，问题所处的情况或状态。

动态规划实验报告心得

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法分析_综合性设计性实验_动态规划法_实验报告

{
for( i = 0 ; i < n ; i ++ )
{
scanf("%d %d",&T[i].value , &T[i].num );
}
scanf("%d",&m ) ;
sort(T,T+n ,comp );
sum = 0 ;
int k = -1 ;
for( i = n-1 ; i >=0 ; i-- )
写出此问题的解空间，画出正确的解空间树是做好本次实验的关键环节。
若重做本实验，为实现预期效果，仪器操作和实验步骤应如何改善：
因为n越大，所要执行的次数就会迅猛增加，所以机器配置应该更高一点，这样才能保证实验有效进行，因为此实验采用的是两种不同的方法，所以排列树这种实验方法的时间效率会更高。
3）、对实验的自我评价：
小组合作：是○否●
小组成员：
1、实验目的：
1）理解回溯法的深度优先搜索策略
2）掌握用回溯法解题的算法框架
3）针对具体问题，能应用回溯法设计有效算法
4）用C++实现算法，并且分析算法的效率
2、实验设备及材料：
硬件设备：PC机
操作系统：win7
开发工具：vc++6.0
3、实验内容
最少硬币问题
问题描述
设有n种不同面值的硬币，各个硬币的面值存于数组T[1:n]中，现在要用这些面值的硬币来找钱，可以使用的各种面值的硬币个数存于数组Coin[1:n]中。
姓名姓名姓名学号学号学号200908001157?200908001157?200908001157?专业专业专业计算机科学与技术计算机科学与技术计算机科学与技术班级班级班级09?09?09?01?01?01?班班实验课程名称实验课程名称实验课程名称算法设计与分析算法设计与分析算法设计与分析??指导教师及职称指导教师及职称指导教师及职称吕兰兰吕兰兰吕兰兰讲师讲师讲师开课学期开课学期开课学期2011?2011?2011?至至2012?2012?2012?学年学年学年学期学期学期上课时间上课时间上课时间201120112011年年12?12?12?月月湖南科技学院教务处编印湖南科技学院教务处编印湖南科技学院教务处编印实验名称

动态规划法2

解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
一般来说，适合于用动态规划法求解的问题具有以下特点：
1、可以划分成若干个阶段，问题的求解过程就是对若干个阶段的一系列决策过程。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
三、动态规划与其他算法的比较
动态规划与其说是一种算法，不如说是一种算法设计的策略，他的基本思想体现于许多其它算法之中。下面我们通过比较动态规划和其他的一些算法之间的相互联系，来深入理解动态规划的基本思想。
动态规划与静态规划——某些情况下可以相互转化
动态规划与递推——动态规划是最优化算法

南京邮电大学算法设计实验报告——动态规划法

for(int j=1;j<=n;j++) {
if(a[i]==b[j]) {
c[i][j]=c[i-1][j-1]+1; s[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; s[i][j]=2; } else { c[i][j]=c[i][j-1]; s[i][j]=3; } } } return c[m][n]; //返回最优解值 }
算法分析与设计 A
动态规划法
2009
年 11 月 20 日
计算机学院软件工程系
张怡婷
学生姓名学院(系)
丁力琪班级学号计算机学院专业
B07030907 软件工程
实验报告
实验名称
动态规划法
指导教师张怡婷
实验类型
验证
实验学时 2×2 实验时间 2009-11-20
一、实验目的和任务
目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态
6
8、输入序列 X={x1,x2,……,xm}={a,b,c,b,d,a,b}和 Y={y1,y2,……,yn}={b,d,c,a,b,a}作为测试数据，测试程序是否能够正确运行？输出结果是什么？运行正确，实验结果显示：4
bcba
9、分析该动态规划算法的两个主要成员函数 int LCSLength()和 void CLCS()的时间复杂性。
#include<iostream> #include<string> using namespace std; #define maxlength 11 class LCS { public:

动态规划算法实验报告

南京信息工程大学滨江学院实验（实习）报告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. 实验小结通过本次实验加深了我对动态规划算法的理解。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

C[i, j ] = min{C[1, k − 1] + C[k , n] + r1rk rn +1}
1< k ≤ n
这样，求 M1M2…Mn 所需要最少数量乘法次数只需要求解 C[1,n]即可。其算法伪代码如下： 1. for i←1 to n 2. C[i,j]←0 3. end for 4. for d←1 to n-1 5. for i←1 to n-d 6. j←i+d 7. C[i,j]←∞
n −1
f ( n) =
1 2n − 2 (2n − 2)! 4n 4n ，因此 ( ) = Ω ( ) ，对于每一种方案， = ≈ f n 2 n1.5 n 4 π n1.5 n − 1 n((n − 1)!)
找到数量乘法的次数还需要 Θ(n) 时间，因此总的时间复杂度为
∑∑∑ c = c((n − 1) ×1 + (n − 1) × 2 + + (n − (n − 1)) × (n − 1))
d =1 i =1 k =1
n −1 n − d d
= c(n × (1 + 2 + + (n − 1)) − (1×1 + 2 × 2 + (n − 1) × (n − 1))) n 2 × (n − 1) n × (n − 1) × (2n − 1) = c( − ) 2 6 cn 3 − cn = = Θ( n 3 ) 6 三、实验内容及要求 1. 编写程序使用动态规划算法 MATCHAIN 求解 n 个矩阵连乘所需最找数量乘法次数，并用实际数据对算法进行测试。 2. 要求对算法 MATCHAIN 加以改进，不仅能够输出数量乘法次数，还要能输出最佳乘法方案，如(M1M2)((M3M4)M5)。四、实验步骤
1. 编写函数 MATCHAIN 求解矩阵链相乘问题，函数头为： int MATCHAIN(int r[], int n) r 为数组名， r[i]和 r[j]分别表示矩阵 Mi 的行数和列数， n 表示连乘矩阵的个数。 2. 在 main 函数中使用给定数组{4,5,3,6,4,5}测试 MATCHAIN 函数，效果如下图所示。
= rn max( pi + rn −i )
1≤ i ≤ n
根据此公式，可按照长度为 0,1,2,…,n 的顺序逐步求解最优切割方案。（注意：程序中不需要使用递归调用）
实验二动态规划法
一、实验目的 1．理解动态规划法的方法； 2. 掌握使用动态规划法解决一般问题的步骤； 3. 掌握动态规划算法求解矩阵连续相乘的方法。二、实验原理假设有 M1，M2，M3 这三个矩阵，这三个矩阵的维数分别是 2×10，10×2 和 2×10，要求他们的乘积 M1M2M3。如果先将 M1 和 M2 相乘，然后将结果和 M3 相乘，那么要进行 2×10×2+2×2×10=80 次乘法。如果先用 M2 和 M3 相乘，然后将结果和 M1 相乘，那么要进行 10×2×10+2×10×10=400 次乘法。显然，矩阵乘法的顺序不同会导致乘法次数的不同。一般来说，n 个矩阵 M1M2…Mn 链乘法的耗费，取决于 n-1 个乘法执行的顺序。如果使用满立法计算每一种可能顺序的数量乘法次数。设 f(n)是求 n 个矩阵乘积可能的顺序数，假定要进行以下乘法(M1M2…Mk)(Mk+1Mk+2…Mn)，那么，对于前 k 个矩阵有 f(k)种方案，对于每一种方案，对余下的 n-k 个矩阵有 f(n-k)种方案，因此总共有 f(k)f(n-k)种方案。因此，n 个矩阵相乘总的方案数为 f (n) = ∑k =1 f (k ) f (n − k ) 种，经计算可以证明
C[2,2]
C[2,3]Leabharlann C[2,4]C[2,5]
C[3,3]
C[3,4]
C[3,5]
C[4,4]
C[4,5]
C[5,5]
代码第 1 行~第 3 行填充对角线 d=0，第 4 行的循环用来填充对角线 d=1 到 d=n-1，第 5 行循环用于填充对角线 d=i 的项目，第 8 行~第 10 行用于计算 C[i,j]，函数的返回值在第 13 行给出，为 C[1,n]，即矩阵 M1M2…Mn 链相乘所需最少乘法的次数。算法的时间复杂度分析如下：
8. for k←i+1 to j 9. C[i,j]←min{C[i,j],C[i,k-1]+C[k,j]+r[i]r[k]r[j+1]} 10. end for 11. end for 12.end for 13.return C[1,n]
C[1,1]
C[1,2]
C[1,3]
C[1,4]
C[1,5]
f (n) = Ω(4 n / n ) ，随着 n 的增大，f(n)的增长速度惊人。
采取动态规划法的思想，对于 n 个矩阵 M1M2…Mn，其中矩阵 Mi 的行数和列数分别用 ri 和 ri+1 来表示，因此需要一个 n+1 维的矩阵存储 n 个矩阵的行数和列数。令 Mi,j 为 M1M2…Mn 的成绩，计其乘法所耗费的数量乘法的次数为 C[i,j]，则有以下递推式：
五、思考和作业 1. 对 MATCHAIN 算法加以改进，使算法能够输出乘法方案，效果如下图所示。
提示： (1) 用一个数组 brackets 记录矩阵链乘法方案括号的数目，数组 brackets 的大小为 2n，brackets[0]和 brackets[1]分别表示矩阵 1 的左括号和右括号数目。 (2) 设定辅助矩阵 flag，其大小和矩阵 C 等同，flag[i,j]表示求解 C[i,j] 时所得到的最佳分割 k 值，如计算 C[2,5]时，使 C[2,5]值最小的 k 的值为 4，则 flag[2,5]=4，利用 flag 数组可以计算 brackets 数组的值。 (3) 根据 brackets 数组输出最终方案。 2. 钢条切割问题给定一段长度为 n 的钢条和一个价格表 pi(i=1,2,…,n)，求切割钢条方案，使得销售收益 rn 最大。提示：要求长度为 n 的钢条的最好切割方案，可以使用以下递归求解方法：将钢条从左边切割下来长度为 i 的一段，对右边剩下长度为 n-i 的一段继续进行切割（递归求解），对左边一段不再进行切割。