一、學(xué)習(xí)要點(diǎn)

??理解動(dòng)態(tài)規(guī)劃算法的概念。
??掌握動(dòng)態(tài)規(guī)劃算法的基本要素：
??（1）最優(yōu)子結(jié)構(gòu)性質(zhì)
??（2）重疊子問(wèn)題性質(zhì)

??掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟：
??(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。
??(2)遞歸地定義最優(yōu)值。
??(3)以自底向上的方式計(jì)算出最優(yōu)值。
??(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。

??通過(guò)應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。
??（1）矩陣連乘問(wèn)題；
??（2）最長(zhǎng)公共子序列；
??（3）最大子段和
??（4）凸多邊形最優(yōu)三角剖分；
??（5）多邊形游戲；
??（6）圖像壓縮；
??（7）電路布線；
??（8）流水作業(yè)調(diào)度；
??（9）背包問(wèn)題；
??（10）最優(yōu)二叉搜索樹(shù)。

二、算法總體思想

??動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其 基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。

??但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。

??如果 能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。

三、動(dòng)態(tài)規(guī)劃基本步驟

??找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。
??遞歸地定義最優(yōu)值。
??以自底向上的方式計(jì)算出最優(yōu)值。
??根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。

四、矩陣連乘問(wèn)題

??問(wèn)題：給定n個(gè)矩陣{A1,A2,…,An}，其中Ai與Ai+1是可乘的，i=1,2,…n-1。我們要計(jì)算出這 n個(gè)矩陣的連乘積。
??因?yàn)?strong>矩陣乘積滿足結(jié)合律，所以哪兩個(gè)矩陣先乘哪兩個(gè)后乘結(jié)果是一樣的，但是 計(jì)算次數(shù)不一樣，我們要找計(jì)算次數(shù)最小的那個(gè)次序！

4.1 完全加括號(hào)的矩陣連乘積

??完全加括號(hào)的矩陣連乘積可遞歸地定義為：

??設(shè)有四個(gè)矩陣A,B,C,D；它們的維數(shù)分別是：

??總共有五中完全加括號(hào)的方式：

??16000, 10500, 36000, 87500, 34500

??給定n個(gè)矩陣：其中Ai與Ai+1是可乘的，i=1,2,…,n-1?？疾爝@n個(gè)矩陣的連乘積
??由于 矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。
??若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。
??給定n個(gè)矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1，2…，n-1。如何確定計(jì)算 矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。

4.2 窮舉法

??列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。
??算法復(fù)雜度分析：
??對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。
??由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1…Ak)(Ak+1…An)可以得到關(guān)于P(n)的遞推式如下：

4.3 動(dòng)態(tài)規(guī)劃

??將矩陣連乘積AiAi+1…Aj簡(jiǎn)記為A[i:j]，這里i≤j
??考察計(jì)算A[i:j]的最優(yōu)計(jì)算次序。設(shè) 這個(gè)計(jì)算次序在矩陣
Ak和Ak+1之間將矩陣鏈斷開(kāi)，i≤k<j，則其相應(yīng)完全加括號(hào)方式為：
??計(jì)算量：A[i:k]的計(jì)算量加上A[k+1:j]的計(jì)算量，再加上A[i:k]和A[k+1:j]相乘的計(jì)算量。

4.3.1 分析最優(yōu)解的結(jié)構(gòu)

??特征：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈 A[i:k]和A[k+1:j]的次序也是最優(yōu)的。
??矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。

4.3.2 建立遞歸關(guān)系

??設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問(wèn)題的最優(yōu)值為m[1,n]
??當(dāng)i=j時(shí)，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n
??當(dāng)i<j時(shí)，

??可以遞歸地定義m[i,j]為：

??（k的位置只有j-i種可能）

4.3.3 計(jì)算最優(yōu)值

??對(duì)于1≤i≤j≤n不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題。因此，不同子問(wèn)題的個(gè)數(shù)最多只有
??由此可見(jiàn)，在遞歸計(jì)算時(shí)，許多子問(wèn)題被重復(fù)計(jì)算多次。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。
??用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。

??1.計(jì)算A1，A2，A3，A4，A5，A6
??2.計(jì)算（A1A2），（A2A3），（A3A4），（A4A5），（A5A6）
??3.計(jì)算（A1A2A3），…，（A4A5A6）
??4.計(jì)算A[1,4],A[2,5],A[3,6]
??5.計(jì)算A[1,5],A[2,6]
??6.計(jì)算A[1,6]

4.3.4 用動(dòng)態(tài)規(guī)劃法求最優(yōu)解

void MatrixChain(int *p，int n，int **m，int **s)
{
        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];
              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;}
              }
          }
}

??算法復(fù)雜度分析：
??算法matrixChain的主要計(jì)算量取決于算法中對(duì)r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。

五、動(dòng)態(tài)規(guī)劃算法的基本要素

5.1 最優(yōu)子結(jié)構(gòu)

??矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)。
??在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的，然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾。
??利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式 遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。

??同一個(gè)問(wèn)題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問(wèn)題的維度低）

5.2 重疊子問(wèn)題

??遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱(chēng)為子問(wèn)題的重疊性質(zhì)。
??動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。
??通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。

5.3 備忘錄方法

??備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，避免了相同子問(wèn)題的重復(fù)求解。

int LookupChain(int i，int j)
{
       if (m[i][j] > 0) return m[i][j];
       if (i == j) return 0;
       int u = LookupChain(i，i) + 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 = LookupChain(i，k) + LookupChain(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;
}

六、思考題：撿硬幣問(wèn)題

??現(xiàn)有n個(gè)硬幣按順序依次排列在你面前，可以看為一個(gè)數(shù)組coins[]={5,1,2,10,6,2}，請(qǐng)?jiān)诖酥袚烊∪舾蓚€(gè)硬幣，使得所取硬幣累加值最大，撿取個(gè)數(shù)不限，但相鄰兩個(gè)硬幣不得撿取，請(qǐng)?jiān)O(shè)計(jì)相應(yīng)算法，并輸出累加值
??提示：硬幣面值必須是正數(shù)，不能有負(fù)值。建立數(shù)組dp[i]存儲(chǔ)選取前i個(gè)硬幣的累加值文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-717018.html

到了這里，關(guān)于【算法分析與設(shè)計(jì)】動(dòng)態(tài)規(guī)劃（上）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！