编程作业三

[算法导论] 编程作业三:矩阵链乘法与最大子数组

PB15000105 肖映泰

一、作业任务

1.采⽤用动态规划算法编程实现矩阵连乘的最优括号化方案，并输出最优括号化方案

2.采用分治法和贪心算法实现最大子数组

二、算法原理

矩阵链乘法

给定n个矩阵的链<A1,A2,...,An>$<A_1,A_2,...,A_n>$，矩阵的规模为pi−1×pi(1≤i≤n)$p_{i-1}\times p_i(1\le i\le n)$，求完全括号化方案，使得计算乘积A1A2...An$A_1{A}_2...A_n$所需要标量乘法的时间最少

步骤1：最优括号化方案的结构特征

​ 假设AiAi+1...Aj$A_i{A}_{i+1}...A_j$的最优括号化方案的割点在Ak$A_k$和Ak+1$A_{k+1}$之间，那么子问题分解为独立求解AiAi+1...Ak$A_i{A}_{i+1}...A_k$的最优括号化方案，与Ak+1Ak+2...Aj$A_{k+1}{A}_{k+2}...A_j$的最优括号化方案

步骤2：一个递归求解方案

​ 令m[i,j]$m[i,j]$表示计算矩阵所需要标量乘法次数的最小值，则可以递归定义m[i,j]$m[i,j]$如下

m[i,j]={0,i=jmini≤k<jm[i,k]+m[k+1,j]+pi−1pkpj,i<j(3)(4)$$m[i,j]=\{\begin{array}{}\text{(3)}& 0,i=j\text{(4)}& \underset{i\le k<j}{min}m[i,k]+m[k+1,j]+p_{i-1}{p}_k{p}_j,i<j\end{array}$$

​ 令s[i,j]$s[i,j]$保存AiAi+1...Aj$A_i{A}_{i+1}...A_j$最优括号化方案的分割点位置k

步骤3：计算最优代价

​ 可以证明算法的运行时间为Ω(n3)$\mathrm{\Omega }(n^3)$

步骤4：构造最优解

​ 利用表格s[i,j]$s[i,j]$即可递归地输出最优解

最大子数组

分治法

递归求解

A[low...high]$A[low...high]$的任何连续子数组A[i,j]$A[i,j]$所处的位置必然是一下集中情况之一

∙$\bullet$完全位于子数组A[low...mid]$A[low...mid]$中

∙$\bullet$完全位于子数组A[mid+1…high]中

∙$\bullet$跨越了中点

对于第三种情况可以使用O(n)$O(n)$的算法FMCS求解

对于前两种情况，继续采用分治法递归求解

贪心算法

从A[1]开始，M记录当前子数组的和，Mr记录从开始至今的最大子数组的和。

一旦M大于Mr，将Mr设置为M并记录当前子数组的下标[low,high]$[low,high]$ 。

若M小于0，则将当前子数组置为0，重新开始。

三、性能分析

正确性验证

利用书本例子验证算法的正确性

1.矩阵链乘法

调用test.h中的testMCO()函数，得到书本P214页同样的输出

2.最大子数组

分别调用testFMS()和testGreedy()得到与书本P39相同的输出

性能分析

随机产生100,200,300大小的数组，范围在[-100,100)之间，调用时间测试算法，输出结果

从图中所得的数据可以粗略估计

MCO：O(n3)$O(n^3)$

分治法：O(nlg2(n))$O(nl{g}_2(n))$

贪心算法：O(n)$O(n)$

四、实验总结

本次实验学习到了一些新的c++使用技巧

1.vector表示矩阵

#include <iostream>
#include <vector>
void testVector()
{
    //定义一个row*col的矩阵
    int row=3;
    int col=5;
    //vec是一个向量，其中的元素为向量，大小为row，vec.size()==row;
    //vec[0]是一个向量，大小为col,vec[0].size()==col;
    vector<vector<double> > vec(row,vector<double>(col,0.0));

}

2.返回多个值的方法

//有些时候用参数表返回值会显得冗余，可以采用返回指向结构体的指针的方法返回多个值
//这些值被存储在一个结构体中
//当然也可以将结构体指针作为参数传入
struct Result
{
    int left;
    int right;
    double sum;
};

Result* testResult()
{
    Result *result= new Result;//new 之后记得要 delete
    result->left=1;
    result->right=10;
    result->sum=100;
    return result;
}

int main()
{
    Result *result;
    result=testResult();
    delete result;
    return 0;
}

3.产生随机数

#include <iostream>
#include <vector>
//c++采用的是c的内置函数调用随机数
#include <stdlib.h>
#include <time.h>

void testRand()
{
    int N=100;//产生100个随机数
    vector<int> p(N , 0);

    srand((unsigned)time(NULL));//设置随机种子
    for (int i = 0; i < N ; i++)
    {
        //rand()%(b-a)+a产生[a,b)内的随机数
        p[i] = rand()%(100-(-100))-100;//[-100,100)内的随机数
    }
}