##提綱

####0.動(dòng)態(tài)規(guī)劃基本概念

####1.動(dòng)態(tài)規(guī)劃的基本問(wèn)題

- 簡(jiǎn)述鋼條切割問(wèn)題

- 子問(wèn)題結(jié)構(gòu)圖

- 需要注意的地方

####2.如何區(qū)別其與貪心算法

- 背包問(wèn)題

- Dijkstra

- ”貪心“的正確性證明

####3.動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系

- 問(wèn)題舉例


####0.動(dòng)態(tài)規(guī)劃基本概念

之所以叫**動(dòng)態(tài)**規(guī)劃，是因?yàn)樵摲椒▽?wèn)題分解為一個(gè)一個(gè)的階段，每個(gè)階段都有各自的狀態(tài)，由特定的狀態(tài)轉(zhuǎn)移方程將當(dāng)前的狀態(tài)推到下一次的狀態(tài)。于是可以看出來(lái)，在每一個(gè)階段都有相應(yīng)的”決策“去選擇接下來(lái)的狀態(tài)，所有階段的決策排成一個(gè)序列，我們稱(chēng)它為策略。這種分階段不斷進(jìn)行狀態(tài)轉(zhuǎn)移的問(wèn)題，我們稱(chēng)之為動(dòng)態(tài)規(guī)劃問(wèn)題。?

上面是運(yùn)籌學(xué)里的概念，更多的是對(duì)于問(wèn)題性質(zhì)的總結(jié)歸納。而在實(shí)際的編程，就像算法導(dǎo)論里講的那樣，是具有最優(yōu)子結(jié)構(gòu)和重疊的子問(wèn)題。所謂最優(yōu)子結(jié)構(gòu)是指原來(lái)的總體可以”劃分為多個(gè)子問(wèn)題的最優(yōu)組合，并且子問(wèn)題可以獨(dú)立求解“。重疊的子問(wèn)題是指在前面不斷遞歸尋找最優(yōu)子問(wèn)題時(shí)，會(huì)不斷碰到一樣的子問(wèn)題。這里不理解沒(méi)關(guān)系，下面我會(huì)具體講解。

####1.動(dòng)態(tài)規(guī)劃的基本問(wèn)題

- 簡(jiǎn)述鋼條切割問(wèn)題（此處只做簡(jiǎn)單講解作為楔子，有興趣可看算法導(dǎo)論第三版相關(guān)內(nèi)容）

>Serling公司購(gòu)買(mǎi)長(zhǎng)鋼條，將其切割為短鋼條出售。切割工序本身沒(méi)有成本支出。公司管理層希望知道最佳的切割方案。假定我們知道Serling公司出售一段長(zhǎng)為i英寸的鋼條的價(jià)格為pi(i=1,2,…，單位為美元)。鋼條的長(zhǎng)度均為整英寸。圖15-1給出了一個(gè)價(jià)格表的樣例。鋼條切割問(wèn)題是這樣的：給定一段長(zhǎng)度為n英寸的鋼條和一個(gè)價(jià)格表pi(i=1,2,…n)，求切割鋼條方案，使得銷(xiāo)售收益rn最大。注意，如果長(zhǎng)度為n英寸的鋼條的價(jià)格pn足夠大，最優(yōu)解可能就是完全不需要切割。

首先我們來(lái)看，如果暴力破解要遍歷多少種方法。因?yàn)槊績(jī)捎⒋缰g都可以切割，它們有兩種選擇，被切割或拒絕，于是需要遍歷2^(n-1)次，無(wú)法忍受。?

現(xiàn)在引入動(dòng)態(tài)規(guī)劃的思想，我先直接拋公式，再根據(jù)公式講解。

>?

pi部分不進(jìn)行繼續(xù)切割，直接作為一個(gè)整體售出 ;?

rn?i部分繼續(xù)切割，考慮所有的情況，分成子問(wèn)題。?

求出所有k值對(duì)應(yīng)的收益最大者作為rn?

根據(jù)這個(gè)數(shù)學(xué)模型，我們可以從兩個(gè)角度看問(wèn)題都可以，先是”自頂向下“：?

要求rn的最大值，而現(xiàn)在假設(shè)已經(jīng)知道i從1到n的rn-1的最大值，只需要拿pi+rn-i各自加起來(lái)再比較就可以知道rn的最大值了。而要知道rn-1的最大值，也是同樣的道理。最后會(huì)遞歸到長(zhǎng)度為0,返回0就行了。?

同樣也可以”自底向上“的看問(wèn)題：?

要知道r1的最大值，可以直接返回p1;要知道r2的最大值，需要比較p1+r1和p2+r0（r0的值為0）;……這樣把所有的情況都比較得出來(lái)后，就可以知道rn的最大值了。?

這里將rn分解為pi+rn-i，并假設(shè)rn-i也是最優(yōu)的方法，就是我開(kāi)始說(shuō)的”最優(yōu)子結(jié)構(gòu)“：先在所有”最優(yōu)子結(jié)構(gòu)“里找到各自進(jìn)行”狀態(tài)轉(zhuǎn)移“后的最優(yōu)值，再遞歸地求解最優(yōu)子結(jié)構(gòu)。?

這里需要注意的是，重疊的子問(wèn)題：

解決辦法很簡(jiǎn)單，建個(gè)數(shù)組把遞歸或遍歷過(guò)的結(jié)果存起來(lái)，下次直接拿就可以了。

- 子問(wèn)題結(jié)構(gòu)圖?


這個(gè)可以理解為把上面那個(gè)樹(shù)的圖壓縮成的東西，壓縮掉的是那些重復(fù)計(jì)算的路徑。每個(gè)定點(diǎn)都是一個(gè)子問(wèn)題，子問(wèn)題的求解時(shí)間則是射出去的邊的總數(shù)。所以這時(shí)問(wèn)題的時(shí)間復(fù)雜度變成了O(n(n+1)/2)，化簡(jiǎn)為O(n^2)。

- 需要注意的地方?

1.有最優(yōu)子結(jié)構(gòu)也可能可以使用貪心算法解決（事實(shí)上能使用貪心算法的問(wèn)題絕大多數(shù)都能使用動(dòng)態(tài)規(guī)劃）。?

2.子問(wèn)題互相之間必須是無(wú)關(guān)的，比如求最長(zhǎng)路徑時(shí)遇到了環(huán)，不同的子問(wèn)題都有重復(fù)的中間節(jié)點(diǎn)，這樣分解出來(lái)的子問(wèn)題就都是相關(guān)的，便不能使用動(dòng)態(tài)規(guī)劃解決。

####2.如何區(qū)別其與貪心算法

- 背包問(wèn)題?


大家應(yīng)該都知道貪心算法是每個(gè)階段都追求局部的最優(yōu)，然后達(dá)成全局的最優(yōu)，必須要證明這樣的合理性才能使用貪心算法，因?yàn)榇蟛糠智闆r下全局的最優(yōu)每個(gè)階段都不一定最優(yōu)。?

像這里的部分背包問(wèn)題可以使用反證法，假設(shè)當(dāng)前背包里的物品價(jià)值已達(dá)到最高，而且沒(méi)有每磅價(jià)值最高的物品，那么可以移除當(dāng)前背包里價(jià)值最低的物品，并放入價(jià)值最高的物品，則背包的價(jià)值提升，與假設(shè)矛盾。于是這個(gè)問(wèn)題可以每一次都拿當(dāng)前價(jià)值最高的物品而得到整體價(jià)值的最高。

- Dijkstra?

[Dijkstra-維基百科](https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95)?

這里默認(rèn)大家都懂這算法了。事實(shí)上這個(gè)算法就是典型的貪心算法，但這種問(wèn)題也往往是動(dòng)態(tài)規(guī)劃里的入門(mén)示例（我的運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃的例子就是這個(gè)）。?

Dijkstra的貪心原理的正確性在于：

>一個(gè)圖中的點(diǎn)分為兩個(gè)集合，一個(gè)是V：所有點(diǎn)的集合；另一個(gè)是S：表明已經(jīng)找到最短路徑的點(diǎn)，即一個(gè)點(diǎn)找到了最短路就加入S，而我們要證的就是加入S的點(diǎn)的最短路都已確定。設(shè)d[u]表示u點(diǎn)到源點(diǎn)的當(dāng)前距離，z[u]表示u到源點(diǎn)的最短路。?

和證明整數(shù)的唯一分解定理有些類(lèi)似，假設(shè)一個(gè)點(diǎn)u是加入S集合中的第一個(gè)不滿足d[u]=z[u]的點(diǎn)，如果u點(diǎn)到源點(diǎn)s沒(méi)有路，那么d[u]=z[u]=無(wú)窮，就不滿足z[u]=d[u]這個(gè)條件了，所以可以得出s到u一定有條最短路。我們假設(shè)y點(diǎn)是V-S中的一點(diǎn)，y-u不一定存在，也就是說(shuō)y有可能就是u點(diǎn)，然后假設(shè)x是y的緊鄰前驅(qū)，但s-x也不一定存在，s點(diǎn)有可能為x點(diǎn)，因?yàn)閤已經(jīng)加入S了，x又是y的緊鄰前驅(qū)，所以在松弛時(shí)已經(jīng)計(jì)算出d[y]=z[y]，（因?yàn)閳D中的s-u是一條最短路了，所以此路上的s-y也是s到y(tǒng)的最短路，否則s-u就不是s到u的最短路了）（根據(jù)收斂性質(zhì)：（此中的字母與本文無(wú)關(guān)，只是描述收斂性質(zhì)用到）s-u-v是圖G某u點(diǎn),v點(diǎn)屬于V的最短路徑，而且在松弛邊（u，v）之前的任何時(shí)間d[u]=z[u],則在操作后總有d[v]=z[v]），到了這里我們就得出了兩個(gè)不等式，1.在這條路徑中看得出d[u]>=z[u]>=z[y]=d[y]，2.在選擇u點(diǎn)時(shí)，只有d[u]<=d[y]時(shí)，才會(huì)選到u點(diǎn)加入S，從而得到d[u]=d[y]=z[u]=z[y]。?

- ”貪心“的正確性證明?

易知，貪心算法一般是特殊的動(dòng)態(tài)規(guī)劃問(wèn)題，其特殊性在于能證明局部最優(yōu)策略的正確性。

####3.動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系

- 問(wèn)題舉例



我們能看到，這個(gè)問(wèn)題的式子本身是很直觀的線性規(guī)劃問(wèn)題，假如求最大值的表達(dá)式?jīng)]有二次方，則可以直接用高中學(xué)習(xí)的線性規(guī)劃知識(shí)畫(huà)圖解決。但是這種靜態(tài)規(guī)劃問(wèn)題，可以人為的加入**階段**的概念，然后用動(dòng)態(tài)規(guī)劃的思想解決，就像圖片里那樣。