Python算法：动态规划
本節(jié)主要結(jié)合一些經(jīng)典的動(dòng)規(guī)問(wèn)題介紹動(dòng)態(tài)規(guī)劃的備忘錄法和迭代法這兩種實(shí)現(xiàn)方式，并對(duì)這兩種方式進(jìn)行對(duì)比
[這篇文章實(shí)際寫(xiě)作時(shí)間在這個(gè)系列文章之前，所以寫(xiě)作風(fēng)格可能略有不同，嘿嘿]
大家都知道，動(dòng)態(tài)規(guī)劃算法一般都有下面兩種實(shí)現(xiàn)方式，前者我稱(chēng)為遞歸版本，后者稱(chēng)為迭代版本，根據(jù)前面的知識(shí)可知，這兩個(gè)版本是可以相互轉(zhuǎn)換的
1.直接自頂向下實(shí)現(xiàn)遞歸式，并將中間結(jié)果保存，這叫備忘錄法；
2.按照遞歸式自底向上地迭代，將結(jié)果保存在某個(gè)數(shù)據(jù)結(jié)構(gòu)中求解。
編程有一個(gè)原則DRY=Don’t Repeat Yourself，就是說(shuō)你的代碼不要重復(fù)來(lái)重復(fù)去的，這個(gè)原則同樣可以用于理解動(dòng)態(tài)規(guī)劃，動(dòng)態(tài)規(guī)劃除了滿(mǎn)足最優(yōu)子結(jié)構(gòu)，它還存在子問(wèn)題重疊的性質(zhì)，我們不能重復(fù)地去解決這些子問(wèn)題，所以我們將子問(wèn)題的解保存起來(lái)，類(lèi)似緩存機(jī)制，之后遇到這個(gè)子問(wèn)題時(shí)直接取出子問(wèn)題的解。
舉個(gè)簡(jiǎn)單的例子，斐波那契數(shù)列中的元素的計(jì)算，很簡(jiǎn)單，我們寫(xiě)下如下的代碼：
Python| 123 | def fib(i):????if i<2: return 1????return fib(i-1)+fib(i-2) |
好，來(lái)測(cè)試下，運(yùn)行fib(10)得到結(jié)果69，不錯(cuò)，速度也還行，換個(gè)大的數(shù)字，試試100，這時(shí)你會(huì)發(fā)現(xiàn)，這個(gè)程序執(zhí)行不出結(jié)果了，為什么？遞歸太深了！要計(jì)算的子問(wèn)題太多了！
所以，我們需要改進(jìn)下，我們保存每次計(jì)算出來(lái)的子問(wèn)題的解，用什么保存呢？用Python中的dict！那怎么實(shí)現(xiàn)保存子問(wèn)題的解呢？用Python中的裝飾器！
如果不是很了解Python的裝飾器，可以快速看下這篇總結(jié)中關(guān)于裝飾器的解釋：Python Basics
修改剛才的程序，得到如下代碼，定義一個(gè)函數(shù)memo返回我們需要的裝飾器，這里用cache保存子問(wèn)題的解，key是方法的參數(shù)，也就是數(shù)字n，值就是fib(n)返回的解。
Python| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | from functools import wraps def memo(func): ????cache={} ????@wraps(func) ????def wrap(*args): ????????if args not in cache: ????????????cache[args]=func(*args) ????????return cache[args] ????return wrap @memo def fib(i): ????if i<2: return 1 ????return fib(i-1)+fib(i-2) |
重新運(yùn)行下fib(100)，你會(huì)發(fā)現(xiàn)這次很快就得到了結(jié)果573147844013817084101，這就是動(dòng)態(tài)規(guī)劃的威力，上面使用的是第一種帶備忘錄的遞歸實(shí)現(xiàn)方式。
帶備忘錄的遞歸方式的優(yōu)點(diǎn)就是易于理解，易于實(shí)現(xiàn)，代碼簡(jiǎn)潔干凈，運(yùn)行速度也不錯(cuò)，直接從需要求解的問(wèn)題出發(fā)，而且只計(jì)算需要求解的子問(wèn)題，沒(méi)有多余的計(jì)算。但是，它也有自己的缺點(diǎn)，因?yàn)槭沁f歸形式，所以有限的棧深度是它的硬傷，有些問(wèn)題難免會(huì)出現(xiàn)棧溢出了。
于是，迭代版本的實(shí)現(xiàn)方式就誕生了！
迭代實(shí)現(xiàn)方式有2個(gè)好處：1.運(yùn)行速度快，因?yàn)闆](méi)有用棧去實(shí)現(xiàn)，也避免了棧溢出的情況；2.迭代實(shí)現(xiàn)的話(huà)可以不使用dict來(lái)進(jìn)行緩存，而是使用其他的特殊cache結(jié)構(gòu)，例如多維數(shù)組等更為高效的數(shù)據(jù)結(jié)構(gòu)。
那怎么把遞歸版本轉(zhuǎn)變成迭代版本呢？
這就是遞歸實(shí)現(xiàn)和迭代實(shí)現(xiàn)的重要區(qū)別：遞歸實(shí)現(xiàn)不需要去考慮計(jì)算順序，只要給出問(wèn)題，然后自頂向下去解就行；而迭代實(shí)現(xiàn)需要考慮計(jì)算順序，并且順序很重要，算法在運(yùn)行的過(guò)程中要保證當(dāng)前要計(jì)算的問(wèn)題中的子問(wèn)題的解已經(jīng)是求解好了的。
斐波那契數(shù)列的迭代版本很簡(jiǎn)單，就是按順序來(lái)計(jì)算就行了，不解釋，關(guān)鍵是你可以看到我們就用了3個(gè)簡(jiǎn)單變量就求解出來(lái)了，沒(méi)有使用任何高級(jí)的數(shù)據(jù)結(jié)構(gòu)，節(jié)省了大量的空間。
Python| 123456789 | def fib_iter(n):????if n<2: return 1????a,b=1,1????while n>=2:????????c=a+b????????a=b????????b=c????????n=n-1????return c |
斐波那契數(shù)列的變種經(jīng)常出現(xiàn)在上樓梯的走法問(wèn)題中，每次只能走一個(gè)臺(tái)階或者兩個(gè)臺(tái)階，廣義上思考的話(huà)，動(dòng)態(tài)規(guī)劃也就是一個(gè)連續(xù)決策問(wèn)題，到底當(dāng)前這一步是選擇它(走一步)還是不選擇它(走兩步)呢?
其他問(wèn)題也可以很快地變相思考發(fā)現(xiàn)它們其實(shí)是一樣的，例如求二項(xiàng)式系數(shù)C(n,k)，楊輝三角(求從源點(diǎn)到目標(biāo)點(diǎn)有多少種走法)等等問(wèn)題。
二項(xiàng)式系數(shù)C(n,k)表示從n個(gè)中選k個(gè)，假設(shè)我們現(xiàn)在處理n個(gè)中的第1個(gè)，考慮是否選擇它。如果選擇它的話(huà)，那么我們還需要從剩下的n-1個(gè)中選k-1個(gè)，即C(n-1,k-1)；如果不選擇它的話(huà)，我們需要從剩下的n-1中選k個(gè)，即C(n-1,k)。所以，C(n,k)=C(n-1,k-1)+C(n-1,k)。
結(jié)合前面的裝飾器，我們很快便可以實(shí)現(xiàn)求二項(xiàng)式系數(shù)的遞歸實(shí)現(xiàn)代碼，其中的memo函數(shù)完全沒(méi)變，只是在函數(shù)cnk前面添加了@memo而已，就這么簡(jiǎn)單！
Python| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | from functools import wraps def memo(func): ????cache={} ????@wraps(func) ????def wrap(*args): ????????if args not in cache: ????????????cache[args]=func(*args) ????????return cache[args] ????return wrap @memo def cnk(n,k): ????if k==0: return 1 #the order of `if` should not change!!! ????if n==0: return 0 ????return cnk(n-1,k)+cnk(n-1,k-1) |
它的迭代版本也比較簡(jiǎn)單，這里使用了defaultdict，略高級(jí)的數(shù)據(jù)結(jié)構(gòu)，和dict不同的是，當(dāng)查找的key不存在對(duì)應(yīng)的value時(shí)，會(huì)返回一個(gè)默認(rèn)的值，這個(gè)很有用，下面的代碼可以看到。 如果不了解defaultdict的話(huà)可以看下Python中的高級(jí)數(shù)據(jù)結(jié)構(gòu)
| 12345678910 | from collections import defaultdictn,k=10,7C=defaultdict(int)for row in range(n+1):????C[row,0]=1????for col in range(1,k+1):????????C[row,col]=C[row-1,col-1]+C[row-1,col]print(C[n,k]) #120 |
楊輝三角大家都熟悉，在國(guó)外這個(gè)叫Pascal Triangle，它和二項(xiàng)式系數(shù)特別相似，看下圖，除了兩邊的數(shù)字之外，里面的任何一個(gè)數(shù)字都是由它上面相鄰的兩個(gè)元素相加得到，想想C(n,k)=C(n-1,k-1)+C(n-1,k)不也就是這個(gè)含義嗎?
所以說(shuō)，順序?qū)τ诘姹镜膭?dòng)態(tài)規(guī)劃實(shí)現(xiàn)很重要，下面舉個(gè)實(shí)例，用動(dòng)態(tài)規(guī)劃解決有向無(wú)環(huán)圖的單源最短路徑問(wèn)題。假設(shè)有如下圖所示的圖，當(dāng)然，我們看到的是這個(gè)有向無(wú)環(huán)圖經(jīng)過(guò)了拓?fù)渑判蛑蟮慕Y(jié)果，從a到f的最短路徑用灰色標(biāo)明了。
好，怎么實(shí)現(xiàn)呢?
我們有兩種思考方式：
1.”去哪里?”：我們順向思維，首先假設(shè)從a點(diǎn)出發(fā)到所有其他點(diǎn)的距離都是無(wú)窮大，然后，按照拓?fù)渑判虻捻樞?#xff0c;從a點(diǎn)出發(fā)，接著更新a點(diǎn)能夠到達(dá)的其他的點(diǎn)的距離，那么就是b點(diǎn)和f點(diǎn)，b點(diǎn)的距離變成2，f點(diǎn)的距離變成9。因?yàn)檫@個(gè)有向無(wú)環(huán)圖是經(jīng)過(guò)了拓?fù)渑判虻?#xff0c;所以按照拓?fù)漤樞蛟L(fǎng)問(wèn)一遍所有的點(diǎn)(到了目標(biāo)點(diǎn)就可以停止了)就能夠得到a點(diǎn)到所有已訪(fǎng)問(wèn)到的點(diǎn)的最短距離，也就是說(shuō)，當(dāng)?shù)竭_(dá)哪個(gè)點(diǎn)的時(shí)候，我們就找到了從a點(diǎn)到該點(diǎn)的最短距離，拓?fù)渑判虮ＷC了后面的點(diǎn)不會(huì)指向前面的點(diǎn)，所以訪(fǎng)問(wèn)到后面的點(diǎn)時(shí)不可能再更新它前面的點(diǎn)的最短距離！(這里的更新也就是前面第4節(jié)介紹過(guò)的relaxtion)這種思維方式的代碼實(shí)現(xiàn)就是迭代版本。
[這里涉及到了拓?fù)渑判?#xff0c;前面第5節(jié)Traversal中介紹過(guò)了，這里為了方便沒(méi)看前面的童鞋理解，W直接使用的是經(jīng)過(guò)拓?fù)渑判蛑蟮慕Y(jié)果。]
Python| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def topsort(W): ????return W def dag_sp(W, s, t): ????d = {u:float('inf') for u in W} # ????d[s] = 0 ????for u in topsort(W): ????????if u == t: break ????????for v in W[u]: ????????????d[v] = min(d[v], d[u] + W[u][v]) ????return d[t] #鄰接表 W={0:{1:2,5:9},1:{2:1,3:2,5:6},2:{3:7},3:{4:2,5:3},4:{5:4},5:{}} s,t=0,5 print(dag_sp(W,s,t)) #7 |
用圖來(lái)表示計(jì)算過(guò)程就是下面所示：
2.”從哪里來(lái)?”：我們逆向思維，目標(biāo)是要到f，那從a點(diǎn)經(jīng)過(guò)哪個(gè)點(diǎn)到f點(diǎn)會(huì)近些呢?只能是求解從a點(diǎn)出發(fā)能夠到達(dá)的那些點(diǎn)哪個(gè)距離f點(diǎn)更近，這里a點(diǎn)能夠到達(dá)b點(diǎn)和f點(diǎn)，f點(diǎn)到f點(diǎn)距離是0，但是a到f點(diǎn)的距離是9，可能不是最近的路，所以還要看b點(diǎn)到f點(diǎn)有多近，看b點(diǎn)到f點(diǎn)有多近就是求解從b點(diǎn)出發(fā)能夠到達(dá)的那些點(diǎn)哪個(gè)距離f點(diǎn)更近，所以又繞回來(lái)了，也就是遞歸下去，直到我們能夠回答從a點(diǎn)經(jīng)過(guò)哪個(gè)點(diǎn)到f點(diǎn)會(huì)更近。這種思維方式的代碼實(shí)現(xiàn)就是遞歸版本。
這種情況下，不需要輸入是經(jīng)過(guò)了拓?fù)渑判虻?#xff0c;所以你可以任意修改輸入W中節(jié)點(diǎn)的順序，結(jié)果都是一樣的，而上面采用迭代實(shí)現(xiàn)方式必須要是拓?fù)渑判蛄说?#xff0c;從中你就可以看出迭代版本和遞歸版本的區(qū)別了。
Python| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | from functools import wraps def memo(func): ????cache={} ????@wraps(func) ????def wrap(*args): ????????if args not in cache: ????????????cache[args]=func(*args) ????????????# print('cache {0} = {1}'.format(args[0],cache[args])) ????????return cache[args] ????return wrap def rec_dag_sp(W, s, t): ????@memo ????def d(u): ????????if u == t: return 0 ????????return min(W[u][v]+d(v) for v in W[u]) ????return d(s) #鄰接表 W={0:{1:2,5:9},1:{2:1,3:2,5:6},2:{3:7},3:{4:2,5:3},4:{5:4},5:{}} s,t=0,5 print(rec_dag_sp(W,s,t)) #7 |
用圖來(lái)表示計(jì)算過(guò)程就如下圖所示：
[擴(kuò)展內(nèi)容：對(duì)DAG求單源最短路徑的動(dòng)態(tài)規(guī)劃問(wèn)題的總結(jié)，比較難理解，附上原文]
Although the basic algorithm is the same, there are many ways of finding the shortest path in a DAG, and, by extension, solving most DP problems. You could do it recursively, with memoization, or you could do it iteratively, with relaxation. For the recursion, you could start at the first node, try various “next steps,” and then recurse on the remainder, or (if you graph representation permits) you could look at the last node and try “previous steps” and recurse on the initial part. The former is usually much more natural, while the latter corresponds more closely to what happens in the iterative version.
Now, if you use the iterative version, you also have two choices: you can relax the edges out of each node (in topologically sorted order), or you can relax all edges into each node. The latter more obviously yields a correct result but requires access to nodes by following edges backward. This isn’t as far-fetched as it seems when you’re working with an implicit DAG in some nongraph problem. (For example, in the longest increasing subsequence problem, discussed later in this chapter, looking at all backward “edges” can be a useful perspective.)
Outward relaxation, called reaching, is exactly equivalent when you relax all edges. As explained, once you get to a node, all its in-edges will have been relaxed anyway. However, with reaching, you can do something that’s hard in the recursive version (or relaxing in-edges): pruning. If, for example, you’re only interested in finding all nodes that are within a distance r, you can skip any node that has distance estimate greater than r. You will still need to visit every node, but you can potentially ignore lots of edges during the relaxation. This won’t affect the asymptotic running time, though (Exercise 8-6).
Note that finding the shortest paths in a DAG is surprisingly similar to, for example, finding the longest path, or even counting the number of paths between two nodes in a DAG. The latter problem is exactly what we did with Pascal’s triangle earlier; the exact same approach would work for an arbitrary graph. These things aren’t quite as easy for general graphs, though. Finding shortest paths in a general graph is a bit harder (in fact, Chapter 9 is devoted to this topic), while finding the longest path is an unsolved problem (see Chapter 11 for more on this).
好，我們差不多搞清楚了動(dòng)態(tài)規(guī)劃的本質(zhì)以及兩種實(shí)現(xiàn)方式的優(yōu)缺點(diǎn)，下面我們來(lái)實(shí)踐下，舉最常用的例子：矩陣鏈乘問(wèn)題，內(nèi)容較多，所以請(qǐng)點(diǎn)擊鏈接過(guò)去閱讀完了之后回來(lái)看總結(jié)！
OK，希望我把動(dòng)態(tài)規(guī)劃講清楚了，總結(jié)下：動(dòng)態(tài)規(guī)劃其實(shí)就是一個(gè)連續(xù)決策的過(guò)程，每次決策我們可能有多種選擇(二項(xiàng)式系數(shù)和0-1背包問(wèn)題中我們只有兩個(gè)選擇，DAG圖的單源最短路徑中我們的選擇要看點(diǎn)的出邊或者入邊，矩陣鏈乘問(wèn)題中就是矩陣鏈可以分開(kāi)的位置總數(shù)…)，我們每次選擇最好的那個(gè)作為我們的決策。所以，動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度其實(shí)和這兩者有關(guān)，也就是子問(wèn)題的個(gè)數(shù)以及子問(wèn)題的選擇個(gè)數(shù)，一般情況下動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度就是兩者的乘積。
動(dòng)態(tài)規(guī)劃有兩種實(shí)現(xiàn)方式：一種是帶備忘錄的遞歸形式，這種方式直接從原問(wèn)題出發(fā)，遇到子問(wèn)題就去求解子問(wèn)題并存儲(chǔ)子問(wèn)題的解，下次遇到的時(shí)候直接取出來(lái)，問(wèn)題求解的過(guò)程看起來(lái)就像是先自頂向下地展開(kāi)問(wèn)題，然后自下而上的進(jìn)行決策；另一個(gè)實(shí)現(xiàn)方式是迭代方式，這種方式需要考慮如何給定一個(gè)子問(wèn)題的求解方式，使得后面求解規(guī)模較大的問(wèn)題是需要求解的子問(wèn)題都已經(jīng)求解好了，它的缺點(diǎn)就是可能有些子問(wèn)題不要算但是它還是算了，而遞歸實(shí)現(xiàn)方式只會(huì)計(jì)算它需要求解的子問(wèn)題。
練習(xí)1：來(lái)試試寫(xiě)寫(xiě)最長(zhǎng)公共子序列吧，這篇文章中給出了Python版本的5種實(shí)現(xiàn)方式喲！
練習(xí)2：算法導(dǎo)論問(wèn)題 15-4: Planning a company party 計(jì)劃一個(gè)公司聚會(huì)
Start example Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is, the supervisor relation forms a tree rooted at the president. The personnel office has ranked each employee with a conviviality rating, which is a real number. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.
Professor Stewart is given the tree that describes the structure of the corporation, using the left-child, right-sibling representation described in Section 10.4. Each node of the tree holds, in addition to the pointers, the name of an employee and that employee’s conviviality ranking. Describe an algorithm to make up a guest list that maximizes the sum of the conviviality ratings of the guests. Analyze the running time of your algorithm.
原問(wèn)題可以轉(zhuǎn)換成：假設(shè)有一棵樹(shù)，用左孩子右兄弟的表示方式表示，樹(shù)的每個(gè)結(jié)點(diǎn)有個(gè)值，選了某個(gè)結(jié)點(diǎn)，就不能選擇它的父結(jié)點(diǎn)，求整棵樹(shù)選的節(jié)點(diǎn)值最大是多少。
假設(shè)如下：
dp[i][0]表示不選i結(jié)點(diǎn)時(shí)，i子樹(shù)的最大價(jià)值
dp[i][1]表示選i結(jié)點(diǎn)時(shí)，i子樹(shù)的最大價(jià)值
列出狀態(tài)方程
dp[i][0] = sum(max(dp[u][0], dp[u][1]))??(如果不選i結(jié)點(diǎn)，u為結(jié)點(diǎn)i的兒子)
dp[i][1] = sum(dp[u][0]) + val[i]??(如果選i結(jié)點(diǎn)，val[i]表示i結(jié)點(diǎn)的價(jià)值)
最后就是求max(dp[root][0], dp[root][1])
《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的Python算法：动态规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
