動態規劃-矩陣連乘（附備忘錄法） - acm1314－IT工程師數位筆記本

文章出處

題目：矩陣連乘，求解計算量最小的加括號方法。

輸入：按順序輸入各個矩陣的行和列。

求解：最少數乘次數和加括號方案。

（詳細情況可自行百度）

題解：用一個數組p[] 來存儲參數，（但要進行處理一下，如：矩陣A 為 10*5 ， B 為 5*15。P【】只記錄 10， 5， 15）

用m【i】【j】來表示從 i->j 的數乘最小值。s[][]記錄過程中的最優步驟.

const int maxn = 100;

int p[maxn], m[maxn][maxn], s[maxn][maxn]

void matrixChain(p[], int m[][maxn], int s[][maxn])
{
    int n=p.length-1;
    for(int i=1; i<=n; i++) m[i][i] = 0;
    for(int r=2; r<=n; r++)//控制行和列   
    for(int i=1; i<=n-r+1; i++)//行 
    {
        int j = i+r-1;//列 
        m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j]//m[i][i]=0, 未加上。 
        s[i][j] = i;
        for(int k=i+1; k<j; k++)
        {
            int 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 traceback(int s[][maxn], int i, int j)
{
    if(i==j) return;
    traceback(s, i, s[i][j]);
    traceback(s, s[i][j]+1, j);
    printf("(%d, %d)  (%d, %d)", i, s[i][j], s[i][j]+1, j);
}
  traceback(s, i, j);

備忘錄法：

int memoizedmatrixChain(int n)
{
    for(int i=1; i<=n; i++)
    for(int j=i; j<=n; j++)
    m[i][j] = 0;
    return lookupChain(1, n);
}

int lookupChain(int i, int j)
{
    if(m[i][j]>0) return m[i][j];
    if(i==j) return 0;
    int u=lookupChain(i+1, j) + p[i-1]*p[i]*p[j];
    s[i][j] = i;
    for(int k=i+1; k<j; k++)
    {
        int t = lookChain(i, k) + lookupChina(k+1, j) + p[i-1]*p[k]*p[j];
        if(t<u)
        {
            u=t;
            s[i][j] = k;
        }
    }
        m[i][j] = u;
        return u;
}

動態規劃和備忘錄法的區別：

備忘錄法是動態規劃的變形。與動態規劃算法一樣，備忘錄方法用表格保存已解決的子問題的答案。在下次需要解此問題時，只要簡單的查看該子問題的解答，而不必重新計算。

不同點：

與動態規劃算法不同的是，備忘錄方法色遞歸方式是自頂向下的，而動態規劃是自底向上的遞歸的。因此備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。

各有千秋：

一般情況下，當一個問題的所有子問題都要至少解一次時，用動態規劃算法比備用錄方法好，此時，動態規劃算法沒有任何多余的計算。同時，對于許多問題，常可利用其規則的表格存取方式，減少動態規劃算法的計算時間和空間需求。當子問題空間中的部分子問題可不必求解時，用備忘錄方法則較有利，因為從其控制結構可以看出，該方法只解那些確實需要求解的子問題。

文章列表