資料課件講義動態(tài)規(guī)劃

1、動態(tài)規(guī)劃小組15級成員楚東方本PPT為思維導向PPT，具體內容詳見：/chudongfang2015/article/details/51590817個人對動態(tài)規(guī)劃的理解： 1.動態(tài)規(guī)劃是一個付出額外空間來節(jié)省時間，就是所謂的空間換時間。 2.動態(tài)規(guī)劃儲存每個狀態(tài)的最優(yōu)解。 3.動態(tài)規(guī)劃是用來把子問題的結果儲存下來，再次用到的時候就不必再進行重復計算。算法導論對動態(tài)規(guī)劃的解釋：動態(tài)規(guī)劃和分治方法相似，都是通過組合子問題的解來求解原問題， 分治方法將問題劃分為互不相交的子問題，遞歸的求解子問題，再將他們的解組合起來，求出原問題的解。與之相態(tài)規(guī)劃應用于子問題重

2、疊的情況，在這種情況下，分治會做許多不必要的工作，它會反復地求解那些公共大子問題，而動態(tài)規(guī)劃算法對每個問題只求解一次，將其解保存在一個表格中，從而無需每次求解一個子問題都重新計算，避免了這種不必要的計算工作，這也就是為什么其可以提高效率的原因。前導題一鋼條切割問題Serling公司購買長鋼條，將其切割為短鋼條出售。切割工序本身沒有成本支出。公司管理層希望知道最佳的切割方案。假定我們知道Serling公司出售一段長為i英寸的鋼條的價格為pi(i=1,2,，單位為美元)。鋼條的長度均為整英寸。圖15-1給出了一個價格表的樣例。鋼條切割問題是這樣的：給定一段長度為n英寸的鋼條和一個價格表pi(i=1

3、,2,n)，求切割鋼條方案，使得銷售收益rn最大。注意，如果長度為n英寸的鋼條的價格pn足夠大，最優(yōu)解可能就是完全不需要切割。動態(tài)規(guī)劃原理給出應用動態(tài)規(guī)劃的四個步驟：1刻畫一個最優(yōu)解的結構特征。234遞歸地定義最優(yōu)解的值。計算最優(yōu)解的值，通常采用自底而上的方法。利用計算出的信息構造一個最優(yōu)解。前導題二矩陣鏈乘法矩陣鏈乘法問題可以表述如下：給定n個矩陣構成的一個鏈（A1*A2*A3*An），其中i=1,2,n,矩陣Ai的維數為p(i-1)*p(i),對于乘積A1*A2*A3*An以一種最小化標量乘法次數的方式進行加括號。所謂矩陣鏈乘法是指當一些矩陣相乘時，如何加括號來改變乘法順序從而來降低乘法次

4、數。例如有三個矩陣連乘：A1*A2*A3，其維數分別為：10*100，100*5，5*50. 如果按照（A1*A2）*A3）來計算的話，求（A1*A2）要10*100*5=5000次乘法，再乘以A3需要10*5*50=2500次乘法，因此總共需要7500次乘法。如果按照（A1*（A2*A3）來計算的話，求（A2*A3）要100*5*50=25000次乘法，再乘以A1需要10*100*50=50000次乘法，因此總共需要75000次乘法?？梢?，按不同的順序計算，代價相差很大。動態(tài)規(guī)劃原理動態(tài)規(guī)劃主要包括以下的四個內容：1 最優(yōu)子結構234重疊子問題重構最優(yōu)解備忘最優(yōu)子結構如果一個問題的最優(yōu)解包含

5、了其子問題的最優(yōu)解，我們就稱此子問題具有最優(yōu)子結構。最優(yōu)子結構在貪心算法中和動態(tài)規(guī)劃算法中體現較多，在動態(tài)規(guī)劃中， 我們用子問題的最優(yōu)解來構造原問題的最優(yōu)解，因此我們必須小心確?？疾炝俗顑?yōu)解中用到的所有子問題（只有這樣才能算當前最優(yōu)）前面兩個例子都用到了最優(yōu)子結構問題，你會發(fā)現在發(fā)掘最優(yōu)子結構性質的過程中，實際上遵循如下模式： 1.證明最優(yōu)解的第一個組成部分是做出一個選擇，做出這個選擇會產生一個或多個子問題。2.對于一個給定的問題，在其可能的一步選擇中，你只是假定已經知道了這個選擇（通過max或min遍歷）3. 給定可獲得最優(yōu)解的選擇后，你確定這次選擇會產生哪些子問題，以及如何更好的刻畫子問題

6、空間。4. 作為構成原問題的最優(yōu)解組成部分，每個子問題的解就是它本身的最優(yōu)解。重疊子問題 適合用動態(tài)規(guī)劃方法求解的最優(yōu)化問題應該具備的第二個性質是子問題空間必須滿足足夠“小”，即問題的遞歸算反復地求解相同的子問題，而不是一直生成新的子問題。一般來講，不同問題的總數通常是輸入規(guī)模的多項式函數為好。如果遞歸算法反復求解相同的子問題，我們就稱最優(yōu)化問題具有重疊子問題性質。與之相對，適合用分治方法求解的問題通常在遞歸的每一步都生成全新的子問題。動態(tài)規(guī)劃算法通常利用重疊子問題性質，對每個子問題求解一次，經解存入一個表中，當再次需要這個子問題時直接查表， 每次查表的代價為時間常量。重構最優(yōu)解 從實際考慮，

7、我們通常將每個子問題所做的選擇存在一個表 中，這樣就不必根據代價值來重構這些信息。對于矩陣鏈乘法， 如果用sij記錄了子問題的最優(yōu)代價，其重構每次選擇只需O(1)，否則其需要w(1)時間。 備忘思路就是對自然但低效的遞歸算法加入備忘機制。與自底而上方法一樣，我們維護一個表記錄子問題的解，但仍保持遞歸算法的控制流程。帶備忘的遞歸算法為每個子問題維護一個表項來保存它的解。每個表項的初值設為一個特殊值，表示尚未填入子問題的解。當遞歸調用過程中第一次遇到子問題時，計算其解，并存入表項。隨后每次遇到同一個子問題，只是簡單的查表，返回其解。例題一：最長公共子序列問題介紹：給定兩個序列X=x1,x2,x3,x4xm,和Y=y1,y2,y3,y4,y5yn.求X和Y長度最長的公共子序列。簡稱LCS例題二：圖論的最短路徑算法：Floy算法求圖任意兩點間的最短路徑例題三：經典問題：石子歸并有n堆石子排成一列，每堆石子有一個重量wi, 每次合并可以合并相鄰的兩堆石子，一次合并的代價為兩堆石子的重量和wi+wi+1。問安排怎樣的合并順序，能夠使得總合