C++動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)矩陣鏈乘法
問(wèn)題描述:
給定n個(gè)矩陣的鏈<A1,A2,…,An>,矩陣Ai的規(guī)模為p(i-1)×p(i) (1<=i<=n),求完全括號(hào)化方案,使得計(jì)算乘積A1A2…An所需標(biāo)量乘法次數(shù)最少。
動(dòng)態(tài)規(guī)劃的第一步是尋找最優(yōu)子結(jié)構(gòu),然后就可以利用這種子結(jié)構(gòu)從子問(wèn)題的最優(yōu)解構(gòu)造出原問(wèn)題的最優(yōu)解。在矩陣鏈乘法問(wèn)題中,我們假設(shè)A(i)A(i+1)…A(j)的最優(yōu)括號(hào)方案的分割點(diǎn)在A(k)和A(k+1)之間。那么,繼續(xù)對(duì)“前綴”子鏈A(i)A(i+1)…A(k)進(jìn)行括號(hào)化時(shí),我們應(yīng)該直接采用獨(dú)立求解它時(shí)所得的最優(yōu)方案。
遞歸實(shí)現(xiàn):
?、賹?duì)于i=j的情況下,顯然有m=0,不需要做任何標(biāo)量乘法運(yùn)算。所以,對(duì)于所有的i=1、2…n,m[i,i] = 0.
②當(dāng)i < j的情況,就按照最優(yōu)括號(hào)化方案的結(jié)構(gòu)特征進(jìn)行計(jì)算m[i,j]。假設(shè)最優(yōu)括號(hào)化方案的分割點(diǎn)在矩陣Ak和Ak+1之間,那么m的值就是Ai…k和Ak+1…j的代價(jià)加上兩者量程的代價(jià)的最小值。即。該公式的假設(shè)是最優(yōu)分割點(diǎn)是已知的,但是實(shí)際上不知道。然而,k只有j-i中情況取值。由于最優(yōu)分割點(diǎn)k必定在i~j內(nèi)取得,只需要檢查所有可能的情況,找到最優(yōu)解即可??梢缘贸鲆粋€(gè)遞歸公式

代碼實(shí)現(xiàn)【C++】
#include <iostream>
using namespace std;
#define N 6
#define MAXVALUE 1000000
void matrix_chain_order(int *p,int len,int m[N+1][N+1],int s[N+1][N+1]);
void print_optimal_parents(int s[N+1][N+1],int i,int j);
int main()
{
int p[N+1] = {30,35,15,5,10,20,25};
int m[N+1][N+1]={0};
int s[N+1][N+1]={0};
int i,j;
matrix_chain_order(p,N+1,m,s);
cout<<"m value is: "<<endl;
for(i=1;i<=N;++i)
{
for(j=1;j<=N;++j)
cout<<m[i][j]<<" ";
cout<<endl;
}
cout<<"s value is: "<<endl;
for(i=1;i<=N;++i)
{
for(j=1;j<=N;++j)
cout<<s[i][j]<<" ";
cout<<endl;
}
cout<<"The result is:"<<endl;
print_optimal_parents(s,1,N);
return 0;
}
void matrix_chain_order(int *p,int len,int m[N+1][N+1],int s[N+1][N+1])
{
int i,j,k,t;
for(i=0;i<=N;++i)
m[i][i] = 0;
for(t=2;t<=N;t++) //當(dāng)前鏈乘矩陣的長(zhǎng)度
{
for(i=1;i<=N-t+1;i++) //從第一矩陣開(kāi)始算起,計(jì)算長(zhǎng)度為t的最少代價(jià)
{
j=i+t-1;//長(zhǎng)度為t時(shí)候的最后一個(gè)元素
m[i][j] = MAXVALUE; //初始化為最大代價(jià)
for(k=i;k<=j-1;k++) //尋找最優(yōu)的k值,使得分成兩部分k在i與j-1之間
{
int temp = m[i][k]+m[k+1][j] + p[i-1]*p[k]*p[j];
if(temp < m[i][j])
{
m[i][j] = temp; //記錄下當(dāng)前的最小代價(jià)
s[i][j] = k; //記錄當(dāng)前的括號(hào)位置,即矩陣的編號(hào)
}
}
}
}
}
//s中存放著括號(hào)當(dāng)前的位置
void print_optimal_parents(int s[N+1][N+1],int i,int j)
{
if( i == j)
cout<<"A"<<i;
else
{
cout<<"(";
print_optimal_parents(s,i,s[i][j]);
print_optimal_parents(s,s[i][j]+1,j);
cout<<")";
}
}結(jié)果

到此這篇關(guān)于C++動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)矩陣鏈乘法的文章就介紹到這了,更多相關(guān)C++矩陣鏈乘法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++中的動(dòng)態(tài)規(guī)劃子序列問(wèn)題分析探討
- C++動(dòng)態(tài)規(guī)劃計(jì)算最大子數(shù)組
- C++動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)查找最長(zhǎng)公共子序列
- C++?動(dòng)態(tài)規(guī)劃算法使用分析
- C++編輯距離(動(dòng)態(tài)規(guī)劃)
- c++動(dòng)態(tài)規(guī)劃經(jīng)典算法
- C++動(dòng)態(tài)規(guī)劃之最長(zhǎng)公子序列實(shí)例
- C++動(dòng)態(tài)規(guī)劃之背包問(wèn)題解決方法
- C++動(dòng)態(tài)規(guī)劃中關(guān)于背包問(wèn)題講解
相關(guān)文章
C++操作MySQL大量數(shù)據(jù)插入效率低下的解決方法
這篇文章主要介紹了C++操作MySQL大量數(shù)據(jù)插入效率低下的解決方法,需要的朋友可以參考下2014-07-07
C語(yǔ)言詳盡圖解函數(shù)棧幀的創(chuàng)建和銷(xiāo)毀實(shí)現(xiàn)
我們知道c語(yǔ)言中函數(shù)都是被調(diào)用的,main函數(shù)里面能調(diào)用其他函數(shù),其實(shí)main函數(shù)也是被別的函數(shù)調(diào)用的,下面通過(guò)本文給大家分享c語(yǔ)言函數(shù)棧幀的創(chuàng)建和銷(xiāo)毀過(guò)程,一起看看吧2022-05-05
C++日期類(lèi)(Date)實(shí)現(xiàn)的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何利用C++語(yǔ)言實(shí)現(xiàn)日期類(lèi)(Date),可以實(shí)現(xiàn)確定某年某月有多少天、打印日期等功能,感興趣的可以了解一下2022-07-07
C++實(shí)現(xiàn)關(guān)系與關(guān)系矩陣的代碼詳解
這篇文章主要介紹了C++實(shí)現(xiàn)關(guān)系與關(guān)系矩陣,功能實(shí)現(xiàn)包括關(guān)系的矩陣表示,關(guān)系的性質(zhì)判斷及關(guān)系的合成,本文結(jié)合示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-04-04
C++中平衡二叉搜索樹(shù)的模擬實(shí)現(xiàn)
二叉搜索樹(shù)雖可以縮短查找的效率,但如果數(shù)據(jù)有序或接近有序二叉搜索樹(shù)將退化為單支樹(shù),查找元素相當(dāng)于在順序表中搜索元素,效率低下,所以本文給大家介紹了C++平衡二叉的搜索樹(shù)模擬實(shí)現(xiàn)方法,需要的朋友可以參考下2023-09-09
C++中使用vector存儲(chǔ)并遍歷數(shù)據(jù)的基本步驟
C++標(biāo)準(zhǔn)模板庫(kù)(STL)提供了多種容器類(lèi)型,包括順序容器、關(guān)聯(lián)容器、無(wú)序關(guān)聯(lián)容器和容器適配器,每種容器都有其特定的用途和特性,這篇文章主要介紹了C++中使用vector存儲(chǔ)并遍歷數(shù)據(jù)的基本步驟,需要的朋友可以參考下2025-01-01
C++ 二維數(shù)組參數(shù)傳遞的實(shí)現(xiàn)方法
這篇文章主要介紹了C++ 二維數(shù)組參數(shù)傳遞的實(shí)現(xiàn)方法的相關(guān)資料,這里提供三種方法幫助大家實(shí)現(xiàn)這樣的功能,需要的朋友可以參考下2017-08-08

