10203. Fast Matrix Chain Multiplication Basic (OpenMP)

題目描述

矩陣鏈乘積（Matrix chain multiplication）是可用動態規劃解決的最佳化問題。給定一序列矩陣，期望求出相乘這些矩陣的最有效方法。此問題並不是真的去執行其乘法，而只是決定執行乘法的順序而已。因為矩陣乘法具有結合律，所有其運算順序有很多種選擇。換句話說，不論如何括號其乘積，最後結果都會是一樣的。例如，若有四個矩陣 $A$、 $B$、$C$ 和 $D$，將可以有：

$$ABCD=(AB)(CD)=A(BCD)=A(BC)D=...$$

但括號其乘積的順序是會影響到需計算乘積所需簡單算術運算的數目，即其效率。例如，設 $A$ 為一 $10\times 30$ 矩陣， $B$為 $30\times 5$ 矩陣與 $C$ 為 $5\times 60$ 矩陣，則：

$(AB)C$ 有 $(10\times 30\times 5)+(10\times 5\times 60)=1500+3000=4500$ 個運算

$A(BC)$ 有 $(30\times 5\times 60)+(10\times 30\times 60)=9000+18000=27000$ 個運算

明顯地，第一種順序較為有效。請用動態規劃 (Dynamic Programming) 找出最少乘法次數的解。

Note

因為 DP 演算法的架構，將會造成矩陣存取上大量的 cache miss，在平行程式中嚴重影響校能，請優化此缺陷，並比較差異。

sequence.c

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
#include <stdio.h>
#define MAXN 2048
#define INF (1LL<<60)
int N;
long long dp[MAXN*MAXN], SZ[MAXN+1];
int main() {
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i <= N; i++)
            scanf("%lld", &SZ[i]);
        for (int i=0; i<N; i++)
            dp[i*N + i] = 0;
 
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < N-i; j++) {
                int l = j, r = j+i;
                long long local = INF;
                for (int k = l; k < r; k++) {
                    long long t = dp[l*N+k] + dp[(k+1)*N+r] + SZ[l] * SZ[k+1] * SZ[r+1];
                    if (t < local)
                        local = t;
                }
                dp[l*N+r] = local;
            }
        }
        printf("%lld\n", dp[0*N+N-1]);
    }
    return 0;
}

輸入格式

有多組測資，每組第一行會有一個整數 $N$ 表示矩陣鏈上有 $N$ 個矩陣，第二行上會有 $N+1$ 個整數 $Z_i$，表示矩陣鏈的每一個行列大小，例如當 $N = 3$ 時，輸入 10 30 5 60 表示矩陣 $A_{10, 30} B_{30, 5} C_{5, 60}$ 相乘。

• $1 \le N \le 2048$
• $1 \le Z_i \le 4096$

輸出格式

對於每組測資輸出一行一個整數 $M$ 為最少乘法次數。

範例輸入

2
2 2 2
3
10 30 5 60
3
1 5 20 1
3
5 10 20 35
6
30 35 15 5 10 20 25

範例輸出

8
4500
105
4500
15125