tyvj矩阵连乘

02-05-2021 约 825 字预计阅读 2 分钟

找最优子结构

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

最优值

将矩阵连乘积$Ai,Ai+1……Aj$记为A[i：j]。对于矩阵连乘积的最优计算次序的问题，设计算A[i：j]，1<=i<=j<=n,所需要的最小数乘次数为m[i][j]，则原问题的最优值为m[1][n]。当i=j时，A[i：j]=Ai为单一的矩阵，则无需计算，所以$m[i][j]=0，i=j=1，2，……，n$。即对应的二维表对角线上的值全为0。当i<j时，这就需要用步骤（1）的最优子结构性质来计算m[i][j]。若计算A[i:j]的最优次序在Ak和Ak+1之间断开，$i<=k<j$,则 ${m[i][j]m[i][k]+m[k+1][j]+p_{i-1}*pk*pj}$ k的位置只有 $j-i$ 种可能，即k属于集合${i,i+1,……,j-1}$，所以k是这j-i个位置中使计算量达到最小的那个位置。所以m[i][j]可以递归地定义为 $m[i][j]={min{m[i][k]+m[k+1][j]+p_{i-1}*pk*pj}i<j ,i<=k<j}$ 将对应于m[i][j]的断开位置k记为s[i][j]，在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#include <iostream>
using namespace std;
int a[1001], dp[1001][1001];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int s = 2; s <= n; s++) //how many
    {
        for (int i = 1; i <= n - s + 1; i++)
        {
            int j = i + s - 1;
            dp[i][j] = dp[i + 1][j] + a[i - 1] * a[i] * a[j];
            for (int k = 1; k < j; k++)
            {
                int t = dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j];
                if (t < dp[i][j])
                {
                    dp[i][j] = t;
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

目录

tyvj矩阵连乘

找最优子结构

最优值