快捷導(dǎo)航

C++動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)矩陣鏈乘法

更新時(shí)間：2022年06月30日 10:32:11 作者：成就一億技術(shù)人

動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解

問題描述：

給定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)從子問題的最優(yōu)解構(gòu)造出原問題的最優(yōu)解。在矩陣鏈乘法問題中，我們假設(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++)  //從第一矩陣開始算起，計(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é)果