動態規劃：矩陣連乘問題

• 2019 年 10 月 29 日
• 筆記

一、問題描述

給定n個數字矩陣A1，A2，…，An，其中Ai與Ai+1是可乘的，設Ai是pi-1*pi矩陣, i=1,2,…,n。求矩陣連乘A1A2…An的加括弧方法，使得所用的乘次數最少。

例子

• 三個矩陣連乘，可以有(A1A2)A3和A1(A2A3)兩種方法求積 ，乘法次數分別為： p0p1p2+p0p2p3和p0p1p3+p1p2p3
• 假設p0=10, p1=100, p2=5, p3=50, 兩種方法的次數分別是：7500 和 75000
• 明顯可以看出，兩種乘法在效率上是有較大差異的，電腦實現乘法比實現加法要複雜，所以如何使乘法次數最小是一個值得探究的問題

如果使用蠻力演算法，對所有可能的加括弧方法遞歸搜索，則:

時間複雜度為指數級別，那麼就需要有更優的方法來計算最佳的矩陣連乘方法

二、最優子結構性質

維基百科：如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）

通常來說，一個問題可以使用動態規劃求解，必須具有最優子結構性質。所以，如果我們證明該問題具有最優子結構性質，我們就可以使用動態規劃的方法來得到它的最優解，通常可以使用反證法進行證明。

證明：

設(A1…Ak)(Ak+1…An) 具有最少乘法次數，則(A1…Ak)中加括弧的方法使A1..Ak乘法次數最少。否則設存在另一種加括弧方法(A1…Ak)’更優，則(A1…Ak)'(Ak+1…An) 比 (A1…Ak)(Ak+1…An) 更優，矛盾。同理， (Ak+1…An) 內的連乘方法也是最優的。

三、實現

用m[i][j]表示Ai到Aj連乘的最小次數，則有遞推關係：

這裡使用一種自底向上的動態填表的方式來進行求解。
由上式及下表可以知道，每當我們要求得一個m[i][j]的值時，都需要知道它左邊位置和下邊位置所有的值，這樣來理解的話就很容易實現了。

演算法過程示例

6個矩陣連乘：P=[30,35,15,5,10,20,25]

計算過程：

還可以增加一個矩陣記錄分割點，求得m[i][j]值的那一個k點即為最佳分割點。
該演算法的時間複雜度為

O(n^3)

程式碼示例

#include<iostream>  using namespace std;      //矩陣連乘問題的解  int MatrixChainOrder(int n,int p[],int a, int b){      int m[n+1][n+1], s[n+1][n+1];//m記錄乘法操作次數，s記錄分割點k      for(int i = 1;i <= n;i++){          m[i][i] = 0;          s[i][i] = 0;      }      for(int i = n-1;i >= 1;i--){          for(int j = i+1;j <= n;j++){              m[i][j] = 10000000;              for(int k = i;k <= j-1;k++){                  int sum = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];                  if(sum < m[i][j]){                      m[i][j] = sum;                      s[i][j] = k;                  }              }          }      }      printf("%d %d", m[a][b], s[a][b]);  }                int main(){      int n, i, j;      cin >> n;      int p[n+1];      for(int i = 0;i < n+1;i++)cin >> p[i];//第i個矩陣為pi*p(i+1)      cin >> i >> j;      MatrixChainOrder(n, p, i, j);  }