矩阵的连乘问的题目《算法分析报告与设计》.doc

实用标准文案 精彩文档 设计性实验报告 课程名称： 《算法分析与设计》 实验题目： 矩阵连乘问题 组 长： 成 员 一： 成 员 二： 成 员 三： 系 别： 数学与计算机科学系 专业班级： 指导教师： 实验日期： 精彩文档 一、实验目的和要求 实验目的 熟悉动态规划算法设计思想和设计步骤，掌握基本的程序设计方法，培养学生用计算机解决实际问题的能力。 实验要求 1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。 2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。 3、实验项目可以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行实验，要求在学期末形成完整的项目程序设计报告。 二、实验内容提要 矩阵连乘问题 给定n个矩阵{A1,A2,…,An}， 其中，Ai与Ai+1是可乘的，i=1,2，…，n-1。考查这n个矩阵的连乘积A1 （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。 三、实验步骤 下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。 （1）分析最优解的结构（最优子结构性质） 设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解结构特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为方便起见，降矩阵乘积Ai Ai+1…Aj简记为A[i:j]。考查计算A[1：n]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1=kn,则其相应的完全加括号方式为（（A1…Ak）（Ak+1…An））即依此次序，先计算A[1：k]和 A[k+1：n]，然后将计算结果相乘得到A[1：n]。依此计算次序，总计算量为A[1：k]的计算量加上A[k+1:n]的计算量，再加上A[1:k]和A[k+1:n]相乘的计算量。 这个问题的一个关键特征是：计算A[1:n]的最优次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。事实上，若有一个计算A[1:k]的次序需要的计算量更少，则用此次序替换原来计算A[1:k]的次序，得到的计算A[1:n]的计算量将比按最优次序计算所需计算量更少，这是一个矛盾。同理可知，计算A[1:n]的最优次序所包含的计算矩阵子链A[k+1:n]的次序也是最优的。 因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。 （2）建立递归关系 对于矩阵连乘积的最优计算次序问题，设计算A[i:j],1=i=n,所需的最少数乘次数为m[i][j],则原问题的最优值为吗m[1][n]。 当i=j时，A[i:j]=Ai为单一矩阵，无需计算，因此，m[i][i]=0,i=1,2,......,n 。 当ij时，可利用最优子结构性质计算m[i][j]。事实上，若计算A[i:j]的最优次序在Ak和Ak+1之间断开，i=kj,则m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]。由于在计算时并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i种可能，即k属于{i，i+1，......，j-1}。因此，k是这j-i个位置中使计算量达到最小的那个位置。从而m[i][j]可以递归地定义为 当i=j，m[i][j]=0; 当ij，m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]},i=kj m[i][j]给出了最优值，即计算A[i:j]所需的最少数乘次数。同时还确定了计算A[i:j]的最优次序中的断开位置k，也就是说，对于这个k有 m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j] 若将对应于m[i][j]的断开位置k记为s[i][j],在计算出最优值m[i][j]后，可递归地有s[i][j]构造出相应的最优解。 （3）计算最优值 根据计算m[i][j]的递归式，容易写一个递归算法计算m[i][n]。.稍后将看到，简单的递归计算将耗费指数计算时间。注意到在递归计算过程中，不同的子问题个数只有θ（n^2）个。事实上，对于1=i=j=n不同的有序对（i,j）对应于不同的子问题。因此，不同的子问题的个数最多只有n*(n-1)/2+n=θ（n^2）个。由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可以动态规划算法求解的又一显著特征。 用动态规划算法解此问题，可依据其