《算法设计与分析》课程实验报告-动态规划算法

《《算法设计与分析》课程实验报告-动态规划算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析》课程实验报告专业：软件工程班级：1120561学号：29姓名：王荣日期：2013年11月11日一、实验题目动态规划算法二、实验目的（1）掌握动态规划算法的基本方法（2）掌握动态规划算法中最优子结构的分析（3）掌握递归求解最优值的方法（4）掌握最优解的构造.三、实验内容1.给定n个矩阵{A1,A2,…,An}，其中，Ai与Ai+1是可乘的，计算这n个矩阵的连乘积。从中找出一种乘次数最少的计算次序。2.给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。3.在一块电路板的上、下2端

2、分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。四、实验步骤1、题目一(1)问题分析解这个问题的最容易想到的方法是穷举搜索法。也就是列出所有可能的计算次序，并计算出每一种计算次序相应需要的计算量，然后找出最小者。然而，这样做计算量太大。事实上，对于n个矩阵的连乘积，设有P(n)个不同的计算次序。由于我们可以首先在第k个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列

3、，k=1,2,…,n-1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。所以关于P(n)，我们有递推式如下：  解此递归方程可得,P(n)实际上是Catalan数，即P(n)=C(n-1)，其中，  也就是说，P(n)随着n的增长是指数增长的。因此，穷举搜索法不是一个有效算法。   下面我们来考虑用动态规划9法解矩阵连乘积的最优计算次序问题。此问题是动态规划的典型应用之一。1.分析最优解的结构   首先，为方便起见，将矩阵连乘积AiAi+1…Aj简记为Ai…j。我们来看计算A1…n的一个最优

4、次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1<=k

5、序所需计算量更少，这是一个矛盾。同理可知，计算A1…n的一个最优次序所包含的计算矩阵子链Ak+1…n的次序也是最优的。根据该问题的指标函数的特征也可以知道该问题满足最优化原理。另外，该问题显然满足无后向性，因为前面的矩阵链的计算方法和后面的矩阵链的计算方法无关。2.建立递归关系   对于矩阵连乘积的最优计算次序问题，设计算Ai…j,1≤i≤j≤n，所需的最少数乘次数为m[i,j]，原问题的最优值为m[1,n]。§当i=j时，Ai…j=Ai为单一矩阵，无需计算，因此m[i,i]=0，i=1,2,…,n；§当i

6、[i,j]。事实上，若计算Ai…j的最优次序在Ak和Ak+1之间断开，i≤k

7、kpj。若将对应于m[i,j]的断开位置k记录在s[i,j]中，则相应的最优解便可递归地构造出来。3.计算最优值   根据m[i,j]的递归定义(2.1)，容易写一个递归程序来计算m[1,n]。稍后我们将看到，简单地递归计算将耗费指数计算时间。然而，我们注意到，在递归计算过程中，不同的子问题个数只有θ(n2)个。事实上，对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有个。由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。   用动态规划算法解此问题，可依

8、据递归式(2.1)以自底向上的方式进行计算，在计算过程中，保存已解决的子问题答案，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得