矩阵连乘问题

超、凢脫俗 2022-12-28 14:17 186阅读 0赞

### 文章目录 ###

*  算法思想
 *  状态转移方程
 *  算法代码

--------------------

# 算法思想 #

从小到大找不同的连乘矩阵的分割点，将所有分割点计算一遍就可以知道最优情况

# 状态转移方程 #

![1][]

# 算法代码 #

#include <iostream>
    using namespace std;
    
    struct ju
    {
        
        int p,q;
    }a[100];
    int m[100][100];    //计算连乘次数
    int s[100][100];    //记录连乘的断开位置
    
    int n;
    
    const int INF = 9999999;
    
    //计算最优连乘次数
    void algo()
    {
        
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++){
        
                if(i == j)
                    m[i][j] = 0;
                else
                    m[i][j] = INF;
                s[i][j] = 0;
            }
        
        for(int d = 2; d <= n; d++){
            //d个矩阵连乘
            for(int i = 1; i <= n - d + 1; i++){
        
                int j = i + d - 1;  //本轮循环下的最后一个矩阵
                
                //从j-i种选择中，找出一个最优的断开位置k，使得数乘次数最少
                for(int k = i; k < j; k++){
        
                    int t = m[i][k] + m[k + 1][j] + a[i].p * a[k + 1].p * a[j].q;
                    if(t < m[i][j]){
            //如果更优就替换
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
            }
        }
    }
    
    //输出最优矩阵连乘情况
    //用分治递归的思想，找出分割点，逐渐缩小到两个矩阵相乘
    void rebuild(int i, int j)
    {
        
        if(i == j){
         //这时只有一个矩阵，就直接输出这个矩阵
            cout << "A" << i;
            return;
        }
        else if(j == i + 1){
            //这时为两个矩阵相乘，直接输出这两个矩阵
            cout << "A" << i << "A" << j;
            return;
        }
        
        
        //每次分治都要在开始和结束为止加括号
        if(i != s[i][j])
            cout << "(";
        
        rebuild(i, s[i][j]);    //处理左半部分的矩阵连乘
        
        if(i != s[i][j])
            cout << ")";
        
        if(s[i][j] + 1 != j)
            cout << "(";
        
        rebuild(s[i][j] + 1, j);    //处理右半部分的矩阵连乘
        
        if(s[i][j] + 1 != j)
            cout << ")";
        
        //每次分治都要在开始和结束为止加括号
        
        return;
    }
    
    
    int main()
    {
        
        cin >> n;
        
        for(int i = 1; i <= n; i++)
            cin >> a[i].p >> a[i].q;
        
        algo();
        
        cout << m[1][n] << endl;
        rebuild(1, n);
        cout << endl;
        
    }
    
    /*
    样例
    6
    30 35
    35 15
    15 5
    5 10
    10 20
    20 25
    */

[1]: /images/20221120/2ce5d3a065aa4ea2807d205107fcb60d.png