计算矩阵连乘积的动态规划算法

本是古典何须时尚 2024-03-22 11:51 78阅读 0赞

/\*  
\* 计算矩阵连乘积的动态规划算法  
\*/

/*
    * 计算矩阵连乘积的动态规划算法
    */
    
    #include<iostream>
    using namespace std;
    const int NUM = 51;
    int p[NUM];			//记录矩阵的维数
    int m[NUM][NUM];	//记录矩阵连城计算最少次数
    int s[NUM][NUM];	//记录断开位置--k
    
    /*
    *	计算矩阵连乘积的动态规划算法
    */
    void MatrixChain(int n) {
    	/*
    	*	对角线全为0-----i=j，问题是平凡的，价值链只包含一个矩阵，
    	*	不用计算--》次数为0
    	*/
    	for (int i = 1; i <= n; i++)
    		m[i][i] = 0;
    
    	/*
    	*  i 表示当前矩阵链的起点---r 表示当前矩阵链的长度，也就是矩阵链中包含的矩阵数量
    	* 
    	*	外层循环 r 表示矩阵链长度。从长度为 2 开始循环到 n，因为矩阵链中至少有两个矩阵。
    	*	内层循环 i 表示矩阵链的起点，j 表示终点。在新的一轮内层循环开始时，
    		首先计算从 i 出发断开的情况下计算矩阵链的最少次数：
    	*/
    	for (int r = 2; r <= n; r++)
    		/*
    		*	n - r + 1 就表示从当前位置开始后面还能选多少个矩阵，
    			也就是当前位置后面可以选择的矩阵链长度
    		*	 i <= n - r + 1 表示当前位置 i 可以取到的最大值，
    			 即设当前矩阵链长度为 r 的时候，i 最大可以取到 n-r+1。
    		*/
    		for (int i = 1; i <= n - r + 1; i++) {
    
    			/*
    			*	j 的定义就是将当前矩阵链的终点位置计算出来，从而方便后续的计算。
    				假设当前矩阵链的长度为 r，则该矩阵链的终点位置应该是从起点位置 i 开始，
    				往后遍历 r 个矩阵得到的位置，需要减去 1 才能得到正确的下标，因此可以使用 i + r - 1 来得到终点位置的下标。
    			*/
    			int j = i + r - 1;
    			//计算初值，从i出断开
    			m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
    			s[i][j] = i;//记录断开位置
    			for (int k = i + 1; k < j; k++) {  //k处断开
    				int t;
    				t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
    				if (t < m[i][j]) {
    					m[i][j] = t;
    					s[i][j] = k;
    				}
    			}
    		}
    }
    
    /*
    *	计算矩阵连乘积最优解的递归算法
    */
    void TraceBcak(int i, int j) {
    	if (i == j)
    		cout << "A" << i << " ";
    	else {
    		cout << "(";
    		TraceBcak(i, s[i][j]);
    		TraceBcak(s[i][j] + 1, j);
    		cout << ")";
    	}
    }
    
    int main() {
    	int p[] = { 10, 100, 5, 50 };
    	int n = sizeof(p) / sizeof(p[0]);
    	MatrixChain(n);
    	TraceBcak(1, n);
    	return 0;
    }