矩阵连乘（C语言）

矩阵连乘（C语言） 矩阵连乘（C语言）

参考链接：https://blog.csdn.net/qq_32919451/article/details/80643118

问题描述

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是10 * 100，100 * 5和5 * 50，采用（A1A2）A3，乘法次数为101005+10550=7500次，而采用A1（A2A3），乘法次数为100 * 5 * 50+10 * 100 * 50=75000次乘法，显然，最好的次序是（A1A2)A3，乘法次数为7500次。

分析最优解结构

此问题最难的地方在于找到最优子结构。对乘积A1A2…An的任意加括号方法都会将序列在某个地方分成两部分，也就是最后一次乘法计算的地方，我们将这个位置记为k，也就是说首先计算A1…Ak和Ak+1…An，然后再将这两部分的结果相乘。
最优子结构如下：假设A1A2…An的一个最优加括号把乘积在Ak和Ak+1间分开，则前缀子链A1…Ak的加括号方式必定为A1…Ak的一个最优加括号，后缀子链同理。
一开始并不知道k的确切位置，需要遍历所有位置以保证找到合适的k来分割乘积。

建立递归关系

构建辅助表，解决重叠子问题

从第二步的递归式可以发现解的过程中会有很多重叠子问题，可以用一个nXn维的辅助表m[ n ] [ n ] ，s[n] [n]分别表示最优乘积代价及其分割位置k 。
辅助表s[n] [n]可以由2种方法构造：

1. 一种是自底向上填表构建，该方法要求按照递增的方式逐步填写子问题的解，也就是先计算长度为2的所有矩阵链的解，然后计算长度3的矩阵链，直到长度n；
2. 另一种是自顶向下填表的备忘录法，该方法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为一极大值)，以表示待计算，在递归的过程中逐个填入遇到的子问题的解。

对于一组矩阵:A1(30x35),A2(35x15),A3(15x5),A4(5x10),A5(10x20),A6(20x25) 个数N为6

那么p数组保存它们的行数和列数：p={30,35,15,5,10,20,25}共有N+1即7个元素

p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数…p[5],p[6]代表第六个矩阵的行数和列数

计算最优值

构造最优解

代码实现

#include 
#include 
//MAXSIZE为数组数字个数
#define MAXSIZE 6
#include 
int n = MAXSIZE-1;//矩阵个数
int a[MAXSIZE] = {2,3,5,8,6,5};//全局设置内容
int t[MAXSIZE][MAXSIZE]; //备忘录


int m[MAXSIZE][MAXSIZE];          //m[i][j]存储子问题的最优解
int s[MAXSIZE][MAXSIZE];           //s[i][j]存储子问题的最佳分割点

//方法一：备忘录法优化
int F(int left,int right)
{
    int i=0,lefttimes,righttimes,wholetimes;
    int min=10000;
    int k;
    if(left==right) return 0;
    if(t[left][right]>0)
    {
        return t[left][right];
    }
    for(i=left;i 
截图 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/4948833.html