動態(tài)規(guī)劃最好的講解之一

ZZvvh2vjnmrpl4 2019-07-11

展開全文

今天，你AI了沒？

編者按：本文可能是對動態(tài)規(guī)劃講的最易懂深刻的文章之一。

前言：以往見過許多教材，對動態(tài)規(guī)劃（DP）的引入屬于“奉天承運，皇帝昭曰”式：不給出一點引入，見面即拿出一大堆公式嚇人；學(xué)生則死啃書本，然后突然頓悟。針對入門者的教材不應(yīng)該是這樣的。恰好我給入門者講過四次DP入門，迭代出了一套比較靠譜的教學(xué)方法，所以今天跑過來獻(xiàn)丑?，F(xiàn)在我們試著自己來一步步“重新發(fā)明”DP。

從一個生活問題談起

先來看看生活中經(jīng)常遇到的事吧——假設(shè)您是個土豪，身上帶了足夠的1、5、10、20、50、100元面值的鈔票?，F(xiàn)在您的目標(biāo)是湊出某個金額w，需要用到盡量少的鈔票。

　　依據(jù)生活經(jīng)驗，我們顯然可以采取這樣的策略：能用100的就盡量用100的，否則盡量用50的……依次類推。在這種策略下，666=6×100 1×50 1×10 1×5 1×1，共使用了10張鈔票。

　　這種策略稱為“貪心”：假設(shè)我們面對的局面是“需要湊出w”，貪心策略會盡快讓w變得更小。能讓w少100就盡量讓它少100，這樣我們接下來面對的局面就是湊出w-100。長期的生活經(jīng)驗表明，貪心策略是正確的。

　　但是，如果我們換一組鈔票的面值，貪心策略就也許不成立了。如果一個奇葩國家的鈔票面額分別是1、5、11，那么我們在湊出15的時候，貪心策略會出錯：
　　15=1×11 4×1 （貪心策略使用了5張鈔票）
　　15=3×5 （正確的策略，只用3張鈔票）
　　為什么會這樣呢？貪心策略錯在了哪里？

　　鼠目寸光。
　　剛剛已經(jīng)說過，貪心策略的綱領(lǐng)是：“盡量使接下來面對的w更小”。這樣，貪心策略在w=15的局面時，會優(yōu)先使用11來把w降到4；但是在這個問題中，湊出4的代價是很高的，必須使用4×1。如果使用了5，w會降為10，雖然沒有4那么小，但是湊出10只需要兩張5元。
　　在這里我們發(fā)現(xiàn)，貪心是一種只考慮眼前情況的策略。

　　那么，現(xiàn)在我們怎樣才能避免鼠目寸光呢？

　　如果直接暴力枚舉湊出w的方案，明顯復(fù)雜度過高。太多種方法可以湊出w了，枚舉它們的時間是不可承受的。我們現(xiàn)在來嘗試找一下性質(zhì)。

　　重新分析剛剛的例子。w=15時，我們?nèi)绻?1，接下來就面對w=4的情況；如果取5，則接下來面對w=10的情況。我們發(fā)現(xiàn)這些問題都有相同的形式：“給定w，湊出w所用的最少鈔票是多少張？”接下來，我們用f(n)來表示“湊出n所需的最少鈔票數(shù)量”。

　　那么，如果我們?nèi)×?1，最后的代價（用掉的鈔票總數(shù)）是多少呢？
　　明顯，它的意義是：利用11來湊出15，付出的代價等于f(4)加上自己這一張鈔票?，F(xiàn)在我們暫時不管f(4)怎么求出來。
　　依次類推，馬上可以知道：如果我們用5來湊出15，cost就是f(10) 1=1 2=3 。

　　那么，現(xiàn)在w=15的時候，我們該取那種鈔票呢？當(dāng)然是各種方案中，cost值最低的那一個！

　　顯而易見，cost值最低的是取5的方案。我們通過上面三個式子，做出了正確的決策！

　　這給了我們一個至關(guān)重要的啟示—— 只與相關(guān)；更確切地說：

　　這個式子是非常激動人心的。我們要求出f(n)，只需要求出幾個更小的f值；既然如此，我們從小到大把所有的f(i)求出來不就好了？注意一下邊界情況即可。代碼如下：

　　我們以 O(n) 的復(fù)雜度解決了這個問題?，F(xiàn)在回過頭來，我們看看它的原理：

　　這兩個事實，保證了我們做法的正確性。它比起貪心策略，會分別算出取1、5、11的代價，從而做出一個正確決策，這樣就避免掉了“鼠目寸光”！

　　它與暴力的區(qū)別在哪里？我們的暴力枚舉了“使用的硬幣”，然而這屬于冗余信息。我們要的是答案，根本不關(guān)心這個答案是怎么湊出來的。譬如，要求出f(15)，只需要知道f(14),f(10),f(4)的值。其他信息并不需要。我們舍棄了冗余信息。我們只記錄了對解決問題有幫助的信息——f(n).

　　我們能這樣干，取決于問題的性質(zhì)：求出f(n)，只需要知道幾個更小的f(c)。我們將求解f(c)稱作求解f(n)的“子問題”。

　　這就是DP（動態(tài)規(guī)劃，dynamic programming）.

　　將一個問題拆成幾個子問題，分別求解這些子問題，即可推斷出大問題的解。

思考題：請稍微修改代碼，輸出我們湊出w的方案。

幾個簡單的概念

【無后效性】

　　一旦f(n)確定，“我們?nèi)绾螠惓鰂(n)”就再也用不著了。

　　要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出來的，對之后的問題沒有影響。

　　“未來與過去無關(guān)”，這就是無后效性。

　?。▏?yán)格定義：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響。）

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

　　回顧我們對f(n)的定義：我們記“湊出n所需的最少鈔票數(shù)量”為f(n).

　　f(n)的定義就已經(jīng)蘊含了“最優(yōu)”。利用w=14,10,4的最優(yōu)解，我們即可算出w=15的最優(yōu)解。

　　大問題的最優(yōu)解可以由小問題的最優(yōu)解推出，這個性質(zhì)叫做“最優(yōu)子結(jié)構(gòu)性質(zhì)”。

　　引入這兩個概念之后，我們?nèi)绾闻袛嘁粋€問題能否使用DP解決呢？

　　能將大問題拆成幾個小問題，且滿足無后效性、最優(yōu)子結(jié)構(gòu)性質(zhì)。

DP的典型應(yīng)用：DAG最短路

問題很簡單：給定一個城市的地圖，所有的道路都是單行道，而且不會構(gòu)成環(huán)。每條道路都有過路費，問您從S點到T點花費的最少費用。

這個問題能用DP解決嗎？我們先試著記從S到P的最少費用為f(P).
　　想要到T，要么經(jīng)過C，要么經(jīng)過D。從而f(T)=min{f(C) 20,f(D) 10}.

　　好像看起來可以DP。現(xiàn)在我們檢驗剛剛那兩個性質(zhì)：
　　- 無后效性：對于點P，一旦f(P)確定，以后就只關(guān)心f(P)的值，不關(guān)心怎么去的。
　　- 最優(yōu)子結(jié)構(gòu)：對于P，我們當(dāng)然只關(guān)心到P的最小費用，即f(P)。如果我們從S走到T是 S->P->Q->T，那肯定S走到Q的最優(yōu)路徑是S->P->Q。對一條最優(yōu)的路徑而言，從S走到沿途上所有的點（子問題）的最優(yōu)路徑，都是這條大路的一部分。這個問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是顯然的。

　　既然這兩個性質(zhì)都滿足，那么本題可以DP。式子明顯為：

　其中R為有路通到P的所有的點，WR->P 為R到P的過路費。

　代碼實現(xiàn)也很簡單，拓?fù)渑判蚣纯伞?/p>

對DP原理的一點討論

【DP的核心思想】

　　DP為什么會快？
　　無論是DP還是暴力，我們的算法都是在可能解空間內(nèi)，尋找最優(yōu)解。

　　來看鈔票問題。暴力做法是枚舉所有的可能解，這是最大的可能解空間。
　　DP是枚舉有希望成為答案的解。這個空間比暴力的小得多。

　　也就是說：DP自帶剪枝。

　　DP舍棄了一大堆不可能成為最優(yōu)解的答案。譬如：
　　15 = 5 5 5 被考慮了。
　　15 = 5 5 1 1 1 1 1 從來沒有考慮過，因為這不可能成為最優(yōu)解。

　　從而我們可以得到DP的核心思想：盡量縮小可能解空間。

　　在暴力算法中，可能解空間往往是指數(shù)級的大小；如果我們采用DP，那么有可能把解空間的大小降到多項式級。

　　一般來說，解空間越小，尋找解就越快。這樣就完成了優(yōu)化。

【DP的操作過程】

　　一言以蔽之：大事化小，小事化了。

　　將一個大問題轉(zhuǎn)化成幾個小問題；
　　求解小問題；
　　推出大問題的解。

【如何設(shè)計DP算法】

　　下面介紹比較通用的設(shè)計DP算法的步驟。

　　首先，把我們面對的局面表示為x。這一步稱為設(shè)計狀態(tài)。
　　對于狀態(tài)x，記我們要求出的答案(e.g. 最小費用)為f(x).我們的目標(biāo)是求出f(T).
找出f(x)與哪些局面有關(guān)（記為p），寫出一個式子（稱為狀態(tài)轉(zhuǎn)移方程），通過f(p)來推出f(x).

【DP三連】

　　設(shè)計DP算法，往往可以遵循DP三連：

　　我是誰？ ——設(shè)計狀態(tài)，表示局面
　　我從哪里來？
　　我要到哪里去？ ——設(shè)計轉(zhuǎn)移

　　設(shè)計狀態(tài)是DP的基礎(chǔ)。接下來的設(shè)計轉(zhuǎn)移，有兩種方式：一種是考慮我從哪里來（本文之前提到的兩個例子，都是在考慮“我從哪里來”）；另一種是考慮我到哪里去，這常見于求出f(x)之后，更新能從x走到的一些解。這種DP也是不少的，我們以后會遇到。

　　總而言之，“我從哪里來”和“我要到哪里去”只需要考慮清楚其中一個，就能設(shè)計出狀態(tài)轉(zhuǎn)移方程，從而寫代碼求解問題。前者又稱pull型的轉(zhuǎn)移，后者又稱push型的轉(zhuǎn)移。