算法笔记 13_矩阵连乘问题


一、问题描述

给定 n 个矩阵:A1,A2,…,An,其中 Ai 与 Ai+1 是可乘的(也就是说Aiy=Ai+1x),i=1,2,…,n-1。确定计算矩阵连乘积的次序,使得依照此次序来计算矩阵连乘积所需要的数乘次数最少(输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数)。 
如下例子: 
矩阵连乘积 A1A2A3A4 有 5 种不同的完全加括号的方式:(A1(A2(A3A4))),(A1((A2A3)A4)),((A1A2)(A3A4)),((A1(A2A3))A4),(((A1A2)A3)A4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序,这决定了作乘积所需要的计算量。
详细例子: 
计算三个矩阵连乘{A1,A2,A3};维数分别为10*100 , 100*5 , 5*50, 按此顺序计算需要的次数((A1*A2)A3):10X100X5+10X5X50=7500次,按此顺序计算需要的次数(A1(A2*A3)):100*5*50+10*100*50=75000次数乘,是前一种计算方式的10倍。 
{矩阵两两相乘求计算量方法为:比如((A1*A2)*A3):A1x*A2x*A2y + A3x*A1x*A2y}

二、C++ 代码

#include<iostream>
using namespace std;

#define MAX 1000int p[MAX+1];  //p用来记录用户所输入的相邻矩阵的行列值(重复数字只写一遍,所以是 MAX+1)

int m[MAX][MAX];  //m[i][j]用来记录数乘次数最优解
int s[MAX][MAX];  //s[][]用来记录在哪里进行加括号划分
int n; //记录矩阵的个数

void mark() // 标记函数,标记在哪里加括号
{
    for(int i=1; i<=n; i++) m[i][i]=0;  //函数初始化

    for(int r=2; r<=n; r++) //对角线循环
        for(int i=1; i<=n-r+1; i++) //对角线循环格式
        {   
            //行循环
            int j = r+i-1;  //列的控制

            //找m[i][j]的最小值,先初始化一下,令k=i
            m[i][j] = m[i][i] + m[i+1][j] + p[i-1]*p[i]*p[j];
            s[i][j] = i;    // s在这里只是标明加括号的位置

            //k从i+1到j-1循环找m[i][j]的最小值
            for(int k=i+1; k<j; k++)
            {                
                int temp = m[i][k] +m[k+1][j] + p[i-1]*p[k]*p[j]; 
                               
                if(temp < m[i][j])
                {
                    m[i][j] = temp;                    //s[][]用来记录在子序列i-j段中,在k位置处
                    //断开能得到最优解
                    s[i][j]=k;
                }
            }
        }
}
                
//根据s[][]记录的各个子段的最优解,将其输出
void traceback(int i,int j)
{ 
        //回溯函数
    if(i==j) return ;    
    
    //同样的递归调用思想
    traceback(i,s[i][j]);
    traceback(s[i][j]+1,j);    
    cout << "( A" << i << "," << s[i][j] << " and A" << s[i][j]+1 << "," << j << " )" << endl;
}

void main(){ //主函数

    while(1)
    {
        cout << "Please input the number of matrixs you like: ";     //读取用户输入
        cin >> n;        
        cout << "Please input scales of each matrix like\"a1x a2x ... any\": "<< endl;        
        for(int i=0; i<=n; i++)            
            cin >> p[i];

        mark();        
        
        //输出最好的加括号次序
        cout << "The iearest situation is: " << endl;
        traceback(1,n);        
        cout << "And the result is: " << m[1][n] << endl;        //最终解值为m[1][n];
        cout << "-----------------------------------------------------------" << endl;
    }
}


happysneaker.com

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论