第十四章我想放在后面再看，先擱下。希望大家總結(jié)的一些文章也能向我推薦下，大家互相學(xué)習(xí)。
首先，還是建議看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
其次，阿門，感謝老天送給了我們這么一本圣經(jīng)，看了這一章，再次感受到了《算法導(dǎo)論》分析問題的精辟，強(qiáng)悍的魅力。Orz, Orz,各種Orz。
這一章講的是動(dòng)態(tài)規(guī)劃，學(xué)算法的朋友，尤其是搞ACM的，對(duì)這個(gè)策略一定非常熟悉，所以這個(gè)算法網(wǎng)上的分析講解教程也是鋪天蓋地，大家可以多搜幾篇學(xué)習(xí)學(xué)習(xí)。
動(dòng)態(tài)規(guī)劃(Dynamic Programming，簡(jiǎn)稱DP)是通過組合子問題的解來(lái)解決問題的。
注意這里的programming不是指編程，而是指一種規(guī)劃。
因?yàn)镈P用的太廣泛了，并且書上也花了很大的篇幅來(lái)講這一章，所以我也準(zhǔn)備把這一章分幾篇來(lái)總結(jié)，并且我不按照書上的順序來(lái)總結(jié)，也不會(huì)全部用書上的例子。
這一章首先給出一些基礎(chǔ)的概念，然后給出一個(gè)最基礎(chǔ)入門的DP問題，三角形求值問題。
DP適用于子問題不是獨(dú)立的情況，這樣如果用分治法，也會(huì)作許多重復(fù)的工作，而DP只對(duì)子問題求解一次，將其結(jié)果保存在一張表中，從而避免了每次遇到各個(gè)子問題時(shí)重新計(jì)算的情況。
比較分治法于動(dòng)態(tài)規(guī)劃的區(qū)別：
分治法：將問題劃分為一些獨(dú)立的子問題，遞歸的求解各子問題，然后合并子問題的解而得到原問題的解。
eg.
MERGE-SORT(A, p, r)
1 if p < r
2 then q ← |(p + r)/2|
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)
動(dòng)態(tài)規(guī)劃：適用于子問題不是獨(dú)立的情況，也就是各子問題包含公共的子子問題，鑒于會(huì)重復(fù)的求解各子問題，DP對(duì)每個(gè)問
題只求解一遍，將其保存在一張表中，從而避免重復(fù)計(jì)算。
DP算法的設(shè)計(jì)可以分為四個(gè)步驟：
①.描述最優(yōu)解的結(jié)構(gòu)。
②.遞歸定義最優(yōu)解的值。
③.按自底而上的方式計(jì)算最優(yōu)解的值。
④.由計(jì)算出的結(jié)果創(chuàng)造一個(gè)最優(yōu)解。
下面來(lái)看看三角形求值這個(gè)問題：
將一個(gè)由N行數(shù)字組成的三角形，如圖所以，設(shè)計(jì)一個(gè)算法，計(jì)算出三角形的由頂至底的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。
這是在我見過的DP題目中，算是最簡(jiǎn)單的了，我相信就算沒有學(xué)過DP的也會(huì)。
將上圖轉(zhuǎn)化一下：
假設(shè)上圖用map[][]數(shù)組保存。
令f[i][j]表示從頂點(diǎn)(1, 1)到頂點(diǎn)(i, j)的最大值。
則可以得到狀態(tài)轉(zhuǎn)移方程：
f[i][j] = max(f[i+1][j], f[i+1][j+1]) + map[i][j]
此題既適合自頂而下的方法做，也適合自底而上的方法，
當(dāng)用自頂而下的方法做時(shí)，最后要在在最后一列數(shù)中找出最大值，
而用自底而上的方法做時(shí)，f[1][1]即為最大值。
所以我們將圖2根據(jù)狀態(tài)轉(zhuǎn)移方程可以得到圖3：
最大值是30.
很簡(jiǎn)單的DP題，代碼如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
/*
Author: Tanky Woo
Blog: www.WuTianQi.com
Description: 動(dòng)態(tài)規(guī)劃之三角形求值問題
*/
#include <iostream>
using namespace std;
int map[6][6] =
{
{0, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 0, 0},
{0, 3, 8, 0, 0, 0},
{0, 8, 1, 0, 0, 0},
{0, 2, 7, 4, 4, 0},
{0, 4, 5, 2, 6, 5}
};
int f[6][6];
int _max(int a, int b)
{
if(a >= b)
return a;
return b;
}
int main()
{
memset(f, 0, sizeof(f));
for(int i=0; i<6; ++i)
f[5][i] = map[5][i];
for(int i=4; i>=1; --i)
for(int j=1; j<=i; ++j)
f[i][j] = _max(f[i+1][j], f[i+1][j+1]) + map[i][j];
for(int i=1; i<=5; ++i)
{
for(int j=1; j<=5; ++j)
{
cout.width(2);
cout << f[i][j] << " ";
}
cout << endl;
}
cout << f[1][1] << endl;
} |
結(jié)果如圖：
下一篇會(huì)將裝配線的調(diào)度。
在我獨(dú)立博客上的原文：http://www.wutianqi.com/?p=2484
歡迎大家互相學(xué)習(xí)，互相進(jìn)步！