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

《算法设计与分析》课程实验报告 专 业： 软件工程 班 级： 1120561 学 号： 29 姓 名： 王荣 日期： 2013 年 11 月 11 日 实验题目 动态规划算法 实验目的 掌握动态规划算法的基本方法 掌握动态规划算法中最优子结构的分析 掌握递归求解最优值的方法 掌握最优解的构造. 实验内容 给定n个矩阵{A1, A2, …,An}，其中，Ai与Ai+1是可乘的，计算这n个矩阵的连乘积。从中找出一种乘次数最少的计算次序。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。 实验步骤 题目一 问题分析 解这个问题的最容易想到的方法是穷举有哪些信誉好的足球投注网站法。也就是列出所有可能的计算次序，并计算出每一种计算次序相应需要的计算量，然后找出最小者。然而，这样做计算量太大。事实上，对于n个矩阵的连乘积，设有P(n)个不同的计算次序。由于我们可以首先在第k个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,…,n-1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。所以关于P(n)，我们有递推式如下： ?? 解此递归方程可得,P(n)实际上是Catalan数，即P(n)=C(n-1)，其中， ?? 也就是说，P(n)随着n的增长是指数增长的。因此，穷举有哪些信誉好的足球投注网站法不是一个有效算法。 ??? 下面我们来考虑用动态规划法解矩阵连乘积的最优计算次序问题。此问题是动态规划的典型应用之一。 1.分析最优解的结构 ??? 首先，为方便起见，将矩阵连乘积AiAi+1…Aj简记为Ai…j。我们来看计算A1…n的一个最优次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1=kn，则完全加括号方式为((A1…Ak)(Ak+1…An))。照此，我们要先计算A1…k和Ak+1…n，然后，将所得的结果相乘才得到A1…n。显然其总计算量为计算A1…k的计算量加上计算Ak+1…n的计算量，再加上A1…k与Ak+1…n相乘的计算量。 ??? 这个问题的一个关键特征是：计算A1…n的一个最优次序所包含的计算A1…k的次序也是最优的。事实上，若有一个计算A1…k的次序需要的计算量更少，则用此次序替换原来计算A1…k的次序，得到的计算A1…n的次序需要的计算量将比最优次序所需计算量更少，这是一个矛盾。同理可知，计算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 ； 当ij时，可利用最优子结构性质来计算m[i,j]。事实上，若计算Ai…j的最优次 序在Ak和Ak+1之间断开，i≤kj，则：m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj。由于在计算时我们并不知道断开点A的位置，所以A还未定。不过k的位置只有j-i个可能，即k∈{i,i+1,…,j-1}。因此k是这j-i个位置中计算量达到最小的那一个位置。从而m[i,j]可以递归地定义为： ??? m[i,j]给出了最优值，即计算Ai…j所需的最少数乘次数。同时还确定了计算Ai…j的最优次序中的断开位置k，也就是说，对于这个k有m[i,j] = m[i,k] + m[k+1,j] + pi-1pkpj 。若将对应于m[i,j]的断开位置k记录在s[i,j]中，则相应的最优解便可递归地构造出来。 3.计算最优值 ??? 根据m[i,j]的递归定义(2.1)，容易写一个递归程序来计算m[1,n]。稍后我们将看到，简单地递归计算将耗费指数计算时间。然而，我们注意到，在递归计算过程中，不同的子问题个数只有θ(n2)个。事实上，对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 个。由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 ?